RogerBW's Blog

Perl Weekly Challenge 52: stepping numbers and game theory 13 April 2020

I’ve been doing the Perl Weekly Challenges. The latest involved some game theory.

Write a script to accept two numbers between 100 and 999. It should then print all Stepping Numbers between them. A number is called a stepping number if the adjacent digits have a difference of 1. For example, 456 is a stepping number but 129 is not.

I'm assuming for the sake of argument that it's always +1, rather than allowing the digit to decrease as well (e.g. 321).

Quite simple: break each candidate down into digits, then test each digit pair.

my @a=@ARGV;

if ($a[0]>$a[1]) {
  @a=($a[1],$a[0]);
}

foreach my $c ($a[0]..$a[1]) {
  my @d=split '',$c;
  my $v=1;
  foreach my $i (0..$#d-1) {
    if ($d[$i]+1 != $d[$i+1]) {
      $v=0;
      last;
    }
  }
  if ($v) {
    print "$c\n";
  }
}

Perl6 is slightly prettier.

my @a=@*ARGS;

for min(@*ARGS)..max(@*ARGS) -> $c {
  my @d=$c.comb(/./);
  my $v=1;
  for 0..@d.end-1 -> $i {
    if (@d[$i]+1 != @d[$i+1]) {
      $v=0;
      last;
    }
  }
  if ($v) {
    say $c;
  }
}

On the other hand, running the Perl5 version just took 0.533s for 100 single-threaded runs (with translation each time), while Perl6 took 36.679s to do the same thing.

With longer numbers I'd generate the stepping numbers rather than testing them.

Suppose there are following coins arranged on a table in a line in random order.

£1, 50p, 1p, 10p, 5p, 20p, £2, 2p

Suppose you are playing against the computer. Player can only pick one coin at a time from either ends. Find out the lucky winner, who has the larger amounts in total?

The first consideration is that these add up to less than £4, so the winner will be whoever takes the £2.

We can therefore ignore the values of the other coins and model the game with a pair of numbers: how many coins are to the left of the £2, and how many are to the right. So in the example above the game state is defined as (6,1).

Clearly if either of these numbers is 0 the active player can take the £2 and win.

If both of these numbers are 1, the active player must take one of the end coins, and the other player takes the £2 to win. If one number is 1 and the other is higher, the active player has to take the higher one to avoid leaving the game in an (n,0) state winnable by the other player.

If both of these numbers are 2, the first player takes either end coin to leave 2-1 or 1-2, the second player takes the other to leave 1-1 and avoid giving away a win, first must play 1-0 or 0-1, and second player wins.

If one of these numbers is above 2, the play doesn't make any difference as long as one avoids losing moves where possible. With 4-2, player A might play 3-2, B 3-1; or A might play 4-1, B 3-1. But from there the game progresses identically: A 2-1, B 1-1, A 1-0, B wins.

So what the algorithm does is to set things up for each possible game:

my $coins=8;

foreach my $a (0..$coins-1) {
  my @c=($a,$coins-1-$a);

Then cut down either side if it's higher than 2. Each step here is two player-turns.

  while (($c[0]>2 || $c[1]>2) && $c[0]>0 && $c[1]>0) {
    @c=sort @c;
    $c[1]-=2;
  }

Now we care about which side is playing. If either side has a number more than 1, they'll play that.

  my $toplay=0;
  while (($c[0]>1 || $c[1]>1) && $c[0]>0 && $c[1]>0) {
    @c=sort @c;
    $c[1]--;
    $toplay=1-$toplay;
  }

At this point the remaining possible states are 1-1, N-0, 0-N and 0-0. For everything except 1-1, the active player wins; otherwise it's the other player.

  @c=sort @c;
  unless ($c[0]==0) {
    $toplay=1-$toplay;
  }
  print "$a: $toplay wins\n";
}

Running this reveals that player 0 (i.e. the first player to choose) wins in every case.

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