Advent of Code: Year 2020, Day 9

Today we have a classic sliding window problem. But, instead of the traditional iterative approach, we take a recursive approach.

The Problem

Part 1

After helping our seatmate fix his Game Boy yesterday, we find ourselves bored on the plane. Why not pass the time with a little mid-air hacking?

We hook our computer up to the seat-back entertainment center, but it is protected by the eXchange-Masking Addition System (XMAS), which is a cipher with a documented weakness.

XMAS starts by sending us 25 numbers (a “preamble”). The 26th number should be the sum of two numbers in the preamble. The 27th number should be the sum of its previous 25 numbers, and so on. Here is an example with a preamble of size 5:

35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576

We can see how the pattern works here:

• 40 is the sum of 15 and 25
• 62 is the sum of 15 and 47
• 55 is the sum of 15 and 40
• etc.

The first step in attacking the weakness of the cipher is that exactly one number doesn’t follow the pattern. In this case 127 is not the sum of any numbers in the previous 5 (95, 102, 117, 150, 182). Our job is to find the invalid number in the XMAS cipher.

Solution

See below for explanation and any implementation-specific comments.

sub find-invalid(@list, \$window-start = 0, \$window-size = 25) {                               # 
my \$window-end = \$window-start + \$window-size - 1;
my \$target-number = @list[\$window-end + 1];
my @preamble-combinations = @list[\$window-start..\$window-end].combinations(2).map(*.sum); # 
if \$target-number ∈ @preamble-combinations {
find-invalid(@list, \$window-start + 1);
} else {
\$target-number;
}
}

sub MAIN(\$file) {
say find-invalid(\$file.IO.lines.map(*.Int));
}

This runs as such:

\$ raku day-09.raku input.txt
31161678

Explanation

First, we pull all of our numbers into a list and turn them into integers. Once we’ve done that, we pass the list to find-invalid, which will find the sliding window and target value we are looking for (@list[0..24] and @list in the first iteration). We then find all possible combinations in that 25-item list (via .combinations(2)) and sum each pair (vis .map(*.sum). If the target is in the list of sums, it is valid, and we go to the next sliding window. If it is not, we found our invalid term and return.

1. I added a parameter for \$window-size here because I had a feeling it would change in part two. It did not, but I left it in here to give an idea of my thought process.
2. I am trying to get more consistent in using dot operators (like .sum) rather than mixing paradigms. With that being said, .map([+] *) didn’t work here to begin with; it wanted me to do something like .map(-> @pair { [+] @pair }). I think it was interpreting the * as a multiplication operator instead of a Whatever star, so it was getting confused. All the more reason to use dot operators, I guess!

Part 2

The second step of finding the weakness relies on the invalid number found above.

We need to find a contiguous set of numbers (size two or greater) in the input that add up to our invalid input. Once we have found that contiguous range, we need to add the minimum and maximum numbers in the range; that is our encryption weakness.

Solution

See below for explanation and any implementation-specific comments.

sub find-invalid(@list, \$window-start = 0, \$window-size = 25) {
my \$window-end = \$window-start + \$window-size - 1;
my \$target-number = @list[\$window-end + 1];
my @preamble-combinations = @list[\$window-start..\$window-end].combinations(2).map(*.sum);
if \$target-number ∈ @preamble-combinations {
find-invalid(@list, \$window-start + 1);
} else {
\$target-number;
}
}

sub find-contiguous-range(@list, \$target, \$start = 0, \$end = 1) {
my @range = @list[\$start..\$end];
given @range.sum {
when * < \$target  { find-contiguous-range(@list, \$target, \$start, \$end + 1) }       # 
when * == \$target { @range }
when * > \$target  { find-contiguous-range(@list, \$target, \$start + 1, \$start + 2) }
}
}

sub MAIN(\$file, Bool :\$p2 = False) {
my @input = \$file.IO.lines.map(*.Int);
my \$invalid = find-invalid(@input);
if \$p2 {
my @contiguous-range = find-contiguous-range(@input.reverse, \$invalid); # 
say @contiguous-range.min + @contiguous-range.max;
} else {
say \$invalid;
}
}

This runs as such:

# Part 1
\$ raku day-09.raku input.txt
31161678

# Part 2
\$ raku day-09.raku --p2 input.txt
5453868

Explanation

our find-invalid subroutine stays the same, but we now assign the output of it to a variable. If the user is running part one, we print and exit. If the user is running part two, we recursively search the list for a range that adds up to the invalid number. We use the following criteria:

2. If the sum of the window is less than the target, increase it by one and try again
3. If the sum of the window is the target, return the range
4. If the sum of the window is greater than the target, move the start of the window by one, resize to a window of size two and start again