Perl Weekly Challenge 104
This week had some fun topics like recursion, memoization, and IO/data validation!
Task 1: FUSC Sequence
Write a script to generate first 50 members of FUSC
Sequence. Please refer to OEIS for more information.
The sequence defined as below:
fusc(0) = 0
fusc(1) = 1
for n > 1:
when n is even: fusc(n) = fusc(n / 2),
when n is odd: fusc(n) = fusc((n-1)/2) + fusc((n+1)/2)
Solution
See below for explanation and any implementation-specific comments.
use experimental :cached; # [1]
sub fusc(Int(Rat) $n) is cached returns Int { # [2]
given $n {
when 0 { 0 }
when 1 { 1 }
when * %% 2 { fusc($n / 2) } # [3]
default { fusc(($n - 1) / 2) + fusc(($n + 1) / 2) } # [4]
}
}
sub MAIN(Int $terms = 50) {
say (^$terms).map(&fusc); # [4]
}
This program runs as such:
$ raku ch-1.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)
Explanation
I feel like this is pretty straight forward, and aligns well to the definition of the FUSC sequence. When we look at $n
, we run through the following logic:
- Is it 0? Return 0.
- Is it 1? Return 1.
- Is it even? Return
fusc($n / 2)
. - Otherwise, return
fusc(($n - 1) / 2) + fusc(($n + 1) / 2)
The function recurses until it ends up in one of the two stopping conditions (0 or 1). So obviously fusc(50)
is going to go through fusc(49)
, fusc(48)
, etc. See below for how we make this efficient.
Specific comments
- Caching in Raku is an experimental feature, so we have to import it (and add the
is cached
trait to our subroutine). The basic idea is thatfusc($n)
is always the same value, so once we calculate it once, we can just look it up later. Adding this trait essentially adds a hash behind the scenes that checks iffusc($n)
already exists. If it does, it just returns that value, otherwise, it will actually calculate the value and store it in the hash before returning. - Notice the function signature takes
Int(Rat)
. This means that this function will accept eitherInt
orRat
(Rational number) types, but it will coerce the input to anInt
. The reason for this is that division in Raku will generate aRat
type, even for something like2 / 1
. So we need to convert it to anInt
on the recursive calls. This saves use from having to writefusc(($n / 2).Int)
. - Raku has a special “is divisible by” operator. So instead of saying
$n % 2 == 0
, we can say$n %% 2
. Also notice that in thegiven
block, we have to use the “whatever star” (*
) to do this operation; this is because we can’t smartmatch against%% 2
, so we need to be more explicit. - Remember when passing a function as an argument (in this case to
map
), it has a special sigil –&
.
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
Solution
See below for explanation and any implementation-specific comments.
# Formats a message defined as plural to be singular if $n == 1
sub format(Str $message, Int $n) returns Str {
$n == 1 ?? $message.trans(['are', 'tokens'] => ['is', 'token']) !! $message; # [1]
}
sub challenge(Int $n) {
my $remaining = $n;
# Defined within the challenge sub because it references $remaining
sub default-prompt returns Any {
prompt(format("There are $remaining tokens. How many would you like to pick up? (1, 2, 3) ", $remaining)); # [2]
}
my $input = default-prompt;
my $most-recent-move;
while $remaining > 0 {
given $input {
when 1|2|3 {
if $input > $remaining {
$input = prompt("There are only $remaining tokens left. Please enter a valid number ")
} else {
say format("You take $input tokens", $input);
$remaining -= $input;
$most-recent-move = 'You';
last if $remaining == 0;
# If there are only 3 or less tokens, take all of them. Otherwise, take a random number between 1 and 3
my $bot-move = $remaining ~~ 1|2|3 ?? $remaining !! (1..3).pick;
say format("The computer takes $bot-move tokens", $bot-move);
$remaining -= $bot-move;
$most-recent-move = 'Computer';
last if $remaining == 0;
$input = default-prompt;
}
}
default { $input = prompt('Please enter 1, 2, or 3 ') }
}
}
say $most-recent-move eq 'Computer' ?? 'The computer wins!' !! 'You win!'; # [3]
}
sub MAIN(Int $n where $n > 0 = 12) { # [4]
challenge($n);
}
This program runs as such:
$ raku ch-2.raku
There are 12 tokens. How many would you like to pick up? (1, 2, 3) 3
You take 3 tokens
The computer takes 3 tokens
There are 6 tokens. How many would you like to pick up? (1, 2, 3) 2
You take 2 tokens
The computer takes 3 tokens
There is 1 token. How many would you like to pick up? (1, 2, 3) 1
You take 1 token
You win!
Explanation
This task is basically an exercise in IO (prompt
) and data validation (did I get what I expect?). We follow the following steps:
- Ask the user to give us a number (1, 2, or 3).
- Did they give it to us? Move on to step 2.
- Otherwise, keep asking for a valid input (doesn’t matter if they gave us an invalid number, a string, etc.).
- Do a special check to see if their number is higher than the remaining tokens (only happens when there are 3 or fewer tokens). If so, keep prompting them for a valid input.
- Now that we know we have valid input, decrement
$remaining
to reflect the number of token the user took. - If there are 0 tokens left, exit the loop and print that the user won.
- Otherwise, there are tokens left, and it is the computer’s turn. Our bot is semi-smart, so if there are 3 or fewer tokens take all of them (and win). Otherwise, take a random valid number of tokens.
- If there are 0 tokens left, exit the loop and print that th computer won.
- Finally, if there are still tokens left, repeat steps 1-6 until there are 0 tokens left.
Specific Comments
- This is simply a helper function, so we can write all of our prompts like
"There are $n tokens remaining"
and they will get properly formatted if$n
is 1. This is very specific to this question, obviously, but it is useful.trans
basically just translates allare
instances tois
and alltokens
instances totoken
. - You’ll notice a few things about this subroutine. First, we don’t have to define it with parentheses if it doesn’t take any arguments. Second, it returns
Any
because we don’t know what we are going to get from the user. Third, it is defined insidechallenge
because it is acting as a closure, meaning it references variables defined outside itself (in this case,$remaining
). - Raku is kind of strange in that if you want to do string equality you have to use
eq
instead of==
. - This function signature specifies that it takes an
Int
that is greater than 0, and if it is not provided, it defaults to 12.
Final Thoughts
Raku gives us some cool tools to make these challenges easier. The given
syntax was especially helpful in both of these challenges (and in others)!