# 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.

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 `\$n`th root of the number `\$k` can usually be expressed as the number ​`\$k` raised to the `1/N`th 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)
#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
Katie, Katie, bo-batie
Bonana-fanna fo-fatie
Fee fi mo-matie)
Katie!

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

\$ ./raku name-game.raku
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
Katie

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

\$ perl  name-game.pl
Anna

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

\$ perl  name-game.pl
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.

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
``````

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
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
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
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
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.