Add day 08

[adventofcode2020.git] / src / day08.lisp

diff --git a/src/day08.lisp b/src/day08.lisp
new file mode 100644 (file)
index 0000000..8d8f7c8
--- /dev/null
+++ b/src/day08.lisp
@@ -0,0 +1,99 @@
+(asdf:load-system :adventofcode2020)
+(in-package #:adventofcode2020)
+(named-readtables:in-readtable fn-reader)
+
+(defun make-program (insts)
+  (let ((len (length insts))
+        (parse-inst (lambda (inst)
+                      (cl-ppcre:register-groups-bind
+                        (code (#'parse-integer imm)) 
+                        ("([a-z]{3}) ([-+][0-9]+)" inst)
+                        (list code imm)))))
+   (list 
+     :ptr 0
+     :acc 0
+     :mem (make-array len :initial-contents (mapcar parse-inst insts))
+     :vis (make-array len :element-type 'bit))))
+
+(defun step-program (program)
+  (let ((ptr (getf program :ptr))
+        (mem (getf program :mem))
+        (acc (getf program :acc)))
+    (if (= ptr (length mem))
+        (setf (getf program :stop) 1)
+        (if (= 1 (bit (getf program :vis) ptr))
+            (setf (getf program :stop) 2)
+            (destructuring-bind (code imm) (aref mem ptr)
+              (cond ((string= code "nop") 
+                     (setf (getf program :ptr) (1+ ptr)))
+                    ((string= code "acc")
+                     (progn
+                       (setf (getf program :ptr) (1+ ptr))
+                       (setf (getf program :acc) (+ acc imm))))
+                    ((string= code "jmp") 
+                     (setf (getf program :ptr) (+ ptr imm))))
+              (setf (bit (getf program :vis) ptr) 1))))
+    program))
+
+(defun run-until-stop (program)
+  (if (getf program :stop)
+      (values (getf program :acc) (getf program :stop))
+      (run-until-stop (step-program program))))
+
+(defun run-with-fix (program i)
+  (let ((fixing (aref (getf program :mem) i))
+        (fix-code (lambda (inst)
+                    (destructuring-bind (code imm) inst
+                      (cond ((string= code "nop") (list "jmp" imm))
+                            ((string= code "jmp") (list "nop" imm)))))))
+    (setf (aref (getf program :mem) i) (funcall fix-code fixing))
+    (multiple-value-bind (acc stop) (run-until-stop program)
+      (setf (aref (getf program :mem) i) fixing)
+      (setf (getf program :stop) nil)
+      (setf (getf program :ptr) 0)
+      (setf (getf program :acc) 0)
+      (setf (getf program :vis) (make-array (length (getf program :mem)) :element-type 'bit))
+      (if (= stop 1) 
+          acc
+          most-negative-fixnum))))
+
+(defun find-fixed-result (program)
+  (loop for i from 0 below (length (getf program :mem))
+        unless (string= "acc" (first (aref (getf program :mem) i)))
+        maximizing (run-with-fix program i)))
+
+(day 08 input
+  (let ((program (make-program (list-from input))))
+    (part1 (run-until-stop program))
+    (part2 (find-fixed-result program))))
+
+(def-suite day08)
+(in-suite day08)
+
+(defvar *simple-instructions*
+  '("nop +0" 
+    "acc +1" 
+    "jmp +4" 
+    "acc +3" 
+    "jmp -3" 
+    "acc -99" 
+    "acc +1" 
+    "jmp -4"
+    "acc +6"))
+
+(test run-until-stop
+  (is (equal
+        5
+        (run-until-stop (make-program *simple-instructions*)))))
+
+(test run-with-fix
+  (is (equal
+        8
+        (run-with-fix (make-program *simple-instructions*) 7))))
+
+(test find-fixed-result
+  (is (equal
+        8
+        (find-fixed-result (make-program *simple-instructions*)))))
+
+(run! 'day08)