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