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:

mem = 11
mem = 101
mem = 0

value:  000000000000000000000000000000001011  (decimal 11)
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.

my @num-list  = \$num.base(2).comb;

@num-list.unshift(0);                                 # 
}

}
}

}

sub extract-values(\$line) {
my \$value = \$line.split(' = ').Int;
}

sub MAIN(\$file) {
my @mem;
for \$file.IO.lines -> \$line {
} else {
}
}
say @mem.sum; # 
}

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

1. 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.
2. Z is Raku’s zip operator. So (1, 2, 3) Z (4, 5, 6) yields ((1, 4), (2, 5), (3, 6)).
3. 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:

result:  000000000000000000000000000000X1101X

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 = ()) {                          # 
if \$pointer == @zipped.elems {
@prefix.join.parse-base(2);
} else {
when '0' { find-all-masks(@zipped, \$pointer + 1, (|@prefix, \$digit)) } # 
when 'X' {
|(
find-all-masks(@zipped, \$pointer + 1, (|@prefix, '0')),
find-all-masks(@zipped, \$pointer + 1, (|@prefix, '1'))
)
}
}
}
}

my @num-list  = \$num.base(2).comb;

@num-list.unshift(0);
}

if \$part-two {
} else {
}
}
}
}

sub extract-values(\$line) {
my \$value = \$line.split(' = ').Int;
}

sub MAIN(\$file, Bool :\$p2 = False) {
my @mem;
for \$file.IO.lines -> \$line {
} else {
if \$p2 {
@mem[\$index] = \$value;
}
} else {
}
}
}
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:

1. If it is \$part-two, apply-mask now returns a list of integers instead of just a single integer.
2. Given the above, if it is \$p2 in MAIN, we iterate through the returned list.
3. 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!