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


  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.

Add A Comment

Your Name
Your Email
Your Comment

Your submission will be ignored if any field is left blank, but your email address will not be displayed. Comments will be processed through markdown.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo geodata gin gurps gurps 101 harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread humour in brief avoid instrumented life kickstarter learn to play leaving earth linux lovecraftiana mecha men with beards museum mystery naval non-fiction one for the brow opera perl perl weekly challenge photography podcast politics powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1