I’ve been doing the Perl Weekly
Challenges. The
latest
involved the Stern-Brocot sequence (which Dijkstra named "fusc") and a
variant of Nim. (Note that this is open until 21 March 2021.)
TASK #1 › FUSC Sequence
Write a script to generate first 50 members of FUSC Sequence
.
Please refer to OEIS for more
information.
The sequence defined as below:
fusc(0) = 0
fusc(1) = 1
for n > 1:
when n is even: fusc(n) = fusc(n / 2),
when n is odd: fusc(n) = fusc((n-1)/2) + fusc((n+1)/2)
Well, that looks like a fairly straightforward bit of recursion. To
make it more interesting, let's cache the results on first
calculation.
In Perl this is trivial with a core module, without having to
accommodate it in the function:
use Memoize;
memoize('fusc');
sub fusc {
my $n=shift;
if ($n==0) {
return 0;
} elsif ($n==1) {
return 1;
} elsif ($n%2 == 0) {
return fusc($n/2);
} else {
my $h=($n-1)/2;
return fusc($h)+fusc($h+1);
}
}
sub fuscseq {
my $m=shift;
return [map {fusc($_)} (0..$m-1)];
}
The actual calculation stays the same from one language to the next, so
I shan't repeat it. Raku has a Memoize
module but it's non-core, so I
used a state
variable (persistent between function invocations).
sub fusc($n) {
state %cache;
if (%cache{$n}:exists) {
return %cache{$n};
}
my $m;
# [...] calculate $m here as above [...]
%cache{$n}=$m;
return $m;
}
Python lets me treat functions as first-class objects and redefine
them. So here's my memoised-function factory:
def memoize(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
The @memoize
decoration is equivalent to putting
fusc=memoize(fusc)
after the function definition.
@memoize
def fusc(n):
if n==0:
return 0
elif n==1:
return 1
elif n%2==0:
return fusc(n/2)
else:
h=(n-1)/2
return fusc(h)+fusc(h+1)
In Ruby again it's an external library, so I used a global.
$cache=Hash.new
def fusc(n)
if $cache.has_key?(n) then
return $cache[n]
end
# [...] calculate m here as above [...]
$cache[n]=m
return m
end
and in Rust I used the Raku/Ruby approach of explicitly cacheing the
results, but put the whole thing in a class in order to get a
persistent variable.
pub struct Fusc {
cache: HashMap<u32,u32>
}
impl Fusc {
pub fn new() -> Fusc {
Fusc {
cache: HashMap::new()
}
}
pub fn fusc(&mut self,n: u32) -> u32 {
if self.cache.contains_key(&n) {
return *self.cache.get(&n).unwrap();
}
let m: u32;
// [...] calculate m here as above [...]
self.cache.insert(n,m);
return m;
}
}
TASK #2 › NIM Game
Write a script to simulate the NIM Game.
It is played between 2 players. For the purpose of this task, let
assume you play against the machine.
There are 3 simple rules to follow:
a) You have 12 tokens
b) Each player can pick 1, 2 or 3 tokens at a time
c) The player who picks the last token wins the game
Well. It's a Nim game. The more usual sorts involve multiple heaps
where the player can pick up as many tokens as they like but only from
one heap, and often the last player to pick is the loser – which is
not as symmetrical a change as one might assume. But anyway.
This version is even more readily solved than most variants of Nim.
The game's state is just the number of tokens remaining, and could be
represented as a track numbered 12 to 0.
- If I start my turn at state 1, 2 or 3, I take that number and win.
- If I start my turn at state 4, I must end it at state 1, 2 or 3, so
you will win.
- If I start my turn at state 5, 6 or 7, I can choose to end it at
state 4, so I will win.
- If I start my turn at state 8, I must end it at state 5, 6 or 7, so
you will win.
- If I start my turn at state 9, 10 or 11, I can choose to end it at
state 8, so I will win.
- If I start my turn at state 12, I must end it at state 9, 10 or 11,
so you will win.
If it's your turn and the heap mod 4 is non-zero, you play to get it
to zero. If heap mod 4 is zero at the start of your turn, it doesn't
matter what you play because you've lost. Therefore the second player
wins if the starting heap modulo 4 is 0, and the first player wins
otherwise. (So a valid solution to this challenge could just print
"Player 2 wins".)
I'm not really interested in interaction so I wrote this as a system
that would play itself. play(n)
gives the play when the heap is of
size n
, and game(h)
runs a game with a heap of size h. Clearly
this could be expanded to interactivity if you could find a human
bored enough to want to play.
I expanded things a little by producing a turn-by-turn log, and
accepting different starting heap sizes. From the losing state, the
algorithm plays randomly.
sub game {
my $heap=shift || 12;
my @players=qw(Alice Bob);
my $a=0;
while ($heap>0) {
my $n=play($heap);
$heap-=$n;
warn "$players[$a] takes $n leaving $heap.\n";
if ($heap==0) {
warn "$players[$a] wins.\n";
last;
}
$a++;
$a %= 2;
}
return $a;
}
sub play {
my $state=shift;
my $m=$state % 4;
if ($m==0) {
return int(rand()*3)+1;
} else {
return $m;
}
}
For Raku I used multi-dispatch to get a default parameter value.
multi game {
return game(12);
}
multi game($hh) {
# (etc.)
Python has default parameters.
def game(hh=12):
So does Ruby.
def game(hh=12)
But not Rust, and here I just gave up on getting the function to work
both with and without a parameter. (Not, to be fair, that I've ever
particularly wanted this in the real world.) Also Rust's random number
generator is in an external library and I didn't fancy making this
into a proper Rust project, so I just used the Unix process ID mod 3
instead.
Full code on
github.