Rafraîchissoir

By Shahed Nooshmand

Perl Weekly Challenge: week 56

No dumb one-liners this week.

Task #1

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.

The easiest way to do this is probably with two nested loops. This is the general solution for a given array of numbers, and perhaps the best one at O(n²) since you’d have to sum up every two numbers in the array.

With this particular problem, however, we can do better; since we know the array is sorted. We can iterate over the array at O(n) and look for a correct number in the array which meets our diff constraint using binary search at O(log n), which gets us down to O(n log n).

Assuming there is a sub infix:« 🔎 » ($needle, @haystack) that returns the index of $needle in @haystack or Nil, the following would print out all the right pairs of indices:

(There are a couple of implementations of binary search in Raku on Rosetta Code.)

#!/usr/bin/env raku

my @N = 2, 7, 9;
my $k = 2;

for ^@N -> $i {
	my $j = (@N[$i] + $k) 🔎 @N[$i+1..*];
	say $i, " ", 1 + $i + $j with $j
}

Which operates at O(log n!), which is practically O(n log n).

Task #2

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.

Here’s the example script:

#!/usr/bin/env raku

multi paths(Pair $tree) {
	|paths($tree.value).map: {$tree.key, |$_}
}
multi paths(Positional $nodes) {
	$nodes.map: { paths $_ }
}
multi paths($leaf) { $leaf }

my $tree = 5 => (4 => 11 => (7, 2),
                 8 => (9 => 1, 13));
say %(paths($tree).map: {.sum => $_}){22}

In the above notation, each parent is the key of a Pair, and its children are the value of that Pair. The variable $tree is therefore a representation of the binary tree below, as came in the text of the task.

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

The paths subroutine returns a list of all the paths in the tree, obviously. When its argument is a single leaf at the bottom of the tree, it act as the identity function. When its argument is a list of nodes, it returns a list of all the paths for each node, recursively calling paths. For arguments in form of a Pair, i.e. a parent and its child(ren) … well … you know what happens.

Note that we use | to flatten the list of different paths because of the function’s recursive nature. Without it, paths $tree would give the following abstract:

((5 ((4 (11 7)) (4 (11 2)))) (5 ((8 ((9 1))) (8 13))))

Which is sort of correct, but makes calculating the sums harder.

The final statement maps every possible path sum in the tree to the path that produces it, hence the program will say:

(5 4 11 2)

If we asked for 21 instead of 22, it would say:

(Any)

Which means no path in the binary tree has a sum of 21.