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.

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

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 {
Value   uint64
}
``````

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)
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
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
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 {
Value   uint64
}

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 {
}
``````

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

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
}
``````

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.

// Set the mask to it's initial state.

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':
case '0':
}
}
``````

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.

// Set the mask to it's initial state.

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.
case '0':
// Set the bit in the And mask.
}
}

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 {

continue
}

// Set the value with our masks applied on a given address.
}
``````

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

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
}
``````

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

``````type Operation struct {
Value   uint64
}
``````

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':
case '0':
case 'X':
// Add Floating bits one by one.
And: math.MaxUint64 & bitmaskFor36bits & (^v),
Or:  v,
})
}
}
``````

### Solution v2

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:

1. Apply the first and the second `&` which will be `0000`.
2. Apply the first `&` and the second `|` which will be `0001`.
3. Apply the first `|` and the second `&` which will be `0100`.
4. 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:

1. `0000`
2. `0001`
3. `0010`
4. `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.

1. `0000` -> Apply `&` and `&`.
2. `0001` -> Apply `&` and `|`.
3. `0010` -> Apply `|` and `&`.
4. `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 {
} else {