March 2021 Archives

Perl Weekly Challenge 105: Nth Root and The Name Game

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

Spoiler Alert: This weekly challenge deadline is due in a couple of days (March 28, 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: Nth Root

You are given positive numbers $N and $k.

Write a script to find out the $Nth root of $k. For more information, please take a look at the wiki page.

Example:

Input: $N = 5, $k = 248832
Output: 12

Input: $N = 5, $k = 34
Output: 2.02

The $nth root of the number $k can usually be expressed as the number ​$k raised to the 1/Nth power: $k ** (1/$n), with $n > 0.

Nth Root in Raku

We just implement the formula above and compute the first to the tenth root of the input value:

use v6;

my $input = @*ARGS[0] // 248832;
for 1..10 -> $i {
    printf "%2i\t%10.3f\n", $i, $input ** (1/$i);
}

Running this script with no parameter yields the results for the defgault value:

$ raku root.raku
 1      248832.000
 2         498.831
 3          62.898
 4          22.335
 5          12.000
 6           7.931
 7           5.900
 8           4.726
 9           3.977
10           3.464

And providing another integer as a command-line parameter displays the following output:

$ raku root.raku 400
 1         400.000
 2          20.000
 3           7.368
 4           4.472
 5           3.314
 6           2.714
 7           2.354
 8           2.115
 9           1.946
10           1.821

Nth Root in Perl

This a direct port to Perl of the above Raku program:

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

my $input = $ARGV[0] // 248832;
for my $i (1..10) {
    printf "%2i\t%10.3f\n", $i, $input ** (1/$i);
}

Output with the default value:

 $ perl root.pl
 1      248832.000
 2         498.831
 3          62.898
 4          22.335
 5          12.000
 6           7.931
 7           5.900
 8           4.726
 9           3.977
10           3.464

Output with a command-line parameter:

$ perl root.pl 400
 1         400.000
 2          20.000
 3           7.368
 4           4.472
 5           3.314
 6           2.714
 7           2.354
 8           2.115
 9           1.946
10           1.821

Nth Root in Scala

Again, a simple port to Scala:

object root extends App {
  val in: Int = if (args.size == 1) args(0).toInt else 248832
  for (i <- 1 to 10) {
    val root = scala.math.pow(in, (1 / i.toDouble))
    println(f"$i%2d $root%10.3f")
  }
}

Note the in Scala, a division between two integers yields the Euclidean division (or integer division) so that 1 / i would return 0 for all integer values from 2 to 10. That is why the program converts i to a double before performing the division. Replacing 1 by 1.0 would also do the trick.

Output:

 1 248832.000
 2    498.831
 3     62.898
 4     22.335
 5     12.000
 6      7.931
 7      5.900
 8      4.726
 9      3.977
10      3.464

Nth Root in Python

Port of the same program to Python:

#!/usr/bin/python

import sys
input = int(sys.argv[1]) if len(sys.argv) > 1 else 248832
for i in range(1, 11):
    root = input ** (1/i)
    print('{:2d}'.format(i), "   ", root)

Output with default value::

$ python3 root.py
 1     248832.0                                                                                                         
 2     498.8306325798367                                                                                                
 3     62.89779346101351                                                                                                
 4     22.33451661845039                                                                                                
 5     12.000000000000002                                                                                               
 6     7.930812913000375                                                                                                
 7     5.899887726224536                                                                                                
 8     4.725940818339814                                                                                                
 9     3.976904267210367                                                                                                
10     3.464101615137755

Please note that my real output is single-spaced. I have no idea why my mark-down file produces double-space rendering here and in two more entries below.

Output with a command-line parameter:

$ python3 root.py 400
 1     400.0
 2     20.0
 3     7.368062997280773
 4     4.47213595499958
 5     3.3144540173399872
 6     2.7144176165949063
 7     2.353546893650252
 8     2.114742526881128
 9     1.9458877175763887
10     1.8205642030260802

Note that I haven’t tried to format the roots: either Python is bad at formatting numbers, or I did not understand its formatting system. Note that I’ll not try very hard to pretty-print the results in the coming guest languages.

Nth Root in Other Languages

Some languages don’t have the ** exponentiation operator. In some cases, the exponenciation operator may be ^. In others, you might have to use a built-in or an imported pow function. Or possibly to use logarithms (like in bc). Or yet some other construct. Also, in a number of the languages examples below, I did not try to get argument from the command-lin, but preferred to hard code the input value. In some cases, I did not try to pretty-print the results.

In the C Programming Language

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define DEFAULT_IN 248832

int main(int argc, char *argv[]) {
    printf("%s\n", argv[1]);
    int in = argc == 2 ? atoi( argv[1]) : DEFAULT_IN;
    for (int i = 1; i <= 10; i++) {
        printf("%2i     %10.3f \n", i, pow (in, 1.0/i));
    };
    return 0;
}

Output:

$ a.out
 1     248832.000                                                                                                       
 2        498.831                                                                                                       
 3         62.898                                                                                                       
 4         22.335                                                                                                       
 5         12.000                                                                                                       
 6          7.931                                                                                                       
 7          5.900                                                                                                       
 8          4.726                                                                                                       
 9          3.977                                                                                                       
10          3.464    

$ a.out 10000
 1      10000.000                                                                                                       
 2        100.000                                                                                                       
 3         21.544                                                                                                       
 4         10.000                                                                                                       
 5          6.310                                                                                                       
 6          4.642                                                                                                       
 7          3.728                                                                                                       
 8          3.162                                                                                                       
 9          2.783                                                                                                       
10          2.512

In the D Programming Language

After C, comes D (just as C came after B, which itself came after BCPL). More seriously, D was designed as a successor to C (although D is object oriented and might better qualified as a successor to C++),same ideas and simular syntax, but supposedly more robust.

import std.stdio;
import std.math;

void main() {
    auto input = 248832;
    for (int i = 1; i <= 8; i++) {
        double root = pow(input, 1.0/i);
        writeln(i, "     ", root);
    }
}

Output:

1     248832
2     498.831
3     62.8978
4     22.3345
5     12
6     7.93081
7     5.89989
8     4.72594

In Awk

# run e.g. as: $ awk -v input=120 -f root.awk
BEGIN {
    for (i = 1; i <= 10; i++) {
        printf "%2i    ¨%10.3f\n", i, input ** (1/i);
    }
}

Output:

$ awk -v input=248832 -f root.awk
 1    ¨248832.000
 2    ¨   498.831
 3    ¨    62.898
 4    ¨    22.335
 5    ¨    12.000
 6    ¨     7.931
 7    ¨     5.900
 8    ¨     4.726
 9    ¨     3.977
10    ¨     3.464

We don’t really need to store the awk script in a file and can use an awk one-liner:

$ awk -v input=248832 ' BEGIN { for (i = 1; i <= 6; i++) {
                print i, "\t", input ** (1/i); } } '
1        248832
2        498.831
3        62.8978
4        22.3345
5        12
6        7.93081

In Bc

The Unix/Linux bc utility is aimed at performing simple numeric calculations, so it should presumably be ideal for our numeric tasK. However, its name stands for “basic calculator,” and it is so basic that it doesn’t have an exponentiation operator for non-integer exponents. We can work around that issue, though. Using the -l command line option enables a math library that provides the l natural logarithm and e exponential functions. The nth root of k can be computed as the exponential of the logarithm of k divided by n, which is written e(l(k)/n) in the bc syntax. We can run our program as a one-liner:

$ echo  'a = 248832; for(i=1;i<=5;i++) { print i; print "   "; print e(l(a)/i); print "\n"}' | bc -l
1   248831.99999999999999787313
2   498.83063257983666053377
3   62.89779346101351857080
4   22.33451661845039037442
5   11.99999999999999999988

Of course, using logarithm and exponential reduces somewhat the accuracy.

In Gembase

Gembase is a little known proprietary language for database access. You may find some information about it on my blog post of last week. It should be quite easy to understand this code once you know that variable names start with a “sigil”: #.

PROCEDURE_FORM ROOT (#in)
    if (#in = "")
        #input = 248832
    else
        #input = #in
    end_if
    #i = 1
    while(#i <= 10)
        #root = #input ^ (1.0/#i)
        error /text_only (mask("!-@@", #i) & mask("!-@@@@@@@@@@0.@@@", #root))
        #i = #i + 1
    end_while
END_FORM

Output:

 1     248832.000
 2        498.831
 3         62.898
 4         22.335
 5         12.000
 6          7.931
 7          5.900
 8          4.726
 9          3.977
10          3.464

In Ruby

$input = 248832
for i in 1 .. 8 do
    root = $input ** (1.0/i)
    puts "#{i}    #{root}"
end
print "\n"

Output:

1    248832.0
2    498.8306325798367
3    62.89779346101351
4    22.33451661845039
5    12.000000000000002
6    7.930812913000375
7    5.899887726224536
8    4.725940818339814

In Dart

import 'dart:math';

void main() {
  var input = 248832;
  for (int i = 1; i <= 8; i++) {
    var root = pow(input, (1/i));
    print("$i    $root");
  }
}

Output:

1    248832
2    498.8306325798367
3    62.89779346101351
4    22.33451661845039
5    12.000000000000002
6    7.930812913000375
7    5.899887726224536
8    4.725940818339814

In Visual Basic

Module VBModule
    Sub Main()
        for i as Integer = 1 to 5
            Console.WriteLine(248832 ^ (1/i))
        next
    End Sub
End Module

Output:

248832                                                                                                                  
498.830632579837                                                                                                        
62.8977934610135                                                                                                        
22.3345166184504                                                                                                        
12

In Kotlin

fun main() {
    val input = 248832;
    for (i in 1..10) {
        val root = "%12.3f".format(Math.pow(input * 1.0, 1.0/i))
        val formatted_i = "%2d".format(i)
        println("$formatted_i  $root")
    }
}

Output:

 1    248832.000
 2       498.831
 3        62.898
 4        22.335
 5        12.000
 6         7.931
 7         5.900
 8         4.726
 9         3.977
10         3.464

In Lua

input = 248832
for i = 1, 10 do
    print (string.format("%2d  %10.3f", i, input ^ (1/i)))
end

Output:

 1  248832.000
 2     498.831
 3      62.898
 4      22.335
 5      12.000
 6       7.931
 7       5.900
 8       4.726
 9       3.977
10       3.464

In Go

package main
import (
    "fmt"
    "math"
)
func main() {
    const input = 248832

    for i := 1; i <= 10; i++ {
        fmt.Printf("%2d\t%10.3f\n", i, math.Pow(input, 1.0/float64(i)))
    }
}

Output:

 1  248832.000
 2     498.831
 3      62.898
 4      22.335
 5      12.000
 6       7.931
 7       5.900
 8       4.726
 9       3.977
10       3.464

In Java

class Main {  
    public static void main(String args[]) { 
        double input = Double.parseDouble(args[0]);
        for (int i = 1; i <= 10; i++) {
            double root = Math.pow(input, 1.0 / i );
            System.out.format("%2d   %10.3f\n", i, root); 
        } 
    }  
}

Output:

 1   248832.000
 2      498.831
 3       62.898
 4       22.335
 5       12.000
 6        7.931
 7        5.900
 8        4.726
 9        3.977
10        3.464

In Nim

Nim uses Python-like code indentation.

import math

var input = 248832.0
for i in 1..8: 
  var root = pow(input, 1.0 / float(i))
  echo i, "   ", root

Output:

1   248832.0
2   498.8306325798367
3   62.89779346101351
4   22.33451661845039
5   12.0
6   7.930812913000375
7   5.899887726224536
8   4.725940818339814

In Julia

input = 248832
for i = 1:10
    @printf("%2d  %10.3f\n", i, input ^ (1/i) )
end

Output:

$ julia root.jl
 1  248832.000
 2     498.831
 3      62.898
 4      22.335
 5      12.000
 6       7.931
 7       5.900
 8       4.726
 9       3.977
10       3.464

In Rust

fn main() {
    let input = 248832f64;
    for i in 1..11 {
        let root = input.powf(1.0/i as f64);
        println!("{:2}   {:10.3}", i,  root);
    }
}

Output:

 1   248832.000
 2      498.831
 3       62.898
 4       22.335
 5       12.000
 6        7.931
 7        5.900
 8        4.726
 9        3.977
10        3.464

Task 2: The Name Game

You are given a $name.

Write a script to display the lyrics to the Shirley Ellis song The Name Game. Please checkout the wiki page for more information.

Example:

Input: $name = "Katie"
Output:

    Katie, Katie, bo-batie,
    Bonana-fanna fo-fatie
    Fee fi mo-matie
    Katie!

The Name Game is apparently very well known in the United States, but I haven’t lived there and the rules are not entirely clear to me, so I’ll base my programs on my best understanding of those rules.

The Name Game in Raku

We’ll use a here-doc for producing the lyrics of the song, with variable interpolation. So, the only difficulty is to populate these variables with the right values in accordance with rules laid out in the Wikipedia page referred to above.

use v6;

my $name = prompt "Please enter the name: ";
my $vowels = Set.new(<a e i o u>);
my $consonants = Set.new('a'..'z') (-) $vowels;
my ($start, $suffix) = ($0, $1) if $name ~~ /(\w)(\w+)/;

my @y;
if $start.lc (elem) $consonants {
    @y[0] = $start eq 'B' ?? "bo-$suffix" !! "bo-b$suffix";
    @y[1] = $start eq 'F' ?? "fo-$suffix" !! "fo-f$suffix";
    @y[2] = $start eq 'M' ?? "mo-$suffix" !! "mo-m$suffix";
} else {
    @y = "bo-$suffix", "fo-$suffix", "mo-$suffix";
}

say qq:to/END/; 
    $name, $name, @y[0]
    Bonana-fanna @y[1]
    Fee fi @y[2])
    $name!
    END

Examples of output:

$ ./raku name-game.raku
Please enter the name: Katie
Katie, Katie, bo-batie
Bonana-fanna fo-fatie
Fee fi mo-matie)
Katie!

$ ./raku name-game.raku
Please enter the name: Billy
Billy, Billy, bo-illy
Bonana-fanna fo-filly
Fee fi mo-milly)
Billy!

$ ./raku name-game.raku
Please enter the name: Anna
Anna, Anna, bo-nna
Bonana-fanna fo-nna
Fee fi mo-nna)
Anna!

The Name Game in Perl

This a port to Perl of the Raku program above:

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

say "Please enter the name: ";
my $name = <STDIN>;
chomp $name;
my %vowels = map { $_ => 1} qw<a e i o u>;
my ($start, $suffix) = ($1, $2) if $name =~ /(\w)(\w+)/;
my @y;
if (exists $vowels{lc $start}) {
    @y = ("bo-$suffix", "fo-$suffix", "mo-$suffix");
} else {
    $y[0] = $start eq 'B' ? "bo-$suffix" : "bo-b$suffix";
    $y[1] = $start eq 'F' ? "fo-$suffix" : "fo-f$suffix";
    $y[2] = $start eq 'M' ? "mo-$suffix" : "mo-m$suffix";
}
say "\n", <<~EOF;
    $name, $name, $y[0]
    Bonana-fanna $y[1]
    Fee fi $y[2])
    $name!
    EOF

Examples of output:

$ perl  name-game.pl
Please enter the name:
Katie

Katie, Katie, bo-batie
Bonana-fanna fo-fatie
Fee fi mo-matie)
Katie!

$ perl  name-game.pl
Please enter the name:
Anna

Anna, Anna, bo-nna
Bonana-fanna fo-nna
Fee fi mo-nna)
Anna!

$ perl  name-game.pl
Please enter the name:
Billy

Billy, Billy, bo-illy
Bonana-fanna fo-filly
Fee fi mo-milly)
Billy!

The Name Game in Scala

object nameGame extends App {
  val in: String = if (args.size == 1) args(0) else "Katie"
  val start =  in.substring(0, 1)
  val suffix = in.substring(1)
  val vowels = Map("A" -> 1, "E" -> 1, "I" -> 1, "O" -> 1, "U" -> 1)

  val bosuffix = if (start == 'B' || vowels.contains(start)) 
    s"bo-$suffix"  else s"bo-b$suffix"
  val fosuffix = if (start == 'F' || vowels.contains(start)) 
    s"fo-$suffix"  else s"fo-f$suffix"
  val mosuffix = if (start == 'M' || vowels.contains(start)) 
    s"mo-$suffix" else s"mo-m$suffix"

  println(s"$in, $in, $bosuffix")
  println(s"Bonana-fanna $fosuffix")
  println(s"Fee fi $mosuffix")
  println(s"$in!")
}

Example output:

Katie, Katie, bo-batie
Bonana-fanna fo-fatie
Fee fi mo-matie
Katie!

The Name Game in Python

import sys
input = sys.argv[1] if len(sys.argv) > 1 else "Katie"
start = input[0]
suffix = input[1:]
vowels = { "A", "E", "I", "O", "U"}

bosuffix = f'bo-{suffix}' if (start == 'B' or start in vowels) else f'bo-b{suffix}'
fosuffix = f'fo-{suffix}' if (start == 'F' or start in vowels) else f'fo-f{suffix}'
mosuffix = f'mo-{suffix}' if (start == 'M' or start in vowels) else f'mo-m{suffix}'

print(f'{input}, {input}, {bosuffix}')
print(f'Bonana-fanna {fosuffix}')
print(f'Fee fi {mosuffix}')
print(f'{input}!')

Output:

$ python3 name-game.py
Katie, Katie, bo-batie
Bonana-fanna fo-fatie
Fee fi mo-matie
Katie!

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, April 4, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.

Perl Weekly Challenge 104: Fusc Sequence and NIM Game

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.

About laurent_r

user-pic I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.