Advent of Code: Year 2020, Day 15
Even with how short and sweet today’s solution is, I had to rewrite it between parts one and two after hitting the maximum recursion depth. So we’ve got one functional, recursive solution and one imperative, iterative solution!
The Problem
Part 1
While we wait for our next flight, we decide to call the elves back at the North Pole. They’re playing a memory game that they want us to join.
In this game, the players take turns saying numbers. They begin by taking turns reading from a list of starting numbers (your puzzle input). Then, each turn consists of considering the most recently spoken number:
- If that was the first time the number has been spoken, the current player says
0
. - Otherwise, the number had been spoken before; the current player announces how many turns apart the number is from when it was previously spoken.
Here is an example with input 0,3,6
:
- Turn 1: The 1st number spoken is a starting number,
0
. - Turn 2: The 2nd number spoken is a starting number,
3
. - Turn 3: The 3rd number spoken is a starting number,
6
. - Turn 4: Now, consider the last number spoken,
6
. Since that was the first time the number had been spoken, the 4th number spoken is0
. - Turn 5: Next, again consider the last number spoken,
0
. Since it had been spoken before, the next number to speak is the difference between the turn number when it was last spoken (the previous turn, 4) and the turn number of the time it was most recently spoken before then (turn 1). Thus, the 5th number spoken is 4 - 1,3
. - Turn 6: The last number spoken,
3
had also been spoken before, most recently on turns5
and2
. So, the 6th number spoken is 5 - 2,3
. - Turn 7: Since 3 was just spoken twice in a row, and the last two turns are 1 turn apart, the 7th number spoken is
1
. - Turn 8: Since 1 is new, the 8th number spoken is
0
. - Turn 9:
0
was last spoken on turns 8 and 4, so the 9th number spoken is the difference between them,4
. - Turn 10:
4
is new, so the 10th number spoken is0
.
Given an input of 11,18,0,20,1,7,16
, what will be the 2020th number?
Solution
See below for explanation and any implementation-specific comments.
sub play-game(%numbers, $turn, $number, $target-turn) {
if $turn == $target-turn {
$number;
} else {
my $next-number = %numbers{$number}:exists ?? $turn - %numbers{$number} !! 0; # [1]
play-game(%(|%numbers, |($number => $turn)), $turn + 1, $next-number, $target-turn); # [2]
}
}
sub MAIN($file, Bool :$p2 = False) {
my %initial = $file.IO.slurp.split(',').kv.map(-> $key, $value { $value => $key + 1 } ).Hash;
say play-game(%initial, %initial.elems + 1, 0, 2020);
}
This runs as such:
$ raku day-15.raku input.txt
639
Explanation
So, in MAIN
we first pull everything from our input into a Hash
with the keys being the number that was said by the elves, and the value being the turn it was said on. Then we pass that to play-game
with four parameters:
- The
Hash
itself - The turn we are starting on (in the case of our input, 8)
- The next number in the sequence (since our input is so small, we can hard-code this to 0)
- The number in the sequence we are hoping to find (2020)
play-game
will recursively do the following (until it hits turn 2020):
- If we have seen this number find the difference between this turn, and the turn it was last said on, otherwise
0
- Update the
%numbers
variable with the new number/turn pair
That’s it!
Specific Comments
- The
:exists
tag here is something called an adverb in Raku. It is the equivalent ofkey in dictionary
in Python. - There is some special syntax on this line for merging hashes without mutating the original hashes. The slip character (
|
) unpacks the two hashes into an outerHash
(denoted by the preceding%
sigil) and gives precedence to the secondHash
. Here is what that means in simple terms:
my %a = (a => 1, b => 2); # {a => 1, b => 2}
my %b = (b => 3, c => 4); # {b => 3, c => 4}
my %c = %(|%a, |%b); # {a => 1, b => 3, c => 4}
Part 2
The elves are impressed with our memory skills, so they up the ante! What is the 30 millionth term in the sequence?
Solution
See below for explanation and any implementation-specific comments.
sub play-game-recursive(%numbers, $turn, $number, $target-turn) {
if $turn == $target-turn {
$number;
} else {
my $next-turn = %numbers{$number}:exists ?? $turn - %numbers{$number} !! 0;
play-game-recursive(
%(|%numbers, |($number => $turn)),
$turn + 1,
$next-turn,
$target-turn
);
}
}
sub play-game-iterative(%numbers is copy, $target-turn) { # [1]
my $last-item = %numbers.pairs.sort({ $^a.value cmp $^b.value })[*-1]; # [2]
for (%numbers.elems^..$target-turn) -> $turn { # [3]
my $new-item = %numbers{$last-item}:exists ?? ($turn - 1) - %numbers{$last-item} !! 0;
%numbers{$last-item} = $turn - 1;
$last-item = $new-item;
}
$last-item;
}
sub MAIN($file, Bool :$p2 = False) {
my %initial = $file.IO.slurp.split(',').kv.map(-> $key, $value { $value => $key + 1 } ).Hash;
my $last-turn = $p2 ?? 30_000_000 !! 2020; # [4]
say play-game-iterative(%initial, $last-turn);
}
This runs as such:
# Part 1
$ raku day-15.raku input.txt
639
# Part 2
$ raku day-15.raku --p2 input.txt
266
Explanation
So the first thing you’ll notice is I refactored play-game
to be called play-game-recursive
; this is not used anywhere, it was simply left in to show the progression of the code.
MAIN
does the same thing, but changes the $last-turn
value based on if it is $p2
or not, but then passes the input to an iterative solution. The iterative solution basically just keeps the last-said number in memory and checks if it exists in our %number
Hash
. If so, it finds the difference between the last turn, and the last time it was said and that is our next number, otherwise it is 0
. We then add that new number to %numbers
and keep going.
For 30 million iterations this solution is still pretty slow, but it works where the recursive solution just dies.
Specific Comments
- The
is copy
parameter tells the subroutine that it is receiving acopy
of%numbers
and it is safe to mutate it. - Since a
Hash
does not guarantee order, we need to implement a custom sort algorithm. In this case, we are sorting by thevalue
of thePair
objects, which is theturn
in our scenario. The$^a
syntax is special here in that it assigns and uses a variable all at once. This is the equivalent of.sort(-> $a, $b { $a.value cmp $b.value })
. - The
^..
syntax means it is a range exclusive of the bottom end but inclusive of the top; the corresponding math notation is(a, b]
. - Raku (like many languages) allows us to put underscores in numeric literals to make them easier to read.
Final Thoughts
This is obviously a time when recursion is not the best idea. It’s important to be able to distinguish what can be done recursively and what must be done iteratively, even if the recursive solution seems more “natural.”