# RogerBW's Blog

Perl Weekly Challenge 77: Fibonacci Sum and Lonely X 09 September 2020

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
``````

(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.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

1. Posted by RogerBW at 11:50am on 14 September 2020

Looking at other people's answers, now that the challenge has ended, I see that nobody took the prettier approach to part 2 of scanning the entire array and tagging each cell that had at least one neighbour-X. This would probably have been slower, but one could use Game-of-Life optimisations on it. Raku also has the `X` cross-product operator, which is quite a nifty alternative to deeply nested loops.

I do like the way Raku lets you define a Fibonacci sequence as `my \$fibonacci := (1, 1, * + * ... Inf);` (thanks to Arne Sommer and Andrew Shitov for this one). I don't have a lot of use for it but it's very elegant.