2020 day8 part1

3 files changed, 108 insertions, 1 deletions

diff --git a/src/2020/day8/README.md b/src/2020/day8/README.md
index d31f59e..2901c0d 100644
--- a/src/2020/day8/README.md
+++ b/src/2020/day8/README.md
@@ -44,4 +44,40 @@ Immediately before the program would run an instruction a second time, the value
 
 Run your copy of the boot code. Immediately before any instruction is executed a second time, what value is in the accumulator?
 
+--- Part Two ---
 
+After some careful analysis, you believe that exactly one instruction is corrupted.
+
+Somewhere in the program, either a jmp is supposed to be a nop, or a nop is supposed to be a jmp. (No acc instructions were harmed in the corruption of this boot code.)
+
+The program is supposed to terminate by attempting to execute an instruction immediately after the last instruction in the file. By changing exactly one jmp or nop, you can repair the boot code and make it terminate correctly.
+
+For example, consider the same program from above:
+
+nop +0
+acc +1
+jmp +4
+acc +3
+jmp -3
+acc -99
+acc +1
+jmp -4
+acc +6
+
+If you change the first instruction from nop +0 to jmp +0, it would create a single-instruction infinite loop, never leaving that instruction. If you change almost any of the jmp instructions, the program will still eventually find another jmp instruction and loop forever.
+
+However, if you change the second-to-last instruction (from jmp -4 to nop -4), the program terminates! The instructions are visited in this order:
+
+nop +0  | 1
+acc +1  | 2
+jmp +4  | 3
+acc +3  |
+jmp -3  |
+acc -99 |
+acc +1  | 4
+nop -4  | 5
+acc +6  | 6
+
+After the last instruction (acc +6), the program terminates by attempting to run the instruction below the last instruction in the file. With this change, after the program terminates, the accumulator contains the value 8 (acc +1, acc +1, acc +6).
+
+Fix the program so that it terminates normally by changing exactly one jmp (to nop) or nop (to jmp). What is the value of the accumulator after the program terminates?
diff --git a/src/2020/day8/aoc.cpp b/src/2020/day8/aoc.cpp
index 849bad9..830141a 100644
--- a/src/2020/day8/aoc.cpp
+++ b/src/2020/day8/aoc.cpp
@@ -1,5 +1,33 @@
 #include "aoc.h"
+#include <vector>
 
 namespace aoc2020 {
 
+static void run(size_t index, std::vector<code>& cs, int* accumlator) {
+  auto& code = cs[index];
+  if (code.executed == 0) {
+    size_t next = index + 1;
+    if (code.type == acc) {
+      *accumlator += code.value;
+    }
+    if (code.type == jmp) {
+      next = index + code.value;
+    }
+    code.executed += 1;
+    run(next, cs, accumlator);
+  }
 }
+
+int day8(line_view file) {
+  std::vector<code> cs;
+  int accumlator = 0;
+  per_line(file, [&cs](line_view lv) {
+    cs.emplace_back(lv);
+    return true;
+  });
+
+  run(0, cs, &accumlator);
+  return accumlator;
+}
+
+} // namespace aoc2020
diff --git a/src/2020/day8/aoc.h b/src/2020/day8/aoc.h
index c5ad3d1..ae2b8ee 100644
--- a/src/2020/day8/aoc.h
+++ b/src/2020/day8/aoc.h
@@ -3,4 +3,47 @@
 
 namespace aoc2020 {
 
-}
+enum code_t {
+  nop,
+  jmp,
+  acc,
+};
+
+struct code {
+  code_t type;
+  int value;
+  int executed = 0;
+
+  void get_number(const char** pp, int* d) {
+    const char* p = *pp;
+    int sign = *p == '+' ? 1 : -1;
+    p += 1;
+    *d = 0;
+    while (*p >= '0' && *p <= '9') {
+      *d = *d * 10 + *p - '0';
+      p++;
+    }
+    *d *= sign;
+    *pp = p;
+  }
+
+  code(line_view lv) {
+    const char* p = lv.line;
+    if (*p == 'a')
+      type = acc;
+    if (*p == 'n')
+      type = nop;
+    if (*p == 'j')
+      type = jmp;
+    while (p < lv.line + lv.length) {
+      if (*p == '+' || *p == '-') {
+        get_number(&p, &value);
+      }
+      p++;
+    }
+  }
+};
+
+int day8(line_view);
+
+} // namespace aoc2020