Perl weekly challenge 56

13th April 2020

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.