Day 14 banner

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 1s 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 0s 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 Masks 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 Masks 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:

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