feat(tazjin/aoc2020): Add solution for day 8, part 2 r/1995

Change-Id: I03f46faf9b5b1b578b1131ecd08746f1adc3e87f
Reviewed-on: https://cl.tvl.fyi/c/depot/+/2243
Reviewed-by: tazjin <mail@tazj.in>
Tested-by: BuildkiteCI

1 files changed, 44 insertions, 14 deletions

diff --git a/users/tazjin/aoc2020/solution-day8.el b/users/tazjin/aoc2020/solution-day8.el
index eb84badde3..591a07fbf3 100644
--- a/users/tazjin/aoc2020/solution-day8.el
+++ b/users/tazjin/aoc2020/solution-day8.el
@@ -13,21 +13,51 @@
                    (s-lines (s-chomp (f-read "/tmp/aoc/day8.txt"))))))
 
 (defun day8/step (code position acc)
-  (let ((current (aref code position)))
-    (aset code position nil)
-    (pcase current
-      ('() (cons 'final acc))
-      (`(nop . ,val) (cons (+ position 1) acc))
-      (`(acc . ,val) (cons (+ position 1) (+ acc val)))
-      (`(jmp . ,val) (cons (+ position val) acc)))))
+  (if (>= position (length code))
+      (cons 'final acc)
+
+    (let ((current (aref code position)))
+      (aset code position :done)
+      (pcase current
+        (:done (cons 'loop acc))
+        (`(nop . ,val) (cons (+ position 1) acc))
+        (`(acc . ,val) (cons (+ position 1) (+ acc val)))
+        (`(jmp . ,val) (cons (+ position val) acc))))))
 
 ;; Puzzle 1
 
 (message "Solution to day8/1: %s"
- (let ((code (copy-sequence day8/input))
-       (position 0)
-       (acc 0))
-   (cl-loop for next = (day8/step code position acc)
-            when (equal 'final (car next)) return (cdr next)
-            do (setq position (car next))
-            do (setq acc (cdr next)))))
+         (let ((code (copy-sequence day8/input))
+               (position 0)
+               (acc 0))
+           (cl-loop for next = (day8/step code position acc)
+                    when (equal 'loop (car next)) return (cdr next)
+                    do (setq position (car next))
+                    do (setq acc (cdr next)))))
+
+;; Puzzle 2
+
+(defun day8/flip-at (code pos)
+  (pcase (aref code pos)
+    (`(nop . ,val) (aset code pos `(jmp . ,val)))
+    (`(jmp . ,val) (aset code pos `(nop . ,val)))
+    (other (error "Unexpected flip op: %s" other))))
+
+(defun day8/try-flip (flip-at code position acc)
+  (day8/flip-at code flip-at)
+  (cl-loop for next = (day8/step code position acc)
+           when (equal 'loop (car next)) return nil
+           when (equal 'final (car next)) return (cdr next)
+           do (setq position (car next))
+           do (setq acc (cdr next))))
+
+(message "Solution to day8/2: %s"
+         (let ((flip-options (cl-loop for op being the elements of day8/input
+                                      using (index idx)
+                                      for opcode = (car op)
+                                      when (or (equal 'nop opcode)
+                                               (equal 'jmp opcode))
+                                      collect idx)))
+           (cl-loop for flip-at in flip-options
+                    for result = (day8/try-flip flip-at (copy-sequence day8/input) 0 0)
+                    when result return result)))