laurent_r

These are some answers to the Week 56 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a couple of days (April 19, 2020). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Diff-k

You are given an array @N of positive integers (sorted) and another non negative integer k.

Write a script to find if there exists 2 indices i and j such that A[i] - A[j] = k and i != j.

It should print the pairs of indices, if any such pairs exist.

Example:

@N = (2, 7, 9)
$k = 2

Output : 2,1

Since the array items are not necessarily adjacent and we have to print all the matching pairs, I do not see any other way than basically trying all pairs. Well, since the array is sorted, we don’t really need to test all possible pairs, but only all combinations of 2 elements of the input array.

Diff-k in Perl

There are some CPAN modules to generate combinations, but, as usual, I consider that it would somewhat cheating to use a ready-made solution. So, I’ll do it “the hard way” and manually generate the combinations. This is quite simple. The program uses two nested loops to iterate over the array, and prints out the pairs for which the difference is the target. The target difference and the array are passed as two arguments to the program. If no argument is passed, then the program uses some default values.

#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;

sub find_diff {
    my ($diff, @array) = @_;
    for my $i (0..$#array - 1) {
        for my $j ($i +1.. $#array) {
            say "Indices $j and $i (values: $array[$j], $array[$i])" 
                if $array[$j] - $array[$i] == $diff;
        }
    }
}
my $k = shift // 2;
my @N = @ARGV;
@N = (2, 7, 9) unless @N;
find_diff $k, @N;

Here are some sample runs:

$ perl find_diff.pl
Indices 2 and 1 (values: 9, 7)

$ perl find_diff.pl 2 4 5 7 9 11 15 17
Indices 2 and 1 (values: 7, 5)
Indices 3 and 2 (values: 9, 7)
Indices 4 and 3 (values: 11, 9)
Indices 6 and 5 (values: 17, 15)

$ perl find_diff.pl 4 4 5 7 9 11 15 17
Indices 3 and 1 (values: 9, 5)
Indices 4 and 2 (values: 11, 7)
Indices 5 and 4 (values: 15, 11)

Diff-k in Raku

Raku has a built-in method, combinations, which can generate all combinations of two (or any other number, or even a range of numbers) items from an input list. So, our program will just generate all combinations of indices and print out those matching the criteria:

use v6;

sub find-diff ($diff,  @array) {
    for (0..@array.end).combinations: 2 -> ($i, $j) {
        say "Indices $j and $i (values: @array[$j], @array[$i])" 
            if @array[$j] - @array[$i] == $diff;
    }
}
my ($k, @N);
if @*ARGS.elems > 2 {
    ($k, @N) = @*ARGS;
} else {
    $k = 2;
    @N = 2, 7, 9;
}
find-diff $k, @N;

The program uses arguments passed to it (or default values if there isn’t enough arguments).

Here are some sample runs:

$ perl6 find_diff.p6
Indices 2 and 1 (values: 9, 7)

$ perl6 find_diff.p6  2 4 5 7 9 11 15 17
Indices 2 and 1 (values: 7, 5)
Indices 3 and 2 (values: 9, 7)
Indices 4 and 3 (values: 11, 9)
Indices 6 and 5 (values: 17, 15)

$ perl6 find_diff.p6  4 4 5 7 9 11 15 17
Indices 3 and 1 (values: 9, 5)
Indices 4 and 2 (values: 11, 7)
Indices 5 and 4 (values: 15, 11)

Task 2: Path Sum

You are given a binary tree and a sum, write a script to find if the tree has a path such that adding up all the values along the path equals the given sum. Only complete paths (from root to leaf node) may be considered for a sum.

Example: given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  9
 /  \      \
7    2      1

For the given binary tree, the partial path sum 5 → 8 → 9 = 22 is not valid.

The script should return the path 5 → 4 → 11 → 2 whose sum is 22.

So basically we have to implement a depth-first tree traversal algorithm. Once this is done, finding the paths matching the criteria is quite easy.

The first question to be answered is: how do we represent a binary tree? There are a number of possibilities. We’ll just present three.

The most obvious way might be a nested hash of hashes. Each node by a hash with three items: the current node value, a reference to the left child and a reference to the right child. For example, the top of the binary tree shown above could look like this: { val => 5, left => {val => 4, left => { val => 11}}, right => { val => 8, left => { val => 13}, right { val => 9 }}}. Or, in a more graphical way:

{ val => 5, 
  left => {
    val => 4, 
    left => { 
        val => 11
    }
  }, 
  right => { 
    val => 8, 
    left => { 
        val => 13
        }, 
        right { 
            val => 9 
        }
    }
}

But that’s quite verbose, I don’t like doing so much typing. A more concise way would to use a nested array of arrays. For each node, the first array item is the current value, the second item the left child and the third item the right child. The top of the tree shown above might look like this: [5, [4, [11]], [8, [13], ]]. Or, more graphically:

[
    5, 
    [
        4, [11]
       ], 
    [
        8, [13] 
    ]
]

We could even use a simple flat array in a way similar to what is commonly done for binary heaps (i.e. a binary tree that keeps a partial order). Here we’re not interested with partial order, but the idea is to use an array with the following properties. The item with subscript 0 is the value of the root node. The index of an element is used to compute the index of its parent and the indices of its children. The basic idea is that, for any node, the index of its parent is about half the index of the current node, and, conversely, the indices of the children are about twice the index of the current node. More precisely, for a tree starting at index 0, the exact formulas for a node with index $n are commonly as follows:

• parent: int( ($n-1)/2 )
• left child: 2*$n + 1
• right child: 2*$n + 2

The root node is at index 0, and its children are at positions 1 and 2. The children of item with index 1 are at positions 3 and 4 and the children of 2 are at positions 5 and 6.

These rules may seem a bit complicated (and it is a bit tedious to compute these things manually), but they’re in fact quite easy to implement and the binary tree:

      5
     / \
    4   8
   /   / \
  11  13  9

would be represented by this simple array:

[5, 4, 8, 11, , 13, 9]

We will implement such a data structure in the Raku solutions below.

Note that it is very easy to populate the binary-heap-like array from a graphical representation: you just need to perform a breadth-first traversal and provide empty slots for missing nodes.

Path Sum in Perl

We’ll use a nested array of arrays to represent the binary tree. We implement a recursive dfs (for depth-first search) subroutine to traverse the various paths of the tree. At each call of the subroutine, we keep track of the current sum and of the current path. When we reach a leaf (no more child), we print the path if the current sum is equal to the target value.

#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;

my $tree = [5, [4, [11, [7], [2]]], [8, [13], [9, [1]]]] ;

sub dfs {
    my ($node, $target, $sum, $path) = @_;
    my $new_sum = $sum + $node->[0];
    unless (exists $node->[1] or exists $node->[2]) {
        say $new_sum, " -> @$path $node->[0]" if $new_sum == $target;
    }
    dfs($node->[1], $target, $new_sum, [@$path, $node->[0]]) 
        if defined $node->[1];
    dfs($node->[2], $target, $new_sum, [@$path, $node->[0]]) 
        if defined $node->[2];
}

my $target = shift // 22;
dfs($tree, $target, 0, []);

The default target is 22, but we can pass another value to the program.

Here are a few runs:

$ perl bin_tree_sum.pl
22 -> 5 4 11 2

$ perl  bin_tree_sum.pl 23
23 -> 5 8 9 1

$ perl  bin_tree_sum.pl 22
22 -> 5 4 11 2

$ perl  bin_tree_sum.pl 27
27 -> 5 4 11 7

$ perl  bin_tree_sum.pl 26
26 -> 5 8 13

Path Sum in Raku

We’ll implement two solutions for the tree.

Implementing the Tree as a Nested Array of Arrays

This is a port to Raku of our Perl program above:

use v6;

my @tree = [5, [4, [11, [7], [2]]], [8, [13], [9, [1]]]] ;

sub dfs (@node, $target, $sum, @path) {
    my $new-sum = $sum + @node[0];
    unless @node[1]:exists or @node[2]:exists {
        say $new-sum, " -> @path[] @node[0]" if $new-sum == $target;
    }
    dfs(@node[1], $target, $new-sum, (@path, @node[0]).flat) 
        if defined @node[1];
    dfs(@node[2], $target, $new-sum, (@path, @node[0]).flat) 
        if defined @node[2];
}

my $target = @*ARGS.elems == 1 ?? @*ARGS[0] !! 22;
dfs(@tree, $target, 0, []);

Here are a few runs:

$ perl6  bin_tree_sum.p6
22 -> 5 4 11 2

$ perl6  bin_tree_sum.p6 22
22 -> 5 4 11 2

$ perl6  bin_tree_sum.p6 24

$ perl6  bin_tree_sum.p6 26
26 -> 5 8 13

$ perl6  bin_tree_sum.p6 23
23 -> 5 8 9 1

Implementing the Tree as a Flat Array (Binary-Heap-like)

As explained above, we can use a flat array to represent a binary tree, with the following rules: the indices of the children of a node with index $n are as follows:

• left child: 2*$n + 1
• right child: 2*$n + 2

In Raku, it isn’t possible to just leave an “empty slot” when defining an array. We need to provide undefined values, such as, for example, Nil, Any, or Int. We’ll use Int since it is the most consistent option with a tree made of integers.

The code isn’t much more complicated than before:

use v6;

my @tree = [5, 4, 8, 11, Int, 13, 9, 7, 2, Int, Int, Int, Int, 1];

sub dfs ($index, $target, $sum, @path) {
    sub children ($i) { 2*$i+1, 2*$i+2 }
    my $cur-val = @tree[$index];
    my $new-sum = $sum + $cur-val;
    my ($left, $right) = children $index; 
    unless defined @tree[$left] or defined @tree[$right] {
        say $new-sum, " -> @path[] $cur-val" if $new-sum == $target;
    }
    dfs($left, $target, $new-sum, (@path, $cur-val).flat) 
        if defined @tree[$left];
    dfs($right, $target, $new-sum, (@path, $cur-val).flat) 
        if defined @tree[$right];
}

my $target = @*ARGS.elems == 1 ?? @*ARGS[0] !! 22;
my $root-node = 0;
dfs($root-node, $target, 0, []);

Here are a few runs:

$ perl6 bin_tree_sum2.p6
22 -> 5 4 11 2

$ perl6 bin_tree_sum2.p6 22
22 -> 5 4 11 2

$ perl6 bin_tree_sum2.p6 23
23 -> 5 8 9 1

$ perl6 bin_tree_sum2.p6 24

$ perl6 bin_tree_sum2.p6 26
26 -> 5 8 13

Wrapping up

The next week Perl Weekly Challenge is due to start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, April 26, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.