# Advent of Code: Year 2020, Day 14

Today was much less math-heavy than yesterday, although we will dive into an algorithm that would make it faster. However, I did do this problem more imperatively than functionally; read on to see why!

## The Problem

### Part 1

As we approach the mainland, the captain once again asks for our help; our computer system is not compatible with the port’s docking software. We quickly see that the docking parameters are not being properly initialized. The docking program is using a strange bitmask software, and we don’t have the proper chip to decode it. Luckily, we can emulate it.

Our input looks like the following:

```
mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0
```

This defines a 36-bit bitmask and multiple memory addresses to update with bitmasked values. Here is how the bitmask is applied:

```
value: 000000000000000000000000000000001011 (decimal 11)
mask: XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
result: 000000000000000000000000000001001001 (decimal 73)
```

First, a value (in this case 11) is converted to binary and then the mask is applied by using the mask character if it’s a `1`

or `0`

and the original character if it is an `X`

. As you can see, this gives us the number 73 represented as binary. We then store `73`

at memory address 8 and move on to the next instruction.

Once all instructions have been applied, what is the sum of values in memory?

#### Solution

See below for explanation and any implementation-specific comments.

```
sub apply-mask($mask, $num) {
my @mask-list = $mask.comb;
my @num-list = $num.base(2).comb;
while @num-list.elems < @mask-list.elems {
@num-list.unshift(0); # [1]
}
my @masked = gather {
for @mask-list Z @num-list -> ($mask-digit, $digit) { # [2]
take $mask-digit eq 'X' ?? $digit !! $mask-digit;
}
}
@masked.join.parse-base(2);
}
sub extract-values($line) {
my $address = $line.match(/\[(<digit>+)\]/)[0].Int;
my $value = $line.split(' = ')[1].Int;
($address, $value)
}
sub MAIN($file) {
my $mask;
my @mem;
for $file.IO.lines -> $line {
if $line.starts-with('mask') {
$mask = $line.split(' = ')[1];
} else {
my ($address, $value) = extract-values($line);
@mem[$address] = apply-mask($mask, $value);
}
}
say @mem.sum; # [3]
}
```

This runs as such:

```
$ raku day-14.raku input.txt
17934269678453
```

#### Explanation

So, first we define 2 helper functions:

`apply-mask`

takes a`mask`

string and an integer, then converts it to binary and iteratively works through the strings to apply the mask to the integer, then it casts the string back to a base-10 integer.`extract-values`

simply parse the memory address and value to be masked from the input line.

in `MAIN`

you can see how imperatively we did this. First, we define a mutable mask^{*} and memory register, then start iterating through the lines. If we hit a mask, overwrite our current one, otherwise extract the values, apply the mask, and add it to our memory register. Finally, just sum all the masked values up!

^{*}One thing about our input that was not super clear to me in the instructions is that we are given *multiple* masks that we have to apply to the next N values (until we hit the next mask).

##### Specific Comments

`unshift`

adds values to the beginning of an array. Raku has no equivalent of Python’s`zip_longest`

function, so we have to make sure the input lists are exactly the same length.`Z`

is Raku’s zip operator. So`(1, 2, 3) Z (4, 5, 6)`

yields`((1, 4), (2, 5), (3, 6))`

.- Notice we never initialized a size of this array. Raku doesn’t require us to! It will implicitly fill in any unused slots with
`Any`

, which is one of its undefined types.`Any`

is skipped during the sum, so it really is just as simple as saying`@mem.sum`

.

### Part 2

After all that business, we realize the docking computer must be running version 2 of the software while we are still on version 1. 🤦🏻

V2 of the software applies the bitmask to memory *addresses*, not the *values*. Additionally, `X`

now means “floating” (`0 or 1`

), so we have to update both possible addresses. Here is an example:

```
address: 000000000000000000000000000000101010 (decimal 42)
mask: 000000000000000000000000000000X1001X
result: 000000000000000000000000000000X1101X
```

After the mask, we are left with *four* addresses to update:

```
000000000000000000000000000000011010 (decimal 26)
000000000000000000000000000000011011 (decimal 27)
000000000000000000000000000000111010 (decimal 58)
000000000000000000000000000000111011 (decimal 59)
```

Using V2, what is the sum of the memory addresses after initialization?

#### Solution

See below for explanation and any implementation-specific comments.

```
sub find-all-masks(@zipped, $pointer = 0, @prefix = ()) { # [1]
if $pointer == @zipped.elems {
@prefix.join.parse-base(2);
} else {
my ($mask-digit, $digit) = @zipped[$pointer];
given $mask-digit {
when '0' { find-all-masks(@zipped, $pointer + 1, (|@prefix, $digit)) } # [2]
when '1' { find-all-masks(@zipped, $pointer + 1, (|@prefix, $mask-digit)) }
when 'X' {
|(
find-all-masks(@zipped, $pointer + 1, (|@prefix, '0')),
find-all-masks(@zipped, $pointer + 1, (|@prefix, '1'))
)
}
}
}
}
sub apply-mask($mask, $num, Bool $part-two = False) {
my @mask-list = $mask.comb;
my @num-list = $num.base(2).comb;
while @num-list.elems < @mask-list.elems {
@num-list.unshift(0);
}
if $part-two {
find-all-masks(@mask-list Z @num-list);
} else {
my @masked = gather {
for @mask-list Z @num-list -> ($mask-digit, $digit) {
take $mask-digit eq 'X' ?? $digit !! $mask-digit;
}
}
@masked.join.parse-base(2);
}
}
sub extract-values($line) {
my $address = $line.match(/\[(<digit>+)\]/)[0].Int;
my $value = $line.split(' = ')[1].Int;
($address, $value)
}
sub MAIN($file, Bool :$p2 = False) {
my $mask;
my @mem;
for $file.IO.lines -> $line {
if $line.starts-with('mask') {
$mask = $line.split(' = ')[1];
} else {
my ($address, $value) = extract-values($line);
if $p2 {
for apply-mask($mask, $address, $p2) -> $index {
@mem[$index] = $value;
}
} else {
@mem[$address] = apply-mask($mask, $value);
}
}
}
say @mem.sum;
}
```

This runs as such:

```
# Part 1
$ raku day-14.raku input.txt
17934269678453
# Part 2
$ raku day-14.raku --p2 input.txt
3440662844064
```

#### Explanation

We made a few tweaks to the original program:

- If it is
`$part-two`

,`apply-mask`

now returns a list of integers instead of just a single integer. - Given the above, if it is
`$p2`

in`MAIN`

, we iterate through the returned list. - We added a function
`find-all-masks`

that will find all binary combinations for the “floating” bits.

The logic is pretty much the same, except using addresses instead of values!

##### Specific Comments

- This solution works, but it is
*slow*and memory intensive. The correct way to find all of these bit flips is by using something called a Gray code. - We use these slips all over this to make sure we end up with just a 1D list (per call) when all is said and done.

## Final Thoughts

I am enjoying learning about all the shortcuts that are necessary to make these things run in an acceptable amount of time. Maybe next year I will be able to think of them without writing the brute force solution first!