I’ve been doing the Perl Weekly Challenges. The latest involved colinear points and binary tree sums. (Note that this is open until 3 January 2021.)

TASK #1 › Max Points

You are given set of co-ordinates @N.

Write a script to count maximum points on a straight line when given co-ordinates plotted on 2-d plane.

sub mp {
  my @c=@_;
  my $epsilon=0.0001;
  my $mxp=0;

So I do a nested search: for each (ordered) pair of coordinates A and B, see how many of the others fall on the line they form.

  foreach my $a (0..$#c-2) {
    foreach my $b ($a+1..$#c-1) {
      my @d=map {$c[$b][$_]-$c[$a][$_]} (0,1);

Any two points are in a straight line…

      my $pil=2;
      foreach my $c ($b+1..$#c) {
        my $tp=0;
        my @v=map {$c[$c][$_]-$c[$a][$_]} (0,1);

A bit of special-casing deals with the situation where A and B are on the same horizontal or vertical coordinate.

        if ($d[0]==0) {
          if ($v[0]==0) {
            $tp=1;
          }
        } elsif ($d[1]==0) {
          if ($v[1]==0) {
            $tp=1;
          }

Then it's time for floating-point. Yeah, probably could have done it all in integer. max(v[0],d[0]) % min(v[0],d[0]) == 0 and so on, but it starts getting into special cases quite quickly. So I got lazy. epsilon is there because you can never trust floating-point equality. Python has a Fraction class, Raku has Rat, Ruby has Rational and Rust has fraction, but I basically just implemented this same system again.

        } elsif (abs($v[0]/$d[0]-$v[1]/$d[1])<$epsilon) {
          $tp=1;
        }
        if ($tp) {
          $pil++;
        }
      }
      if ($pil > $mxp) {
        $mxp=$pil;
      }
    }
  }
  return $mxp;
}

Raku is basically the same.

Python should have explicit conversion to float (though the test cases don't check for this).

                elif abs(float(v[0])/float(d[0])-float(v[1])/float(d[1])) < epsilon:

Ruby is much the same again. Rust gets more fun, not least because the copy of the book I have uses ... for inclusive range but the compiler has ..=. (And people complained about Ruby changing its syntax.)

TASK #2 › Sum Path

You are given binary tree containing numbers 0-9 only.

Write a script to sum all possible paths from root to leaf.

Rather than parse an ASCII diagram, I started with an array representation of the tree, with non-existing nodes represented by undef.

is(sp(1,2,undef,3,4),13,'example 1');
is(sp(1,2,3,4,undef,5,6),26,'example 2');

Then it's back to good old FIFO buffer code. Which in Perl is trivial (if sluggish); in other languages, a bit less so. See, the great thing is that a Perl array isn't a first-class type: if I say [@array,$variable] that's simply a reference to a new array consisting of all the values of the old array plus variable on the end. Which is what I want. Each entry in @path is a simple list of all the array indices needed to get to this point. If it has no child nodes, I add the sum of entries to the total.

sub sp {
  my @t=@_;
  my $s=0;
  my @path=([0]);
  while (my $a=shift @path) {
    my $c=($a->[-1])*2+1;
    my $tn=1;
    foreach my $ac ($c,$c+1) {
      if ($ac <= $#t && defined $t[$ac]) {
        push @path,[@{$a},$ac];
        $tn=0;
      }
    }
    if ($tn) {
      $s+=sum(map {$t[$_]} @{$a});
    }
  }
  return $s;
}

This is the sort of thing that did my head in in Raku a few months back. And even here it's a bit dodgy; if I called my temporary variable @a rather than $a it behaved differently. Also note the double flat plus list; all of those are necessary in order to get what seems to me the simple result. Raku doesn't like this use of undef so I substituted -1.

sub sp (**@t) {
  my $s=0;
  my @path=((0));
  while (@path) {
    my $a=shift @path;
    my $c=($a[$a.end])*2+1;
    my $tn=1;
    for ($c,$c+1) -> $ac {
      if ($ac <= @t.end && @t[$ac] != -1) {
        push @path,($a.flat,$ac).flat.list;
        $tn=0;
      }
    }
    if ($tn) {
      $s+=sum(map {@t[$_]},$a.list);
    }
  }
  return $s;
}

For Python I used the deque type for the main buffer. It's happy with None though. I did end up using a temporary array variable, which I suppose is what the other languages are doing internally.

def sp(*t):
    s=0
    path=collections.deque([[0]])
    while len(path)>0:
        a=path.popleft()
        c=a[-1]*2+1
        tn=1
        for ac in range(c,c+2):
            if ac < len(t) and t[ac] is not None:
                b=a.copy()
                b.append(ac)
                path.append(b)
                tn=0
        if tn:
            s += sum(t[i] for i in a)
    return s

Ruby has nil, though it doesn't need a deque type.

def sp(*t)
  s=0
  path=[[0]]
  while (a=path.shift) do
    c=a[-1]*2+1
    tn=true
    c.upto(c+1) do |ac|
      if ac <= t.length && !t[ac].nil? then
        path.push([a,ac].flatten)
        tn=false
      end
    end
    if tn
      s += a.map{|i| t[i]}.sum()
    end
  end
  return s
end

And Rust, ah, beautiful Rust… which gets the deque and type conversions, as well as the explicit temporary variable.

fn sp(t: Vec<i32>) -> i32 {
    let mut s: i32=0;
    let mut path: VecDeque<Vec<i32>>=VecDeque::new();
    path.push_back(vec![0]);
    while path.len() > 0 {
        let a=path.pop_front().unwrap();
        let c=((a.last().unwrap())*2+1) as usize;
        let mut tn=true;
        for ac in c..=c+1 {
            if ac < t.len() && t[ac]>-1 {
                let mut b=a.clone();
                b.push(ac as i32);
                path.push_back(b);
                tn=false;
            }
        }
        if tn {
            s+=a.iter().map(|i| t[*i as usize]).sum::<i32>();
        }
    }
    return s;
}

But this is feeling increasingly like the right way to do things.

Full code on github.