This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)
Personal note: It’s been an extremely challenging couple of weeks for me, due to a family emergency. As such I’m combining my solutions into a single, shorter blog post this week. If you also follow my review posts on the perlweeklychallenge.org site, you’ll note they are quite late as well. I’m sorry about that! Hopefully things will settle down so I can get back into my rhythm!
Task 1 › 3Sum Problem
The 3Sum (or kSum) problem is another classic in computer science. With this, you are given a target sum ($T) and a list of integers (@L), and are asked to find all unique sets of 3 numbers in @L that sum to $T.
Perl
The brute force way is to simply have a 3-nested loop and try all combinations of integers in @L, and build a list of the sets that sum to $T. But we can eliminate the inner loop entirely if we pre-build a hash of all numbers greater than a given number:
my @a = @_; my %Lh = map { shift @a => { map { $_ => 1 } @a } } 1..$#a;
Thus, if our input is (1, 2, 3), %Lh = (1 => { 2 => 1, 3 => 1 }, 2 => { 3 => 1 }, 3 => { }.
sub sum3 {
my $T = shift;
# Pre-build hash of numbers greater than $y for O(1) lookups in inner loop
my @a = @_; my %Lh = map { shift @a => { map { $_ => 1 } @a } } 1..$#a;
my @r;
while (my $x = shift) {
$Lh{$_}{ $T-$x-$_ } and push @r, [$x, $_, $T-$x-$_] for @_;
}
@r;
}
This solution is about twice as fast as the brute force method for small lists, and that gets even better with longer lists. Note the use of shift to remove $x from the array, so that we only check elements after $x. That’s the same idea I used to build %Lh.
Raku
In Raku, the solution couldn’t be much simpler:
sub sum3( Int $T, *@L ) {
@L.combinations(3).grep( $T == *.sum )
}
The combinations call will even ensure that the sets passed to grep will be in order, so we don’t need the optimization from the Perl solution, nor do we need to check for uniqueness or anything like that.
Task 2 › Colourful Numbers
Colourful numbers are numbers where the products of all consecutive digits are unique. For example, 987 is a colourful number because (9, 8, 7, 9 × 8, 8 × 7, 9 × 8 × 7) are all unique. 988 is not a colourful number because (9, 8, 8, 9 × 8, 8 × 8, 9 × 8 × 8) has a duplicate element (8).
For this problem, we are constrained to 3-digit colourful numbers, which makes things a little easier.
The algorithm here is essentially the problem description itself: check all 6 possible products (see above), and the number is colourful iff all 6 products are unique.
Perl
sub is_colourful3 {
my ($x, $y, $z) = split //, $_[0];
my %seen;
$seen{$_}++ and return 0 for $x, $y, $z, $x*$y, $y*$z, $x*$y*$z;
return 1;
}
With Perl, it was simpler to just multiply everything by hand and check it against a %seen hash. I could have used List::Util‘s uniq, I suppose, but there isn’t much difference, in practice.
Raku
sub colourful( Int $n where { 100 ≤ $n ≤ 999 } --> Bool ) {
my @D = $n.comb».Int;
!([0], [1], [2], [0,1], [1,2], [0,1,2]).map({ [*] @D[$_] }).repeated;
}
Here, I feed a list of arrays into map, each containing indicies of @D, which I multiply with the [*] reduction, and check for repeated elements. The return of the function is simply the boolean inverse of repeated.