16 minutes

# Advent of Code 2020: Day 14

As usual, I’m an active participant of the annual Advent of Code puzzle
challenge. Not on the competitive side. First, I don’t care and second,
I will **NOT** wake up at 6am.

This year, all the puzzles are kind of easy and I was a bit disappointed. Last year
it had a good raise in difficulty day by day, but now, all of them are on the
same level. At least that’s how I feel. Maybe it’s because this
year I decided to do it in `Go`

and not `Haskell`

… I learned a lot about Haskell
last year and it still bugs me that I didn’t complete all the days. But I had no
time. That’s the reason why I started to do it in Go this year. I’m happy if I
have time to do it at night.

And here we are. **Day 14 was fun**. The first one this year.

## Description

The problem is simple. At least it seems simple. Our input file contains `mask`

and `mem[x]`

lines.

- If it’s
`mask = _____`

, it sets the mask we have to use. - If it’s
`mem[n] = k`

, we have to set the value of the register`n`

to`k`

.

Well, the original text has much more flavor and decoration, but this is the core. The machine works with 36bit registers, so the mask and all values for set can fit in a 36bit integer.

My whole solution is available on Github.

### Mask

The mask is a bitmask. Each bit can be `X`

, `0`

or `1`

. All of them have their own
meaning in the bitmask, and they are different in Part 2 compared to Part 1.

### Set register

If it’s an instruction to set the register, both `n`

and `k`

are numbers, and they are
also different in Part 2 compared to Part 1.

## Part 1

### Mask

In Part 1, each bit in the mask has this property:

- If it’s
`X`

, then it leaves the corresponding bit as it is. - If it’s
`0`

, then it overwrites the corresponding bit with`0`

. - If it’s
`1`

, then it overwrites the corresponding bit with`1`

.

### Prepare

First of all, we have to parse the input. Each line can be an `Operation`

.
Initially it can be a simple struct:

```
type Operation struct {
Address uint64
Value uint64
Mask *Mask
}
```

We will store everything in unsigned 64bit integers, just for safety. There is an extra struct, but first, let’s see the mask.

It seems we have bits to set to `0`

and others we have to set
to `1`

. As the example shows:

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

We can set a bit with bitwise operations.

- We can set a bit to
`0`

if we use the`&`

operator with a number that has`1`

s on all bits except the one we want to set to`0`

. - We can set a bit to
`1`

if we use the`|`

operator with a number that has`0`

s on all bits expect the one we want to set to`1`

.

### Bitwise operators

Let’s see it in action.

#### Or

We have the `00101010`

value and we want to set the 3rd
(`2^0`

, `2^1`

`2^2`

from the right) bit to `1`

as it is a `0`

now. So we want to
end up with `00101110`

. With the instructions above, we can do it with `|`

. Our
mask has to be all zeros except the bit we want to set to `1`

, so it’s `0000100`

.

```
Operation: | (or)
Original: 00101010
Mask: 00000100
Expected: 00101110
```

It works as expected, because on each bit we have `0`

in the mask, so basically
the original value will be used. The only exception is the bit we set to `1`

, on
that bit, we don’t care if the original was `1`

or `0`

, because with `or`

, it
will always be `1`

.

#### And

Now we want to set the 2nd bit to `0`

. Based on the
instructions above, we have to set all bits to `1`

in the mask, except the
bit we want to set to zero and use the `&`

operator.

```
Operation: & (and)
Original: 00101110
Mask: 11111101
Expected: 00101100
```

It works as expected, because on each bit we have `1`

in the mask. If the
original value was `1`

we have `1 & 1`

which is `1`

, if the original value was
`0`

, then we have `0 & 1`

which is `0`

. So we keep the same value as we had
originally, except the only bit we set to zero, because in that case, it does
not matter if the original value was `1`

or `0`

, if we compare it with `and`

to
a `0`

, it will always be `0`

.

#### Shift

We can shift bits to the left or to the right with `<< n`

and `>> n`

. We will
only use left shifts.

If we shift to the left `<<<`

we shift all bits to left (to more significant bit
value) and fill in with `0`

for the first `n`

bit. From `1101`

with `<< 1`

,
the result will be `11010`

. With `<< 3`

, we will end up with `1101000`

.

#### Not

We don’t go deeper in this one, it’s a very simple operator, it just negates
each bit we have. If it was a `0`

, it will be a `1`

and vice versa.

We will use it. Trust me.

### Building blocks

So we have a “mask”, but it’s basically two masks at the same time. The `1`

parts in
the provided mask just mean “use or”, and the `0`

parts just mean “use and”. So
we can split up the original mask into two different masks.

And that’s why we have the `Mask`

struct.

```
// Repeated from above
type Operation struct {
Address uint64
Value uint64
Mask *Mask
}
type Mask struct {
And uint64
Or uint64
}
```

What do we have here? We have an `Operation`

that has an `Address`

, `Value`

and a
`Mask`

field. The `Mask`

field is a pointer, it can be `nil`

. Why? Because that
way we can easily identify if an `Operation`

is a “Set mask” or a “Set
register”.

```
// IsMask is a simple helper function, so I don't have
// to write ugly `if operation.Mask != nil`.
func (o *Operation) IsMask() bool {
return o.Mask != nil
}
```

Now, we have everything to parse and store an operation.

We want to parse the input line by line, so we can do a simple (maybe not elegant) loop with scanner and call functions to parse a given line. We can make a huge “if-elseif-else” block, but we can say “parse mask” if it did not work, we can ask to “parse register assignment”… Well if it did not work, we can skip the line as it’s not a valid one.

```
func (d *Solver) SetInput(input io.Reader) error {
scanner := bufio.NewScanner(input)
d.memory = map[uint64]uint64{}
d.operations = []Operation{}
for scanner.Scan() {
text := scanner.Text()
op := d.parseMask(text)
if op == nil {
op = d.parseAssignment(text)
}
if op != nil {
d.operations = append(d.operations, *op)
}
}
return scanner.Err()
}
```

### Parse register assignment

This is the easiest part of the puzzle. We can do it with the `Sscanf`

function
from the `fmt`

package.

```
func (d *Solver) parseAssignment(text string) *Operation {
// Return if it's not a "set".
if !strings.HasPrefix(text, "mem") {
return nil
}
var op Operation
// Parse the line.
fmt.Sscanf(text, "mem[%d] = %d", &op.Address, &op.Value)
return &op
}
```

### Parse Mask

This is the tricky part. We have to walk through the bitmask string and build up
our `Mask`

.

Building up the `or`

part is not as tricky as building up the `and`

part, as we
want to set all bits to `1`

as an initial state for that mask. We are using
`uint64`

so it’s not enough to just use `math.MaxUint64`

, because that will set
all bits to `1`

above the 36th bit too and that’s not what we want.

We can achieve what we want with `math.MaxUint64 & 0xfffffffff`

. With this
trick, we have a value that has all bits set to `1`

on the first 36 bits.

We can walk thought the string from the left or from right end of the string, but we have to set the values based on that. We can reverse the string, or we can just calculate the values based on the length and the current index.

```
const bitmaskFor36bits = 0xfffffffff
func (d *Solver) parseMask(text string) *Operation {
// Return if it's not a "mask".
if !strings.HasPrefix(text, "mask = ") {
return nil
}
var (
stream string
op Operation
)
// Parse the line.
fmt.Sscanf(text, "mask = %s", &stream)
// Set the mask to it's initial state.
op.Mask = &Mask{And: math.MaxUint64 & bitmaskFor36bits, Or: 0}
l := len(stream) - 1
// Check all characters in the mask string.
for idx := l; idx >= 0; idx-- {
// Magic.
}
return &op
}
```

We have a solid skeleton, the only missing part is to build up our `Mask`

.

For the first bit we want the number where everything is zero expect the bit
where we are right now. So we want `1`

, `10`

, `100`

and so on. That looks like a
bit shift, so we can set up a given bit with `1 << n`

.

As we are parsing the mask from the end of the string (from the least
significant bit), we will set the first bit first and we want to shift it with
`0`

(basically no shift). The value of the `idx`

variable starts with the length
of the string (-1), but we need `0`

for the first round. We can get the value
with `l - idx`

, for the first round `idx = l`

so the result will be `0`

. For the
next round, because of `idx--`

, the result will be `1`

, then `2`

and so on.

Nice, we can generate a value that has only one `1`

bit and it will be at the
right position with `1 << (l - idx)`

.

For the `or`

mask, we want to set the given bit to `1`

, so we can just use the
same or operation again as `op.Mask.Or ^= v`

.

For the `and`

mask, we want to set the given bit to `0`

, but we have all zeros
except the one we want to set. We can use the `not`

operator. It does the thing
we need now (`^value`

). From `0010`

, it will be `1101`

. If we scroll back, we
know that we can set a given bit to `0`

with that. As we have a full-ones
originally, all additional `&`

calls will just set one bit to `0`

.

```
// Check all characters in the mask string.
for idx := l; idx >= 0; idx-- {
// Current value.
bit := stream[idx]
v := uint64(1 << (l - idx))
switch bit {
case '1':
op.Mask.Or ^= v
case '0':
op.Mask.And &= ^v
}
}
```

So that’s how the `parseMask`

function looks like at the end (for now).

```
const bitmaskFor36bits = 0xfffffffff
func (d *Solver) parseMask(text string) *Operation {
// Return if it's not a "mask".
if !strings.HasPrefix(text, "mask = ") {
return nil
}
var (
stream string
op Operation
)
// Parse the line.
fmt.Sscanf(text, "mask = %s", &stream)
// Set the mask to it's initial state.
op.Mask = &Mask{And: math.MaxUint64 & bitmaskFor36bits, Or: 0}
l := len(stream) - 1
// Check all characters in the mask string.
for idx := l; idx >= 0; idx-- {
// Current value.
bit := stream[idx]
v := uint64(1 << (l - idx))
switch bit {
case '1':
// Set the bit in the Or mask.
op.Mask.Or ^= v
case '0':
// Set the bit in the And mask.
op.Mask.And &= ^v
}
}
return &op
}
```

### Solution

What do we have now? We have an empty `map[uint64]uint64`

for the memory and a
`[]Operation`

list with all the operations we have to execute on the memory. We
only have to apply our `And`

and `Or`

masks on the values.

```
for _, op := range d.operations {
if op.IsMask() {
// If it's a "Set mask", just set the mask.
d.currentMask = op.Mask
continue
}
// Set the value with our masks applied on a given address.
d.memory[op.Address] = (op.Value & d.currentMask.And) | d.currentMask.Or
}
```

And that’s it. This is the first part of the puzzle. We have to sum all the values in the register, but that’s easy.

```
func (d *Solver) sum() uint64 {
sum := uint64(0)
for _, v := range d.memory {
sum += v
}
return sum
}
```

## Part 2

For part 2, it was a bit harder. That’s the reason I really enjoyed it.

### Changes

These are the changes we have compared to part 1:

- The mask is applied on the address not on the value.
- If we see a
`0`

bit in the mask, it means we don’t want to change the value, like the`X`

was in part 1. - If we see a
`1`

bit in the mask, it means we want to overwrite the corresponding bit to`1`

. - If we see an
`X`

bit in the mask, we want to set the corresponding bit as “floating” bit.

### Floating bit

A floating bit is not connected to anything and instead fluctuates unpredictably. In practice, this means the floating bits will take on all possible values, potentially causing many memory addresses to be written all at once!

Huh? What does that mean? If we have `1x0x`

as a result (where `x`

is a floating
bit), we have to write the value into these four registers:

`1000`

`1001`

`1100`

`1101`

If we have 3 floating bits, we will write to 8 different registers at the same
time. How convenient, we can calculate how many registers we have to write with
`2^n`

(number of combinations).

### Maskv2

First we have to implement a new `Mask`

type. It has the original `Or`

mask, as
we want to set all `1`

bits to `1`

. We don’t need the `And`

mask, because on
`0`

, we will leave the bit as it is, but we have to handle the Floating bits
somehow.

If we take a closer look, the floating bits part is a monster, but not as much as
it seems. Basically we want to iterate through all possible combinations and set
the bits to `0`

or `1`

. It looks like a `Mask`

from part 1, so we can make a
list of `Mask`

s and just apply all of them one by one on the original address.

```
type Maskv2 struct {
Or uint64
Floating []Mask
}
```

We want to store it somewhere, so we can extend our `Operation`

:

```
type Operation struct {
Address uint64
Value uint64
Mask *Mask
Maskv2 *Maskv2
}
```

### Parse Maskv2

Everything is set, we can use the `parseMask`

function from part 1 and it’s
enough if we can set the `Maskv2`

field.

If it’s `1`

, we can use the same `Or`

as before and we can ignore if it’s a `0`

.

For Floating bits, we can store each bit as it is an `Or`

and `And`

. At the end
we have a `[]Mask`

with all possible bit positions. For example, if we have
`0x0x`

, out list has two `Mask`

s in it:

- for
`0_0x`

, we have`Or: 0100; And: 1011`

- for
`0x0_`

, we have`Or: 0001; And: 1110`

```
op.Maskv2 = &Maskv2{Or: 0, Floating: []Mask{}}
for idx := l; idx >= 0; idx-- {
bit := stream[idx]
v := uint64(1 << (l - idx))
switch bit {
case '1':
op.Mask.Or ^= v
op.Maskv2.Or ^= v
case '0':
op.Mask.And &= ^v
case 'X':
// Add Floating bits one by one.
op.Maskv2.Floating = append(op.Maskv2.Floating, Mask{
And: math.MaxUint64 & bitmaskFor36bits & (^v),
Or: v,
})
}
}
```

### Solution

We will do the same as before, but we apply the `Or`

part on the address, not on
the value.

`address := op.Address | d.currentMaskv2.Or`

After that, we have to do some black magic. And I think basically that’s the reason I write this post.

As we discovered earlier, we know, we have `2^n`

combinations. If we have 5
floating bits, we have `2^5`

combinations, we have to write the value into 32
different registers. That sounds like a good starting point. Make a for loop for
all the values we need. Calculating `2^n`

is easy, we don’t need any
external library for that, we can use bit shifting again.

`2^0`

is`1`

, the same as`1 << 0`

which is`0001`

`2^1`

is`2`

, the same as`1 << 1`

which is`0010`

`2^2`

is`4`

, the same as`1 << 2`

which is`0100`

`2^3`

is`8`

, the same as`1 << 3`

which is`1000`

```
for i := 0; i < 1<<len(d.currentMaskv2.Floating); i++ {
// ...
}
```

Now, we want to apply both the `And`

(`&`

) and `Or`

(`|`

) masks, but not at the same time.
We want to generate all combinations. In words of `&`

and `|`

, if we have
`0x0x`

, we want to apply these masks:

- Apply the first and the second
`&`

which will be`0000`

. - Apply the first
`&`

and the second`|`

which will be`0001`

. - Apply the first
`|`

and the second`&`

which will be`0100`

. - Apply the first and the second
`|`

which will be`0101`

.

```
for i := 0; i < 1<<len(d.currentMaskv2.Floating); i++ {
for idx, m := range d.currentMaskv2.Floating {
// ...
}
}
```

There is an easy way to make that awesome split. It has two parts. The first
part is the `i`

variable. It goes from `0`

to `2^n`

. Let’s write up all the
values it can get based on the example above:

`0000`

`0001`

`0010`

`0011`

And that’s it. If we have 3 floating bits, we would go up to `0111`

.

It’s not easy, but if you see it it’s hard to miss it. We have all combinations with a nice grid.

`0000`

-> Apply`&`

and`&`

.`0001`

-> Apply`&`

and`|`

.`0010`

-> Apply`|`

and`&`

.`0011`

-> Apply`|`

and`|`

.

```
[2020-12-15] update, maybe it shows the matching bits better:
0x0x
0 0 -> i == 0
0 1 -> i == 1
1 0 -> i == 2
1 1 -> i == 3
```

How can we utilize this knowledge? First let’s see what do we have in `idx`

. We
have two items in `[]Mask`

, so `idx`

can be `0`

and `1`

. If we have three items
in there, it can be `0`

, `1`

and `2`

.

We can shift all the bits again. We can use `1 << idx`

and bitmask `i`

with
the result. If it’s not zero, we have to apply the `Or`

part (we want to set
it to 1), otherwise apply the `And`

part (set it to 0).

How does it work (same example `0x0x`

)?

`0000`

&`1 << 0`

(`0001`

) -> 0 -> apply`&`

`0000`

&`1 << 1`

(`0010`

) -> 0 -> apply`&`

`0001`

&`1 << 0`

(`0001`

) -> 1 -> apply`|`

`0001`

&`1 << 1`

(`0010`

) -> 0 -> apply`&`

`0010`

&`1 << 0`

(`0001`

) -> 0 -> apply`&`

`0010`

&`1 << 1`

(`0010`

) -> 1 -> apply`|`

`0011`

&`1 << 0`

(`0001`

) -> 1 -> apply`|`

`0011`

&`1 << 1`

(`0010`

) -> 1 -> apply`|`

(You can grab a pencil and paper; and write down all possible values for 3 floating bits).

```
for i := 0; i < 1<<len(d.currentMaskv2.Floating); i++ {
for idx, m := range d.currentMaskv2.Floating {
if i&(1<<idx) > 0 {
address |= m.Or
} else {
address &= m.And
}
}
d.memory[address] = op.Value
}
```

And that’s it. We did it.

## Conclusion

I really love this puzzle, it has all the beauty in it. It’s so simple, but still so complicated.