Skip to content

Latest commit

 

History

History
479 lines (445 loc) · 14.1 KB

2018.16.org

File metadata and controls

479 lines (445 loc) · 14.1 KB

Day 16

Executing this code

If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:

  1. Starting slime (M-x slime)
  2. Typing C-c C-c in the block initialize.
  3. In the repl type (in-package :aoc-2018-16)
  4. Typing C-c C-c in the block answers

Initial stuffs

Packages to load

(unless (find-package :cl-ppcre)
  (ql:quickload "cl-ppcre"))
(unless (find-package :iterate)
  (ql:quickload "iterate"))
(unless (find-package :parseq)
  (ql:quickload "parseq"))
(unless (find-package :fiveam)
  (ql:quickload "fiveam"))

Create package for this day

<<packages>>
(defpackage :aoc-2018-16
  (:use :common-lisp
        :iterate
        :parseq
        :fiveam)
  (:export :problem-a
           :problem-b))
(in-package :aoc-2018-16)

Input

Need to gather each triple: pre, code, post. Fortunately we just need the numbers, stored as three lists in one list.

(defun parse-input (lines)
  (let ((triples nil)
        (instructions nil))
    (iter (until (and (string= "" (car lines))
                      (string= "" (cadr lines))))
          (push (list (make-array 4 :initial-contents (mapcar #'parse-integer (ppcre:all-matches-as-strings "\\d+" (pop lines))))
                      (make-array 4 :initial-contents (mapcar #'parse-integer (ppcre:all-matches-as-strings "\\d+" (pop lines))))
                      (make-array 4 :initial-contents (mapcar #'parse-integer (ppcre:all-matches-as-strings "\\d+" (pop lines)))))
                triples)
          (pop lines))
    (pop lines)
    (pop lines)
    (iter (while lines)
          (push (make-array 4
                            :initial-contents (mapcar #'parse-integer (ppcre:all-matches-as-strings "\\d+" (pop lines))))
                instructions))
    (list triples (reverse instructions))))
(defun read-input (file)
  (iter (for line in-file file using #'read-line)
        (collect line)))
(defparameter *input*
  (parse-input (read-input "input/16.txt")))

Part 1

We have a simple 4-register machine with 16 opcodes. We don’t know which opcode goes with which number, but we know what the potential opcodes are.p

The question is, given an input like:

Before: [1, 0, 2, 1]
2 3 2 0
After:  [1, 0, 2, 1]

Followed by 3 blank lines and then a list of commands.

How many of the possible opcodes does it match? We specifically want to know the number that match at least 3 opcodes.

Valid opcodes:

  • Addition
    addr
    [A] + [B] => [C]
    addi
    [A] + B => [C]
  • Multiplication
    mulr
    [A] * [B] => [C]
    muli
    [A] * B => [C]
  • Bitwise AND
    banr
    [A] & [B] => [C]
    bani
    [A] & B => [C]
  • Bitwise OR
    borr
    [A] | [B] => [C]
    bori
    [A] | B => [C]
  • Assignment
    setr
    [A] => [C]
    seti
    A => [C]
  • Greater than testing
    gtir
    A > [B] => [C]
    gtri
    [A] > B => [C]
    gtrr
    [A] > [B] => [C]
  • Equality testing
    eqir
    A > [B] => [C]
    eqri
    [A] > B => [C]
    eqrr
    [A] > [B] => [C]

I’m going to make one function per opcode from this list. It’ll take in the initial registers, and the command portion, but ignore the opcode part.

(defun addr (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (+ (aref registers a)
             (aref registers b)))
    registers))
(defun addrp (pre command post)
  (equalp (addr (copy-seq pre) command) post))

(defun addi (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (+ (aref registers a)
             b))
    registers))
(defun addip (pre command post)
  (equalp (addi (copy-seq pre) command) post))
(defun mulr (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (* (aref registers a)
             (aref registers b)))
    registers))
(defun mulrp (pre command post)
  (equalp (mulr (copy-seq pre) command) post))

(defun muli (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (* (aref registers a)
             b))
    registers))
(defun mulip (pre command post)
  (equalp (muli (copy-seq pre) command) post))
(defun banr (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (logand (aref registers a)
                  (aref registers b)))
    registers))
(defun banrp (pre command post)
  (equalp (banr (copy-seq pre) command) post))

(defun bani (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (logand (aref registers a)
                  b))
    registers))
(defun banip (pre command post)
  (equalp (bani (copy-seq pre) command) post))
(defun borr (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (logior (aref registers a)
                  (aref registers b)))
    registers))
(defun borrp (pre command post)
  (equalp (borr (copy-seq pre) command) post))

(defun bori (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (logior (aref registers a)
                  b))
    registers))
(defun borip (pre command post)
  (equalp (bori (copy-seq pre) command) post))
(defun setr (registers command)
  (let ((a (aref command 1))
        (c (aref command 3)))
    (setf (aref registers c)
          (aref registers a))
    registers))
(defun setrp (pre command post)
  (equalp (setr (copy-seq pre) command) post))

(defun seti (registers command)
  (let ((a (aref command 1))
        (c (aref command 3)))
    (setf (aref registers c)
          a)
    registers))
(defun setip (pre command post)
  (equalp (seti (copy-seq pre) command) post))
(defun gtir (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (if (> a (aref registers b)) 1 0))
    registers))
(defun gtirp (pre command post)
  (equalp (gtir (copy-seq pre) command) post))

(defun gtri (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (if (> (aref registers a) b) 1 0))
    registers))
(defun gtrip (pre command post)
  (equalp (gtri (copy-seq pre) command) post))

(defun gtrr (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (if (> (aref registers a) (aref registers b)) 1 0))
    registers))
(defun gtrrp (pre command post)
  (equalp (gtrr (copy-seq pre) command) post))
(defun eqir (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (if (= a (aref registers b)) 1 0))
    registers))
(defun eqirp (pre command post)
  (equalp (eqir (copy-seq pre) command) post))

(defun eqri (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (if (= (aref registers a) b) 1 0))
    registers))
(defun eqrip (pre command post)
  (equalp (eqri (copy-seq pre) command) post))

(defun eqrr (registers command)
  (let ((a (aref command 1))
        (b (aref command 2))
        (c (aref command 3)))
    (setf (aref registers c)
          (if (= (aref registers a) (aref registers b)) 1 0))
    registers))
(defun eqrrp (pre command post)
  (equalp (eqrr (copy-seq pre) command) post))
(defun problem-a () (format t "Problem 16 A: ~a~%" (solve-a (car *input*))))

So all the operations and their respective predicates exist. Let’s hope I wrote that all correctly, no tests so this will be fun.

(defun solve-a (to-test)
  (let ((predicates (list #'addrp #'addip #'mulrp #'mulip
                          #'banrp #'banip #'borrp #'borip
                          #'setrp #'setip #'gtirp #'gtrip
                          #'gtrrp #'eqirp #'eqrip #'eqrrp)))
    (iter (for (pre command post) in to-test)
          (count (iter (for p in predicates)
                       (with i = 0)
                       (when (funcall p pre command post)
                         (incf i))
                       (finally (return (>= i 3))))))))

Part 2

All of the opcode function -> number mappings can be discovered easily enough with the function below.

(defun tally-codes (to-test)
  (let ((predicates (list #'addr #'addi #'mulr #'muli
                          #'banr #'bani #'borr #'bori
                          #'setr #'seti #'gtir #'gtri
                          #'gtrr #'eqir #'eqri #'eqrr))
        (mapping (make-hash-table)))
    (iter (for p in predicates)
          (let ((opcodes (iter (for (pre command post) in to-test)
                               (when (equalp (funcall p (copy-seq pre) command) post)
                                 (collect (aref command 0))))))
            (setf (gethash p mapping) (remove-duplicates opcodes))))
    mapping))
(iter (for (k v) in-hashtable (tally-codes (car *input*)))
                   (format t "~a: ~a~%" k v))
#<FUNCTION ADDR>: (4 13 7)
#<FUNCTION ADDI>: (10 4 13)
#<FUNCTION MULR>: (10 14 5 4 13 7)
#<FUNCTION MULI>: (5 4 13 7)
#<FUNCTION BANR>: (0 14 5 15 4 6 7)
#<FUNCTION BANI>: (14 5 15 4 6 7)
#<FUNCTION BORR>: (4 7)
#<FUNCTION BORI>: (4)
#<FUNCTION SETR>: (5 4 7 2)
#<FUNCTION SETI>: (10 14 5 15 4 7)
#<FUNCTION GTIR>: (8 0 14 5 15 4 6 7 2)
#<FUNCTION GTRI>: (8 0 12 14 5 15 4 1 6 7 11)
#<FUNCTION GTRR>: (8 9 0 12 5 15 4 3 6 7 11)
#<FUNCTION EQIR>: (8 0 12 5 15 1 3 6 11)
#<FUNCTION EQRI>: (8 0 12 14 5 15 6 7)
#<FUNCTION EQRR>: (8 0 14 5 15 1 6)

So it’s obvious that BORI = 4, BORR = 7, and so on. I’m going to write a quick routine to iterate over this until every function has only one opcode.

(defun get-opcodes (to-test)
  (let ((tally (tally-codes to-test))
        (result (make-hash-table)))
    (iter (until (iter (for (k v) in-hashtable tally)
                       (always (= 1 (length v)))))
          (iter (for (k v) in-hashtable tally)
                (when (= 1 (length v))
                  (iter (for (k0 v0) in-hashtable tally)
                        (unless (equal k k0)
                          (setf (gethash k0 tally) (remove (car v) v0)))))))
    (iter (for (k v) in-hashtable tally)
          (setf (gethash (car v) result) k))
    result))
00: #<FUNCTION BANR>
01: #<FUNCTION EQRR>
02: #<FUNCTION SETR>
03: #<FUNCTION EQIR>
04: #<FUNCTION BORI>
05: #<FUNCTION MULI>
06: #<FUNCTION BANI>
07: #<FUNCTION BORR>
08: #<FUNCTION GTIR>
09: #<FUNCTION GTRR>
10: #<FUNCTION ADDI>
11: #<FUNCTION GTRI>
12: #<FUNCTION EQRI>
13: #<FUNCTION ADDR>
14: #<FUNCTION MULR>
15: #<FUNCTION SETI>

(defun solve-b (to-test to-run)
  (let ((codes (get-opcodes to-test))
        (registers (make-array 4 :initial-element 0)))
    (iter (for command in to-run)
          (funcall (gethash (aref command 0) codes)
                   registers
                   command))
    registers))
(defun problem-b () (format t "Problem 16 B: ~a~%" (solve-b (car *input*) (cadr *input*))))

Putting it all together



<<addition>>
<<multiplication>>
<<bitwise-and>>
<<bitwise-or>>
<<assignment>>
<<greater-than>>
<<equality>>
<<read-input>>
<<parse-input>>


<<initialize>>
<<structs>>
<<functions>>
<<input>>
<<solve-a>>
<<problem-a>>
<<tally-codes>>
<<get-opcodes>>
<<solve-b>>
<<problem-b>>
(problem-a)
(problem-b)


Answer


Problem 16 A: 677
Problem 16 B: #(540 2 9 540)



Test Cases


(def-suite aoc.2018.16)
(in-suite aoc.2018.16)

(run! 'aoc.2018.16)


Test Results


Thoughts