This FUSCing Nim Game Is Fixed!

Wherein we learn that where you end up in life sometimes depends on where you started. No matter what the other other person says, either, because they may well be in on the scam.

THE WEEKLY CHALLENGE – PERL & RAKU #104


episode one:
“Well FUSC You Too, Dijkstra”


Task 1

FUSC Sequence

Submitted by: Mohammad S Anwar

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)

Method

The function as stated is defined recursively, so that is how we’ll proceed. I note that this is not strictly necessary, as we could just compile a list of values and immediately compute from the previously calculated values, but instead we’ll arrive at pretty much the same place by memoizing our function.

With the recursive implementation of this algorithm drawing on previously computed values, as the numbers get larger there will be a certain amount of redundant calculation as the fractional components get reused at, roughly, each doubling of the index. Unlike the Fibonacci sequence, however, where both of each values’ immediate predecessors are required to to do every computation, the FUSC sequence’s self-referentiality is considerably sparser. No matter the actual expense incurred, though, waste is waste and both sequences benefit from memoization, or establishing a reference record of values as they are constructed should those values be required again.

Of course whatever the rate of expansion, the complexity does grow exponentially, if not immediately, cripplingly so. Planting a counter within the code reveals considerably more work being done as the sequence lengths get larger. For this short sequence of 50 values the gain might be insignificant, but larger values show the speedup both obvious and accelerating.

   0..10000  values:    3873034  vs  15000   function calls   258x speedup
   0..100000 values:  149830797  vs  150000  function calls   999x speedup
PERL 5 SOLUTION

I think the whole argument of necessity is made moot by the ease of implementation. The Memoize module is core, and memoizing the fusc() function is as easy as adding two lines, to add the module and tell it which subroutines to watch. If the fusc() routine gets called twice with the same parameter, a cached value will be returned instead of recalculating the result.

use warnings;
use strict;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
use Memoize;

memoize qw(fusc);

sub fusc ($n) {
    return undef if $n < 0;
    return 0 if $n == 0;
    return 1 if $n == 1;
    
    $n % 2 && return fusc(($n-1)/2) + fusc(($n+1)/2);
    
    return fusc($n/2);
}

my @out;
for ( 0..49 ) {
    push @out, fusc($_);
}

say join ', ', @out;
raku solution
MAIN: {

    multi sub fusc(0) { 0 }
    multi sub fusc(1) { 1 }
    multi sub fusc($n) {
        
        state %f;
        state $loop++;
        return if $loop > 20000;
            
        %f{ $n } //= $n %% 2 ?? fusc($n/2)
                             !! fusc( ($n-1)/2 ) + fusc( ($n+1)/2 );
    }

    say "$_  {fusc($_) }" for ^4 ;

}
Python solution
import functools

@functools.lru_cache(maxsize=1024)

def fusc(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
               
    if n % 2:
        return fusc( (n-1)/2 ) + fusc( (n+1)/2 )
    
    return fusc(n/2)


for n in range (1,11):
    print( fusc(n) )

episode two:
“Pick A Card, Any Card”


task 2

NIM Game

Submitted by: Mohammad S Anwar

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:

  1. You have 12 tokens
  2. Each player can pick 1, 2 or 3 tokens at a time
  3. The player who picks the last token wins the game

Method

Just to make it a wee bit more complex, I implemented this one misère, where the objective is to leave the opponent in an untenable position. In this version the person talking the last token loses.

analysis

I had a feeling I could just look this one up, but as often decided to mull it over on my own. One night while falling asleep I worked everything through.

I had suspected that with enough tokens, the small range allowed in moves would be amplified enough to produce complex behavior in the gameplay. Perhaps without such technical working through I was expected to think this, as the facts prove otherwise.

It’s a set-up. A con. Whoever moves first, if the role is played right, will win. Every time. And the gameplay to win can be reduced to a few easily stated rules.

gameplay

Lets call the two players You and your Opponent.

Let’s walk winning backwards from the end: your Opponent draws one token, and loses. The pot at that point holds one token; any other number and the Opponent would draw one or more and not lose. The turn before, the pot must therefore contain 2-4 tokens, so You can draw 1-3 and leave your Opponent with 1.

For this to happen, you must make it so in the previous move your Opponent has 5 tokens. If that is so no matter the move made, You will be left with the required 2-4 tokens to win.

Regressing an additional step, to leave your opponent with 5 tokens you must have between 6-8 tokens, and to ensure that in the previous step your opponent must have 9 tokens.

When starting from 12 take 3 tokens, leaving your opponent with 9. You will then always be able to win. At every move make sure your opponent is left with either 1, 5, or 9 tokens, which is always possible when taking the first move from 12 tokens.

the con

There is a list of fatal token quantities that, when a player recieves a pot containing that many tokens, the player has lost. The objective is to deliver one’s opponent a quantity from that list.

The list is all multiples of 4, plus 1:

1, 5, 9, 13, 17, 21 …

If the game is played with a quantity of tokens from this list, the first player will lose. Any other quantity, and the first player will win. So the con is to play with a ‘random’ number of tokens. If the quantity is from the list, insist the other player draw first that turn “to be fair”. Careful play can always redirect the opponent into a losing position, so unless the opponent also plays perfectly, advantage can be wrested at any point before the end.

If the opponent understands the perfect strategy, it’s unlikely they will agree to play.

PERL 5 SOLUTION

A $pot variable is established, which is reduced as draws are made against it.

The computer will play a perfect strategy, which involves determining a target value for the pot to be delivered to the opponent. This target is the largest multiple of 4, with 1 added, that is less than or equal to the pot. The draw then is the pot minus the target. If the ideal draw is worked out to be 0, a random number between 1 and 3 tokens is drawn. This last behavior is arbitrary, as the computer is in the losing position and there is no good move. However a random draw will avoid the repetion of a 1, or any other defined draw; this infusion of randomness might help to keep the opponent from guessing a winning strategy.

The logic portion of the game wasn’t very complex, so I focused more on the interaction, trying to make it as natural as I could.

To this end I brought in Lingua::EN::Inflexion, and once it was there inflected everything in sight. I also realized that there may not always be be three tokens to take, and implemented a little operation to select the correct phrase at the end of the game. You might say I went to town on the whole thing.

Another cute trick I pulled out was if you give the computer bogus input, it becomes less polite. Notice how on being forced to reiterate itself, “There are now 9 tokens on the pot” becomes “There are 9 tokens on the pot”, removing the “now”. Once the pot size changes it will be reinstated.

I think the increasingly stern tone against the player forcibly highlights the inescapable plight of the their situation.

    There are 12 tokens on the pot. Please draw 1, 2 or 3 tokens.
    2
    You drew two tokens.
    There are now 10 tokens in the pot. Computer will draw next.
    Computer draws one token.
    There are now 9 tokens on the pot. Please draw 1, 2 or 3 tokens.
    4
    Please take 1, 2 or 3 tokens.
    There are 9 tokens on the pot. Please draw 1, 2 or 3 tokens.
    3
    You drew three tokens.
    There are now 6 tokens in the pot. Computer will draw next.
    Computer draws one token.
    There are now 5 tokens on the pot. Please draw 1, 2 or 3 tokens.
    1
    You drew one token.
    There are now 4 tokens in the pot. Computer will draw next.
    Computer draws three tokens.
    There is now 1 token on the pot. Please draw the token.
    0
    Please take the token.
    There is 1 token on the pot. Please draw the token.
    no
    Please take the token.
    There is 1 token on the pot. Please draw the token.
    1
    You drew one token.
    Player loses.

Here’s the code:

use warnings;
use strict;
use feature ":5.26";
use Lingua::EN::Inflexion;


my $pot = 12;

my $now = '';

while (-scam) {
    
    ## player draw phase
    my $request = 
        $pot > 2 ? "1, 2 or 3 tokens."
                 : $pot > 1 ? "1 or 2 tokens."
                            : "the token.";

    say inflect(
        "<#d:$pot>There <V:is>$now $pot <N:token> on the pot. Please draw $request"
    );
    my $draw = <STDIN>;
    if ($draw !~ /^[123]$/ or $draw > $pot) {
        say "Please take $request";
        $now = '';
        redo;
    }
    
    say inflect(
        "You drew <#wnc:$draw> <N:token>."
    );
    
    $pot -= $draw;
    if ( $pot < 1 ) {
        say "Player loses.";
        exit;
    }
    

    ## computer draw phase
    $now = " now";
    
    say inflect(
        "<#d:$pot>
        There <V:is>$now $pot <N:token> in the pot. Computer will draw next."
    );

    my $target = int(($pot-1)/4) * 4 + 1;           
    
    $draw = $pot - $target;
    $draw ||= int rand(3) + 1;
    $draw = 1 if $draw > $pot;
    
    say inflect( 
        "Computer draws <#wnc:$draw> <N:token>."
    );
    
    $pot -= $draw;
    if ( $pot < 1 ) {
        say "Computer loses.";
        exit;
    }
}


The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://perlweeklychallenge.org