RogerBW's Blog

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.