# Perl weekly challenge 56

I have been getting the Perl weekly email for a while (FixMyStreet still runs happily on Perl), and each week it mentions the Perl weekly challenge. I haven’t previously had time to do it, but there’s less on at the moment! This week’s challenge involved two tasks, finding pairs of indices in array whose difference was a number, and finding a path in a binary tree that sums to a number. Not really something I need in normal work, so a bit of a change, not unwelcome. In both tasks, I think I came up with a relatively elegant solution, so I might as well go through them here as a memento.

For both tasks, I put the main code in a function, then the only top-level code
needed was imports and some `Test::More` calls to show that the code
worked. The full code is available
on GitHub,
so below I will only talk about the main function.

## Task 1

The first brute-force naive approach I considered was a double loop, trying
every pair to see if it matched. But then I realised that as the array is
already sorted, you can test a pair and then either increase the upper index
if the difference is too low, or increase the lower index if it’s too high.
So that’s what my `diffk` function does; passed in the wanted difference
as `$p{k}` and the array in `$p{N}`, storing the two indices
being considered in `$i` and `$j`, and moving along/ storing
the result depending on the calculated difference.

```
sub diffk {
my %p = @_;
my ($i, $j) = (0, 1);
my $size = @{$p{N}};
my @out;
while ($i < $size && $j < $size) {
my $diff = $p{N}[$j] - $p{N}[$i];
if ($diff == $p{k} && $i != $j) { # Success
push @out, [$j,$i];
$i++;
} elsif ($diff > $p{k}) { # Too large
$i++;
} else { # Too small, or same
$j++;
}
}
return @out;
}
```

Called as `diffk(k => 2, N => [2, 7, 9])`, it would return `([2,1])`.

## Task 2

This task was made much easier by use of the Tree::Binary package.
Once you have a tree object, it has a `traverse` function that calls
its argument for each node of the tree. In that function, we ignore anything
that isn’t a leaf (we only want complete paths), and then step up from
that leaf through its parents constructing an array of all the values along
the way. If the sum of those values is the wanted value, store that result.

```
sub pathsum {
my ($tree, $sum) = @_;
die "Not a Tree::Binary object" unless $tree && $tree->isa('Tree::Binary');
my $result;
$tree->traverse(sub {
my $t = shift;
return unless $t->isLeaf;
my @nodes;
while ($t) {
unshift @nodes, $t->getNodeValue;
$t = $t->getParent;
}
$result = \@nodes if sum(@nodes) == $sum;
});
return $result;
}
```

Called as `pathsum($tree, 22)`, where `$tree` is
a Tree::Binary object matching the tree shown in the challenge,
it would return `[5, 4, 11, 2]`.

## Conclusion

Writing the programs with associated tests was useful, especially for some tidying-up refactoring I did at the end. I think the Task 2 code is clearer than Task 1, but I’m not sure I’d do anything to Task 1 – it is simple and trying to encapsulate anything somehow I think would actually make it more complicated to follow.