RogerBW's Blog

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.