I’ve been doing the Perl Weekly
Challenges. The
latest
involved summing Fibonacci numbers and looking through a grid for
neighbours.
TASK #1 › Fibonacci Sum
Write a script to find out all possible combination of Fibonacci
Numbers required to get $N
on addition.
You are NOT allowed to repeat a number. Print 0 if none found.
In its original version this was basically the same problem as last
week's #1, but with a different set of candidate numbers (Fibonacci
rather the prime). With that other problem in mind, this falls into
two parts: generate a set of Fibonacci numbers, and enumerate the
combinations to test for the right total.
(I'm reasonably sure that every positive integer is the sum of one or
more Fibonacci numbers.)
I used basically the same algorithm as the generator in each case:
initialise the list with (1,1), then push more entries equal to the
sum of the last two elements until we equal or exceed the target. Then
remove the first element of the list because we don't repeat elements.
Perl:
my @p=(1,1);
while ($p[-1] < $n) {
push @p,$p[-1]+$p[-2];
}
shift @p;
Raku:
my @p=(1,1);
while (@p[@p.end] < $n) {
push @p,@p[@p.end]+@p[@p.end-1];
}
shift @p;
Python:
p=[1,1]
while (p[-1]<=n):
p.append(p[-1]+p[-2])
del p[0]
(I could have used a Python deque
again but for just the one
deletion it didn't seem worth it.)
For the enumeration I decided not to bark myself when I have a
perfectly good dog available. Perl:
use Algorithm::Combinatorics qw(combinations);
my @o;
foreach my $l (1..scalar @p) {
foreach my $comb (combinations(\@p,$l)) {
if (sum(@{$comb})==$n) {
push @o,$comb;
}
}
}
return \@o;
Raku (basically the same one-liner as last time, because its
combinations
is the only one of these three languages that can take
a range of lengths):
my @o=grep {sum(@($_))==$n}, @p.combinations(1..@p.elems);
return @o;
And Python, more like Perl:
o=list()
for l in range (1,len(p)):
for c in combinations(p,l):
if (sum(c)==n):
o.append(c)
return o
TASK #2 › Lonely X
You are given m x n character matrix consists of O and X only.
Write a script to count the total number of X surrounded by O only.
Print 0 if none found.
(The examples make it clear that a diagonally adjacent X counts as
non-lonely.)
This is basically nested enumerations. Each language works essentially
the same way: iterate over each row, iterate over each column. If we
have an "X", iterate over delta-row and delta-column values of
(-1,0,-1) to examine all eight neighbours (skipping the case where
both deltas are 0). If any of these cells is an "X", mark the cell
under consideration as non-isolated. Return the count of isolated "X"
cells.
So here's the Raku version, because all three look much the same apart
from details of syntax.
sub nx(@n) {
my $mr=@n.end;
my $mc=@n[0].end;
my $isol=0;
for 0..$mr -> $r {
for 0..$mc -> $c {
unless (@n[$r][$c] eq 'X') {
next;
}
my $isolated=1;
for (-1,0,1) -> $dr {
if ($r+$dr < 0 || $r+$dr > $mr) {
next;
}
for (-1,0,1) -> $dc {
if ($dc==0 && $dr==0) {
next;
}
if ($c+$dc < 0 || $c+$dc > $mc) {
next;
}
if (@n[$r+$dr][$c+$dc] eq 'X') {
$isolated=0;
last;
}
}
}
if ($isolated) {
$isol++;
}
}
}
return $isol;
}
Full code on github