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.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.