RogerBW's Blog

Perl Weekly Challenge 71: peak elements (and Rallyman tracks) 28 July 2020

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.

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 advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech 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 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 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 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir 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 scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge 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