laurent_r

These are some answers to the Week 104 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a couple of days (March 21, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Fusc Sequence

Write a script to generate first 50 members of FUSC Sequence. Please refer to OEIS for more information.

The sequence is 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)

Fusc Sequence in Raku

We just follow the definition and the implementation is straight forward. We first create a @fusc array and pre-populate it with values for 0 and 1. And, for subscripts larger than 1, we simply apply the formulas in a for loop over the 2..49 range:

use v6;

my @fusc = 0, 1;
for 2..49 -> $i {
    @fusc[$i] = $i %% 2 ?? @fusc[$i/2] !!
        @fusc[($i-1)/2] + @fusc[($i+1)/2];
}
say @fusc.join: " ";

This program displays the following output:

$ raku fusc.raku
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9

Fusc Sequence in Perl

Again, we simply follow the function definition. We first create a @fusc array and prepopulate it with values for 0 and 1. And, for subscripts larger than 1, we simply apply the formulas:

use strict;
use warnings;
use feature "say";

my @fusc = (0, 1);
for my $i (2..49) {
    $fusc[$i] = $i % 2 == 0 ? $fusc[$i/2] :
        $fusc[($i-1)/2] + $fusc[($i+1)/2];
}
say join " ", @fusc;

This Perl program outputs the same result as the Raku program:

$ perl fusc.pl
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9

Fusc Sequence in Scala

This is the same Raku or Perl program ported to Scala:

object Fusc extends App {
  import scala.collection.mutable.ArrayBuffer
  var fusc = ArrayBuffer[Int](0, 1)
  for (i <- 2 until 50)
    fusc += (if (i % 2 == 0) fusc(i / 2)
      else fusc((i - 1) / 2) + fusc((i + 1) / 2))

  println(fusc.mkString(" "))
}

This duly prints the same list of values as before:

0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9

Fusc Sequence in Python

Again the same program, ported to Python.

fusc = list(range(0, 50))
for i in range (2, 50):
    fusc[i] = fusc[int(i/2)] if i % 2 == 0 else fusc[int((i-1)/2)] + fusc[int((i+1)/2)]
print (fusc)

This program displays the following output:

$ python3 fusc.py [0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9]

Fusc Sequence in Ruby

Same algorithm in Ruby:

$fusc = Hash.new
$fusc[0] =  0
$fusc[1] =  1
$size    = 50

for i in 2 .. ($size-1) do
    if i % 2 == 0
        $fusc[i] = $fusc[i/2]
    else
        $fusc[i] = $fusc[(i-1)/2] + $fusc[(i+1)/2]
    end
end
for i in 0..($size-1) do
    print $fusc[i], " "
end
print "\n"

This duly prints the same sequence:

0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9

Fusc Sequence in C

I used to write C code almost daily, but that was up to about 22 years ago. Since then, I have occasionally written simple C code, but on average more like once or twice per year, probably even less in the recent period. So, I have forgotten a lot about the C language. For this simple task, however, I was able to put together the following program quite easily (it compiled and ran correctly immediately):

#include <stdio.h>

#define SIZE 50

int fusc[SIZE];

int main(void) {
    int fusc[SIZE];
    fusc[0] = 0;
    fusc[1] = 1;
    for (int i = 2; i < SIZE; i++) {
        fusc[i] = i % 2 ? 
            fusc[(i-1)/2 ] + fusc[(i+1)/2] :
            fusc[i/2];
    };
    for (int i = 0; i < SIZE; i++) {
        printf("%d ", fusc[i]);
    }
    printf("\n");
    return 0;
}

This also displays the same sequence:

$ ./fusc
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9

Fusc Sequence in Gembase

Gembase is a proprietary language originally developed in the 1980s and 1990s for accessing relational databases (Digital RDB, RMS on VMS, MS SQL Server, Sybase, and Oracle under Unix or Linux), developed initially by Ross Systems and then by CDC Software. It is quite similar in many respects to PL-SQL under Oracle. It is highly efficient for large databases, and it is very powerful and expressive in terms of database access and updates, report producing, ASCII menus, and so on. But, just as PL-SQL, it is quite poor as a general purpose programming languages.

Among its limitations and other low-expressive features, I can enumerate:

• The while loop is the only looping construct, no for loops, no next statement, no last statement, etc.; this leads to quite a bit of boiler-plate code to manage the loop variables;
• No hash or associative table (well, there are virtual tables, which are pretty rich and expressive, but not with the performance of hashes, far from that);
• Arrays are global variables and cannot be passed as a parameter to a function (although individual array elements can); also, there is no way to populate an array directly with a list of values;
• The overall syntax looks a bit obsolete (Pascal-like).

Clearly, I would not seriously use Gembase for solving such a problem (just as I would not use PL-SQL), as this leads to a lot of boring code. Raku and Perl are far far better. I undertook this task for the sole purpose of the challenge.

I guess that most people will be able to understand the overall syntax, you just need to know a few unusual things:

• Variable names start with a sigil, namely the # symbol;

• The language is generally not case-sensitive, it is quite common to use upper case for PROCEDUREFORM and ENDFORM to make the program structure more visible;

• & is the string concatenation operator;

This is the FUSC.DML Gembase program:

PROCEDURE_FORM FUSC
    #size = 50
    #fusc(0) = 0
    #fusc(1) = 1
    #i = 2
    while(#i < #size)
        if (mod (#i, 2))
            #fusc(#i) = #fusc((#i-1)/2) + #fusc((#i+1)/2)
        else
            #fusc(#i) = #fusc(#i/2)
        end_if
        #i = #i + 1
    end_while
    #string = ""
    #i = 0
    while (#i < #size)
        #string = #string & #fusc(#i) & " "
        #i = #i + 1
    end_while
    print(#string)
END_FORM

“.DML” files contain the Gembase source code, and are then compiled into “.DMC” files. This program displays the following output:

perform FUSC.DMC
Value is / 0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9 /

Fusc Sequence in AWK

AWK is really a programming language to process text files. It is a bit unnatural to use it for such computation, but it works rather well in this case. AWK is also a language that I haven’t been using since I started to be fluent with Perl, about 17 or 18 years ago. I was almost surprised to be able to write AWK code so easily after so many years:

BEGIN {
    fusc[0] = 0
    fusc[1] = 1
    printf "%s", "0 1 "
    for (i = 2; i < 50; i ++) {
        fusc[i] = i % 2 ? fusc[(i - 1)/2] + fusc[(i + 1)/2]:
            fusc[i/2]
        printf "%d ", fusc[i]
    }
    printf "%s\n", ""
}

Output:

$ awk -f fusc.awk empty-file
0 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 6 5 9 4 11 7 10 3 11 8 13 5 12 7 9 2 9

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

With these rules, to win, you need to end up with a situation where there are between 1 and 3 tokens on the heap. To make sure you arrive to that, you need, at the preceding step to leave a situation where there are four tokens, so that your opponent has no other choice than to you leave you with 1, 2, or 3 tokens. In order to reach a situation where you leave 4 tokens, you need to leave 8 tokens at the preceding move. and, similarly, there should be 12 tokens at the preceding step. More generally, any player that succeeds to leave a situation where the number of tokens can be evenly divided by 4 has a winning strategy. So, for any move, we should try to leave a situation where the number of tokens left is a multiple of 4, which can always be done, except when we’re given a situation where the number of tokens is a multiple of four.

If the two players know and apply the winning strategy, then the player that starts the game with 12 tokens is bound to lose.

NIM Game in Raku

NIM Dumb Machine in Raku

Nothing in the specification tells us that our program should follow a winning strategy. So, we will start with a dumb program that just picks a random number, except when there are less than 4 remaining token. I like that because, when playing against the machine, I can win most of the time, and I like to win.

use v6;

my $heap-count = 12;
my $max-picks = 3;

my $who-starts = prompt "Please say who starts (Y/I) ";
if $who-starts eq "Y" {
    $heap-count -= prompt "There are $heap-count tokens. How many tokens do you pick? "
}   
loop {
    if $heap-count <= $max-picks {
        say "I win by picking $heap-count tokens!";
        last;
    } else {
        my $pick = (1..$max-picks).pick;
        say "I picked $pick tokens.";
        $heap-count -= $pick;
        $heap-count -= prompt "$heap-count tokens left. How many tokens do you pick? ";
        if $heap-count == 0 {
            say "You won!";
            last;
        }
    }
}

These are two sample runs

$ raku nim-dumb-machine.raku
Please say who starts (Y/I) I
I picked 2 tokens.
10 tokens left. How many tokens do you pick? 2
I picked 1 tokens.
7 tokens left. How many tokens do you pick? 3
I picked 2 tokens.
2 tokens left. How many tokens do you pick? 2
You won!

$ raku nim-dumb-machine.raku
Please say who starts (Y/I) Y
There are 12 tokens. How many tokens do you pick? 2
I picked 1 tokens.
9 tokens left. How many tokens do you pick? 1
I picked 3 tokens.
5 tokens left. How many tokens do you pick? 1
I picked 1 tokens.
3 tokens left. How many tokens do you pick? 3
You won!

As you can see, I was able to win against the machine in both cases, because the machine strategy is very poor and mine absolutely brilliant.

In a real-life program, of course, the program should check that my moves are legal (an integer between 1 and 3). This is left as an exercise to the reader.

Of course, the machine can win if I play as stupidly as the machine:

$ raku nim-dumb-machine.raku
Please say who starts (Y/I) y
I picked 2 tokens.
10 tokens left. How many tokens do you pick? 3
I picked 2 tokens.
5 tokens left. How many tokens do you pick? 2
I win by picking 3 tokens!

Finally, when I start playing, the machine can sometimes also win (even if I play the winning strategy) if its random picks happen to be the correct ones each time through the game (which might happen in 3 to 4% of the games).

NIM Clever Machine in Raku

Of course, I like winning most of the time against the machine, but, on the other hand, programming a dumb machine is not terribly exciting. So let’s program a clever machine, i.e. a machine that knows how to apply the winning strategy.

In our NIM clever implementation, the machine tries to leave a situation where the number of tokens it leaves is a multiple of 4. For that, it simply needs to pick a number of tokens equal to the number of remaining tokens modulo 4 (if it is 0, this is a forbidden move, so then the machine picks a random number between 1 and 3).

use v6;

my $heap-count = 12;
my $max-picks = 3;

my $who-starts = prompt "Please say who starts (Y/I) ";
if $who-starts eq "Y" {
    $heap-count -= prompt "There are $heap-count tokens. How many tokens do you pick? "
}   
loop {
    my $pick = $heap-count % ($max-picks + 1);
    $pick = (1..$max-picks).pick if $pick == 0;
    say "I pick $pick items";
    $heap-count -= $pick;
    if $heap-count == 0 {
        say "I won!";
        last;
    }
    $heap-count -= prompt "$heap-count tokens left. How many tokens do you pick? ";
    if $heap-count == 0 {
        say "You won!";
        last;
    }
}

Now that the machine applies a winning strategy, I can only win when the machine is the first player:

$ raku nim-clever-machine.raku
Please say who starts (Y/I) I
I pick 3 items
9 tokens left. How many tokens do you pick? 1
I pick 3 items
5 tokens left. How many tokens do you pick? 1
I pick 3 items
1 tokens left. How many tokens do you pick? 1
You won!

$ raku nim-clever-machine.raku
Please say who starts (Y/I) Y
There are 12 tokens. How many tokens do you pick? 3
I pick 1 items
8 tokens left. How many tokens do you pick? 2
I pick 2 items
4 tokens left. How many tokens do you pick? 2
I pick 2 items
I won!

NIM Game in Perl

In Perl, we will only implement the clever machine version. So, the machine tries to leave a situation where the number of tokens left is a multiple of four, which it can do by choosing, when possible, a number of tokens equal to the number of token left modulo 4.

use strict;
use warnings;
use feature "say";

my $heap_count = 12;
my $max_picks = 3;
say "Please say who starts (Y/I) ";
my $who_starts = <STDIN>;
chomp $who_starts;
if ($who_starts eq "Y") {
    my $pick = pick_one_val ($heap_count);
    $heap_count -= $pick;
}
while (1) {
    my $pick = $heap_count % ($max_picks + 1);
    $pick = int(rand(3)) + 1 if ($pick == 0);
    say "I picked $pick tokens.";
    $heap_count -= $pick;
    if ($heap_count == 0) {
        say "I won!";
        last;
    }
    $pick = pick_one_val ($heap_count);
    $heap_count -= $pick;
    if ($heap_count == 0) {
        say "You won!";
        last;
    }
}
sub pick_one_val {
    my $count = shift;
    say "There are $count tokens left. How many tokens do you pick? ";
    my $pick = <STDIN>;
    chomp $pick;
    return $pick;
}

As above, I should acknowledge that in a real-life program, the program should (at least) check that my moves are legal (an integer between 1 and 3). This is easy and left as an exercise to the reader.

Two sample runs:

$ perl nim.pl
Please say who starts (Y/I)
Y
There are 12 tokens left. How many tokens do you pick?
2
I picked 2 tokens.
There are 8 tokens left. How many tokens do you pick?
1
I picked 3 tokens.
There are 4 tokens left. How many tokens do you pick?
1
I picked 3 tokens.
I won!


$ perl nim.pl
Please say who starts (Y/I)
I
I picked 3 tokens.
There are 9 tokens left. How many tokens do you pick?
1
I picked 2 tokens.
There are 6 tokens left. How many tokens do you pick?
2
I picked 2 tokens.
There are 2 tokens left. How many tokens do you pick?
2
You won!

NIM Game in Python

Again, the program should (at least) check that my moves are legal (an integer between 1 and 3). This is easy and left as an exercise to the reader.

heap_count = 12
max_picks = 3
def pick_one_val(count):
    pick = input("There are " + str(count) + " tokens left. How many tokens do you pick? ");
    return pick

who_starts = input("Please say who starts (Y/I):")
if who_starts == "Y":
    pick = pick_one_val(heap_count)
    heap_count = heap_count - int(pick)
while True:
    pick = heap_count % (max_picks + 1)
    if pick == 0:
        pick = 1
    print("I picked ", str(pick), " tokens.")
    heap_count = heap_count - int(pick)
    if heap_count == 0:
        print("I won!");
        break
    pick = pick_one_val(heap_count)
    heap_count = heap_count - int(pick)
    if heap_count == 0:
        print ("You won!")
        break

Sample executions:

$ python3 nim.py
Please say who starts (Y/I):Y
There are 12 tokens left. How many tokens do you pick? 2
I picked  2  tokens.
There are 8 tokens left. How many tokens do you pick? 2
I picked  2  tokens.
There are 4 tokens left. How many tokens do you pick? 2
I picked  2  tokens.
I won!

$ python3 nim.py
Please say who starts (Y/I):I
I picked  1  tokens.
There are 11 tokens left. How many tokens do you pick? 3
I picked  1  tokens.
There are 7 tokens left. How many tokens do you pick? 3
I picked  1  tokens.
There are 3 tokens left. How many tokens do you pick? 3
You won!

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, March 28, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.