RogerBW's Blog

Perl Weekly Challenge 117: Missing Possibilities 16 June 2021

I’ve been doing the Perl Weekly Challenges. The latest involved file analysis and combinatorial explosion. (Note that this is open until 20 June 2021.)

TASK #1 › Missing Row

You are given text file with rows numbered 1-15 in random order but there is a catch one row in missing in the file.

11, Line Eleven [etc.]

Write a script to find the missing row number.

I assume that any row which starts with a number is the row of that number. The filename is the parameter to my function. This basically happens in two stages:

  1. read each line, find the number, list that as "a number which is not missing"
  2. look for each positive integer in that list of non-missing numbers, return for the first one which isn't there.

Here's the Raku:

sub mr($n) {
  my $f=SetHash.new;
  my $fh=open :r,$n or die "Cant open file\n";
  for $fh.lines {
    .chomp;
    if (/^(<[0..9]>+)/) {
      $f{$0+0}=1;
    }
  }
  my $a=1;
  while (1) {
    unless ($f{$a}:exists) {
      return $a;
    }
    $a++;
  }
}

You could probably do something clever with first but I didn't.

This version finds the first missing number from 1 up, however large the file; a more sophisticated but less general approach would be to assume that the missing number isn't the first or the last, and look for gaps between the found numbers. Or just start with a set of 1..15 and delete rows as observed.

TASK #2 › Find Possible Paths

You are given size of a triangle.

Write a script to find all possible paths from top to the bottom right corner.

In each step, we can either move horizontally to the right (H), or move downwards to the left (L) or right (R). BONUS: Try if it can handle triangle of size 10 or 20.

Since I'm required to find the paths, not just return a count of them, I'll use my standard non-recursive search pattern. (I looked at ways of mutating the always-valid solution of R×n, but it seemed too much like work.)

Each entry in chain is a tuple of (string of path so far, x position, y position). (Except in Raku where I couldn't get it to do a list of lists, so I used a list of hashes. But this is the first time I've explicitly used the "tuple" type in Rust.) My x and y are slightly unexpected, though. Here's my coordinate system for n=2:

(First time I've used a diagram in a PWC blog post…)

Each valid path starts at (0,0) and ends at (0,4). Each node can generate up to three new path entries. For the y value reachable from the current node, I work out the maximum possible x (the minimum is always 0), and add the path entries that will remain within those bounds. Here's the Ruby version:

def fpp(n)
  o=Set.new
  chain=[["",0,0]]

lim is the maximum y value, which goes up by 4 per +1 except that n=1 has a maximum y of 2.

  lim=(n-1)*4
  if n==1 then
    lim=2
  end
  while chain.length() > 0
    p=chain.pop

These are just convenience aliases.

    x=p[1]
    y=p[2]

If we have a valid solution, add it to the solution set.

    if y >= lim then
      o.add(p[0])
    else

Otherwise, work out the maximum x for the next row.

      mxx=y+1
      if y >= n then
        mxx=lim-y-1
      end

And then for each direction, H, R and L, see if it fits, then generate the path and add it. (There's a bug here - when I'm going to y+2 I should really use a different mxx value because it's one row further down. But it works anyway, because an R-path can only exist where an L-path is possible.)

      0.upto(2) do |txi|
        tx=x-1+txi
        if tx>=0 && tx<=mxx then
          if txi==0 then
            chain.push([p[0]+'H',x-1,y+1])
          elsif txi==1 then
            chain.push([p[0]+'R',x,y+2])
          else
            chain.push([p[0]+'L',x+1,y+1])
          end
        end
      end
    end
  end

Then get the result set, and sort it (because I also sort the test-case answers for easy verification).

  return o.to_a.sort
end

The number of possible paths for each size is in the OEIS, except for the first term, and that gives a formula to generate it. (Interesting that that's every second value of another sequence which gives the number of routes across a square grid allowing diagonal movement.)

sub fpp {
  my $n=shift;
  my $s=0;
  foreach my $i (0..$n*2) {
    $s+=ncr(2*$n+1,$i+1)*ncr(2*$n+$i,$i);
  }
  $s/=(2*$n+1);
  return $s;
}

(ncr is the number of r-combinations to be made out of n, the usual n!/r!(n-r)! for which the actual functions are quite standard or may be available in libraries. I used Memoize a lot.)

Full code on github.


  1. Posted by RogerBW at 03:56pm on 24 June 2021

    Part 1: one can also just add the values rather than keeping them individually, then work out the difference between the observed total and sum(1..15). For a much larger file this would be cheaper in storage, and probably rather faster. Every blogger used either that approach or something like mine above.

    I do like having sets (i.e. valueless hashes) in the languages other than Perl; lots of what I do with hashes involves making a list of things unique, and they're a cleaner way of achieving that.

    Part 2: there are neater coordinate systems, but broadly this comes down to a choice between recursion and exhaustive search. (And I don't mind recursion, but it's more work to debug and often resource-intensive with all the extra stack frames or equivalent; with my buffer-array approach, either pulling off the bottom for BFS or off the top for DFS, all that's getting stored is the actual necessary state.)

    One blogger did take the string-mutating approach, and realised that you can replace each R with an L plus an H, in any position and order except that you can't start with H or end with L. But I suspect this will be slower. Another approach was to find all the LH paths and then substitute Rs.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

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 aviation base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris 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 genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread in brief avoid instrumented life julie enfield kickstarter learn to play leaving earth linux liquor lovecraftiana mecha men with beards museum music mystery naval non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript 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 ruby rust 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