# Advent of Code: 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 is`0`

. - 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 turns`5`

and`2`

. 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 is`0`

.

Given an input of `11,18,0,20,1,7,16`

, what will be the 2020^{th} 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 main.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 of`key 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 outer`Hash`

(denoted by the preceding`%`

sigil) and gives precedence to the second`Hash`

. 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 main.raku input.txt
639
# Part 2
$ raku main.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 a`copy`

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

of the`Pair`

objects, which is the`turn`

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