RogerBW's Blog

Perl Weekly Challenge 104: FUSC NIM 16 March 2021

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.


  1. Posted by RogerBW at 02:35pm on 22 March 2021

    Other people's part 1:

    Well, it looks as if Raku's given can do more than simply matching: someone used a when * %% 2 which is a bit punctuation-heavy for my taste but definitely more useful than a straight equality test.

    One approach was to take the numbers from the OEIS citation, but that would have been a bit boring.

    And of course a non-recursive approach is simply to build up the sequence from the start, since calculating fusc(n) only relies on lower values of n.

    Other people's part 2:

    Well, I thought the obvious approach was to solve the game first, then write the bot to implement a perfect player, but another popular algorithm was "win if you have 1, 2 or 3, otherwise play at random". On the other hand I had no interest in writing the interactive front-end.

    It might have been interesting to have a formal spec and pit people's play functions against each other… though probably with a more complex game than this.

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 advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript 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 ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge 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