RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved vector multiplication and a recently-invented data structure. (Note that this is open until 2 January 2022.)

Task 1: Dot Product

You are given 2 arrays of same size, @a and @b.

Write a script to implement Dot Product.

Pretty straightforward, really. Raku:

sub dotproduct(@a,@b) {
  my $p=0;
  for 0..@a.end -> $i {
    $p += @a[$i]*@b[$i];
  }
  return $p;
}

In an enumerating language (here Rust):

fn dotproduct(a: Vec<u32>, b: Vec<u32>) -> u32 {
    let mut p=0;
    for (i,va) in a.iter().enumerate() {
        p+=va*b[i];
    }
    p
}

Task 2: Palindromic Tree

You are given a string $s.

Write a script to create a Palindromic Tree for the given string.

The actual tree structure is quite fiddly to produce - and the test cases don't test that you've actually produced one. I found a Python implementation by TimSC on Rosetta Code and used that as the basis for my Perl, Raku and Ruby solutions; "Purefox" there had already translated it to Kotlin. PostScript doesn't have an object system, and I don't know how to drive Lua's, so I used a more basic O(N²)-ish algorithm to produce the same list of all palindromes found in the input; and because I don't really get Rust lifetimes and references yet, I ended up using it there too.

(I've found several posts about this structure, but no practical ways of using it; it's a lot more faff to get O(N)-ish performance, and arraying the results in order removes that advantage anyway. I suppose if I were using really huge strings…)

The full version is too long to include, but here's the cheating O(N²) version in Lua:

function eertree(str)
   pal={}
   q={}
   for i = 1,#str do
      for j = i,#str do
         strpal=string.sub(str,i,j)
         strrev=string.reverse(strpal)
         if strpal == strrev and q[strpal] == nil then
            table.insert(pal,strpal)
            q[strpal]=true
         end
      end
   end
   return pal
end

Full code on github.