If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:
- Starting slime (
M-x slime) - Typing
C-c C-cin the block initialize. - In the repl type
(in-package :aoc-2018-21) - Typing
C-c C-cin the block answers
(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"))<<packages>>
(defpackage :aoc-2018-21
(:use :common-lisp
:iterate
:parseq
:fiveam)
(:export :problem-a
:problem-b))
(in-package :aoc-2018-21)(defstruct (computer (:conc-name cp-))
(instructions nil)
(ip 0)
(registers (make-array 6 :initial-element 0)))
(defstruct instruction
operation
a
b
c)
(defun parse-line (line)
(with-input-from-string (s line)
(make-instruction :operation (symbol-function (read s))
:a (read s)
:b (read s)
:c (read s))))
(defun parse-input (list)
(let ((computer (make-computer)))
(setf (cp-ip computer) (parse-integer (ppcre:scan-to-strings "\\d+" (car list))))
(iter (for line in (cdr list))
(push (parse-line line) (cp-instructions computer)))
(setf (cp-instructions computer) (reverse (cp-instructions computer)))
computer))(defun read-input (file)
(iter (for line in-file file using #'read-line)
(collect line)))(defparameter *input*
(parse-input (read-input "input/21.txt")))This is a continuation of the virtual machine stuffs. I’ll go ahead and use my implementation from Day 19.
(defun addr (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(+ (aref registers a)
(aref registers b)))
registers))
(defun addi (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(+ (aref registers a)
b))
registers))(defun mulr (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(* (aref registers a)
(aref registers b)))
registers))
(defun muli (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(* (aref registers a)
b))
registers))(defun banr (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(logand (aref registers a)
(aref registers b)))
registers))
(defun bani (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(logand (aref registers a)
b))
registers))(defun borr (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(logior (aref registers a)
(aref registers b)))
registers))
(defun bori (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(logior (aref registers a)
b))
registers))(defun setr (registers command)
(with-slots (a c) command
(setf (aref registers c)
(aref registers a))
registers))
(defun seti (registers command)
(with-slots (a c) command
(setf (aref registers c)
a)
registers))(defun gtir (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(if (> a (aref registers b)) 1 0))
registers))
(defun gtri (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(if (> (aref registers a) b) 1 0))
registers))
(defun gtrr (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(if (> (aref registers a) (aref registers b)) 1 0))
registers))(defun eqir (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(if (= a (aref registers b)) 1 0))
registers))
(defun eqri (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(if (= (aref registers a) b) 1 0))
registers))
(defun eqrr (registers command)
(with-slots (a b c) command
(setf (aref registers c)
(if (= (aref registers a) (aref registers b)) 1 0))
registers))(defun simulate (computer &optional (iv #(0 0 0 0 0 0)) (limit 1000000))
(let ((iterations 0)
(halt-values (make-hash-table)))
(with-slots (ip registers instructions) computer
(setf registers iv)
(iter (while (and (>= (aref registers ip) 0)
(< (aref registers ip) (length instructions))))
(until (> iterations limit))
(let ((current (elt instructions (aref registers ip))))
(with-slots (operation) current
(funcall operation registers current)
(when (= (aref registers ip) 28)
(when (gethash (aref registers 5) halt-values)
(return halt-values))
(unless (gethash (aref registers 5) halt-values)
(format t "~d: ~d~%" (aref registers 5) iterations)
(setf (gethash (aref registers 5) halt-values) iterations)))
(incf (aref registers ip))
(incf iterations)))))))(simulate *input* #(6619857 0 0 0 0 0) 1000000000)That will terminate in less than a second. I found the value for both by running the above program (changed to actually terminate, the one I actually used didn’t terminate it just went on forever). The above will detect a cycle in the values of register 5 and return a hash table with each value of register 5 and at what iteration it was reached (could by off-by-one, but that number doesn’t matter). The two desired values can be found by examining the printout or storing the hash table and querying it for which keys corresponded to the min/max iteration value.
I managed to shave off a few seconds by moving symbol-function to
the creation of the instruction instances.
Rather than run the whole thing I use 712 as a benchmark. It took 90
seconds in my initial version. 89 by moving symbol-function. Another
3 seconds were removed by getting rid of (setf registers (...))
because that was redundant (the operations themselves change the
registers array already).
The original version took 586 seconds to find the cycle. With those updates it now takes 536 seconds. That’s a pretty good improvement.
(defun problem-a () (format t "Problem 21 A: ~a~%" (identity *input*)))(simulate *input* #(9547924 0 0 0 0 0) 10000000000)That will terminate eventually.
(defun problem-b () (format t "Problem 21 B: ~a~%" (identity *input*)))<<addition>>
<<multiplication>>
<<bitwise-and>>
<<bitwise-or>>
<<assignment>>
<<greater-than>>
<<equality>>
<<parse-input>>
<<simulate>>
<<read-input>><<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)Problem 21 A: #S(COMPUTER
:INSTRUCTIONS (#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 123
:B 0
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION BANI>
:A 5
:B 456
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION EQRI>
:A 5
:B 72
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDR>
:A 5
:B 2
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 0
:B 0
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 0
:B 3
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION BORI>
:A 5
:B 65536
:C 3)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 9010242
:B 6
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION BANI>
:A 3
:B 255
:C 1)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDR>
:A 5
:B 1
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION BANI>
:A 5
:B 16777215
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION MULI>
:A 5
:B 65899
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION BANI>
:A 5
:B 16777215
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION GTIR>
:A 256
:B 3
:C 1)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDR>
:A 1
:B 2
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDI>
:A 2
:B 1
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 27
:B 6
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 0
:B 8
:C 1)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDI>
:A 1
:B 1
:C 4)
#S(INSTRUCTION
:OPERATION #<FUNCTION MULI>
:A 4
:B 256
:C 4)
#S(INSTRUCTION
:OPERATION #<FUNCTION GTRR>
:A 4
:B 3
:C 4)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDR>
:A 4
:B 2
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDI>
:A 2
:B 1
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 25
:B 5
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDI>
:A 1
:B 1
:C 1)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 17
:B 7
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETR>
:A 1
:B 3
:C 3)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 7
:B 2
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION EQRR>
:A 5
:B 0
:C 1)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDR>
:A 1
:B 2
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 5
:B 2
:C 2))
:IP 2
:REGISTERS #(0 0 0 0 0 0))
Problem 21 B: #S(COMPUTER
:INSTRUCTIONS (#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 123
:B 0
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION BANI>
:A 5
:B 456
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION EQRI>
:A 5
:B 72
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDR>
:A 5
:B 2
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 0
:B 0
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 0
:B 3
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION BORI>
:A 5
:B 65536
:C 3)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 9010242
:B 6
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION BANI>
:A 3
:B 255
:C 1)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDR>
:A 5
:B 1
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION BANI>
:A 5
:B 16777215
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION MULI>
:A 5
:B 65899
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION BANI>
:A 5
:B 16777215
:C 5)
#S(INSTRUCTION
:OPERATION #<FUNCTION GTIR>
:A 256
:B 3
:C 1)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDR>
:A 1
:B 2
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDI>
:A 2
:B 1
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 27
:B 6
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 0
:B 8
:C 1)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDI>
:A 1
:B 1
:C 4)
#S(INSTRUCTION
:OPERATION #<FUNCTION MULI>
:A 4
:B 256
:C 4)
#S(INSTRUCTION
:OPERATION #<FUNCTION GTRR>
:A 4
:B 3
:C 4)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDR>
:A 4
:B 2
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDI>
:A 2
:B 1
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 25
:B 5
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDI>
:A 1
:B 1
:C 1)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 17
:B 7
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETR>
:A 1
:B 3
:C 3)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 7
:B 2
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION EQRR>
:A 5
:B 0
:C 1)
#S(INSTRUCTION
:OPERATION #<FUNCTION ADDR>
:A 1
:B 2
:C 2)
#S(INSTRUCTION
:OPERATION #<FUNCTION SETI>
:A 5
:B 2
:C 2))
:IP 2
:REGISTERS #(0 0 0 0 0 0))
(def-suite aoc.2018.21)
(in-suite aoc.2018.21)
(run! 'aoc.2018.21)Running test suite AOC.2018.21 Didn't run anything...huh?