2020, Day 14: Docking Data 🚢 💽

Today was an opportunity to learn more about bitops.

import
  bitops, tables, algorithm, math, strscans, strutils

For part 1 I first make sure I can parse the mask. floating field is a result of refactoring for part 2.

type
  Mask = object
    ones: int
    zeros: int
    floating: seq[int]

  Memory = Table[int, int]
var
  mem: Memory
  mask: Mask
proc parseMask(text: string): Mask =
  for i, c in text.reversed:
    case c
    of '0':
      result.zeros += 2 ^ i
    of '1':
      result.ones += 2 ^ i
    of 'X':
      result.floating.add i
    else:
      echo "ERROR unexpected character in mask string: ", i, " ", c

func apply(n: int; m: Mask): int =
  result = n
  setMask[int](result, m.ones)
  clearMask[int](result, m.zeros)

mask = parseMask "XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X"
echo mask
echo 11.apply(mask)          ## 73
echo 101.apply(mask)

(ones: 64, zeros: 2, floating: @[0, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35])
73
101

Now let's parse full programming instructions with startswith and scanf. I gotta say that I tend to forget the syntax of object variants (case kind: T sounds pretty special).

type
  Program = seq[Action]
  ActionKind = enum
    updateMask, writeMem
  Action = object
    case kind: ActionKind
    of updateMask:
        mask: Mask

    of writeMem:
        address: int
        value: int

  
proc parse(text: string): Program =
  var a: Action
  for line in text.splitLines:
    if line.startsWith("mask"):
      a.kind = updateMask
      a.mask = parseMask line[7 .. line.high]
    elif line.startsWith("mem"):
      a.kind = writeMem
      if not scanf(line, "mem[$i] = $i", a.address, a.value):
        echo "ERROR parsing writeMem: ", line
    else:
      echo "ERROR parsing line: ", line
    result.add a

let example = """mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0"""
let exProg = parse example
echo $exProg

@[(kind: updateMask, mask: (ones: 64, zeros: 2, floating: @[0, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35])), (kind: writeMem, address: 8, value: 11), (kind: writeMem, address: 7, value: 101), (kind: writeMem, address: 8, value: 0)]

Last ingredient is the proc to run the Program on Cpu.

type
  Cpu = object
    mask: Mask
    mem: Memory

var cpu: Cpu
template resetCpu() =
  clear cpu.mem              ## no need to reset mask as it is update as first action in program
  
proc run(cpu: var Cpu; p: Program) =
  for a in p:
    case a.kind
    of updateMask:
      cpu.mask = a.mask
    of writeMem:
      cpu.mem[a.address] = a.value.apply(cpu.mask)

cpu.run exProg
echo cpu
proc answer(cpu: Cpu): int =
  for v in cpu.mem.values:
    result += v

echo answer cpu
resetCpu
let inProg = parse "2020/input14.txt".readFile
cpu.run inProg
echo answer cpu

(mask: (ones: 64, zeros: 2, floating: @[0, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35]), mem: {7: 101, 8: 64})
165
14925946402938

That's the right answer! You are one gold star closer to saving your vacation.

for part 2:

• after refactoring mask code to parse floating bits (done above)
• run2 proc below is straightforward
• apply2 is the part that creates multiple addresses starting from a single address and a mask
• finally zeroBits is the key ingredient that generates all floating bits combinations.

At one point I did consider coding a recursive iterator, but apparently that is not possible, see forum.

iterator zeroBits(s: seq[int]): seq[int] =
  var m: int
  var t: seq[int]
  for n in 0 ..< 2 ^ (s.len):
    m = n
    t = @[]
    for i in 0 .. s.high:
      if m mod 2 == 0:
        t.add s[i]
      m = m shr 1
    yield t

for s in zeroBits(@[1, 3, 5]):
  echo s
func apply2(a: int; m: Mask): seq[int] =
  var b = a
  setMask[int](b, m.ones)
  ## I ignore zeros part of the mask
                         ## floating: loop over all possible combinations
  for zeroBits in zeroBits(m.floating):
    var c = b
    for i in m.floating:
      if i in zeroBits:
        c.clearBit(i)
      else:
        c.setBit(i)
    result.add c

let exMask = parseMask("000000000000000000000000000000X1001X")
echo 42.apply2(exMask)

@[1, 3, 5]
@[3, 5]
@[1, 5]
@[5]
@[1, 3]
@[3]
@[1]
@[]
@[26, 27, 58, 59]

looks good. let's apply directly to input without bothering about the example

proc run2(cpu: var Cpu; p: Program) =
  for a in p:
    case a.kind
    of updateMask:
      cpu.mask = a.mask
    of writeMem:
      for address in a.address.apply2(cpu.mask):
        cpu.mem[address] = a.value

resetCpu
cpu.run2 inProg
echo answer cpu

3706820676200

That's the right answer! You are one gold star closer to saving your vacation.