Advent of Code 2020 Day 14

Part 1

I first thought about using integers, with two bitmasks - one that will be OR’d (to overwrite 1’s) and the other that will be AND’d (to overwrite 0’s), but then I have to truncate to 36 bits. So it’s probably easier (for now) to just deal with the string representations, taking advantage of the bitstring() builtin.

tok = split(line)
if tok[1] == "mask"
    mask = tok[3]
else
    nstr = bitstring(parse(Int64, tok[3]))[64-36+1:end]
    fstr = join([mask[x] != 'X' ? mask[x] : nstr[x] for x in 1:36])
    mem[addr] = parse(Int, fstr, base=2)
end

Part 2

Conceptually simple: for each X generate two addresses, and should be straightforward to implement recursively. I start by moving the part1-specific logic out of readinput() into a new function, so I can reuse the reading/parsing logic. The recursive function can undoubtably be improved, but it works.

function maskaddr(addr, mask)
    if length(addr) == 0 || length(mask) == 0
        [""]
    else
        f(x) = map(y->join([x, y]), maskaddr(addr[2:end], mask[2:end]))
        if mask[1] == '0'
            f(addr[1])
        elseif mask[1] == '1'
            f('1')
        else
            [f('0'); f('1')]
        end
    end
end
@test maskaddr("101010","X1001X") == ["011010","011011","111010","111011"]

Extra Credit

Common Lisp

A fairly straightforward re-implementation of the Julia solution, although it required some more involved parsing due to the limited standard library, notably no split function to tokenize strings or regex support¹. I wrote a naive tokenizer function as an exercise, and extracted the address with a simple function that extracts and parses the digit characters from the string:

(defun parse-address (str)
  (let ((start (position-if #'digit-char-p str)))
    (parse-integer (subseq str start (position-if-not #'digit-char-p str :start start)))))

I used loop to simultaneously iterate over the value (represented in binary in a string) and mask:

(defun masked-value (mask value)
  (concatenate
   'string
   (loop for nb across (to-binary value)
         for mb across mask
         collect (if (char= mb #\X) nb mb))))

I wrote a couple helper functions to convert to and from binary string representation:

(defun to-binary (n)
  (format nil "~36,'0B" n))

(defun from-binary (str)
  (parse-integer str :radix 2))