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.