RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest involved finding peak elements and more mucking about with linked lists.

You are given positive integer $N (>1).

Write a script to create an array of size $N with random unique elements between 1 and 50.

In the end it should print peak elements in the array, if found.

An array element is called peak if it is bigger than it’s [sic]
neighbour.

This is two problems: generate the list, find the peaks.

The examples suggest that (a) you don't need both neighbours to exist in order to be considered a peak, and (b) the output order is indeterminate. The latter is annoying when dealing with tests, so I changed it.

use List::Util qw(shuffle);
use Test::More tests => 2;

is_deeply(peaks(18, 45, 38, 25, 10, 7, 21, 6, 28, 48),
          [45, 21, 48],
          'peaks 1',
            );

is_deeply(peaks(47, 11, 32, 8, 1, 9, 39, 14, 36, 23),
          [47, 32, 39, 36],
          'peaks 2',
            );

To make random unique elements, the easiest approach is to start with one of each element, shuffle and cut.

sub genseq {
  my $n=shift;
  my @out=shuffle(1..50);
  splice @out,$n;
  return @out;
}

To find the peaks, we just iterate through the array looking for them.

sub peaks {
  my @list=@_;
  my @out;
  foreach my $n (0..$#list) {
    if (($n==0 || $list[$n]>$list[$n-1])
          &&
          ($n==$#list || $list[$n]>$list[$n+1])) {
      push @out,$list[$n];
    }
  }
  return \@out;
}

Raku can more readily shuffle and cut a random sequence, though the peak-finding is the same.

sub genseq($n) {
  return (1..50).pick($n);
}

And part 2 was to remove an element from a singly-linked list. But if I were going to be removing elements in Perl, I wouldn't use a singly-linked list in the first place. (In fact I use linked lists of any sort approximately never; the overhead isn't worth it.) Since in this case I would have to write a linked-list implementation before solving the problem, it's too much work to be fun.

So instead I'll talk about some recreational programming I did on Sunday. In the board game Rallyman GT you build racetracks out of tiles. The core box has 32 of these (not all different), and the four expansion boxes have further different tiles in them. So given a track layout (i.e. a list of tiles), which box or boxes do you need in order to build it?

A slight complication is introduced because some tiles are not unique: they occur in more than one expansion. So if my track uses one tile that's found in both box B and box C, and the rest are core box tiles, the output should be "core and B OR core and C".

So what I ended up doing was a binary filter. Using a bitmask I generate a list of box combinations: core only, core and A, core and B, core and A and B, etc. For each item in that list, I build an inventory of available tiles, and check whether the track can be built with them.

But I can take a short cut here. If the track could be built with core plus box A, I don't need to check any of the combinations of core-and-A with something else (both because I already know they'll work and more importantly because I don't want to list them in the final output). And because I'm using a bitmask, I can do that with logical-or: I or each previously-found solution with the new value, and if the result equals the new value, it's a strict superset of that old solution and can be ignored.

The only thing standing between this and generality is that it doesn't check for buildability with multiple instances of the same box. (Which is a thing you might well want to do if you adapted this for, say, Lego models.) Probably the easiest option would be to use the same pruning algorithm as before; though of course a track buildable with just the core box would produce "core box" and "core box #2" as valid options, so one would want to check that too. But I have an odd psychological block that complements my boardgaming completism: I want to have everything that's released for a game, but I also want to have only one of each of those things.