Day 8: Handheld Halting

Basic processor has an instruction pointer that tracks what it's paying attention to. That will move around to different locations in memory. We also care about exactly one value, the accumulator, which can store numbers. Once that was working, I just added something to track which memory locations had been accessed already and told the processor to kill the process if it ever looped.

memory = input_data.split('\n')

instruction_pointer = 0
accumulator  = 0

instructions_executed = []

while instruction_pointer < len(memory):
    if instruction_pointer in instructions_executed:
        break
    else:
        instructions_executed.append(instruction_pointer)
    opp, argument = memory[instruction_pointer].split(' ')
    if opp == 'nop':
        instruction_pointer = instruction_pointer + 1
    elif opp == 'acc':
        accumulator = accumulator + int(argument)
        instruction_pointer = instruction_pointer + 1
    elif opp == 'jmp':
        instruction_pointer = instruction_pointer + int(argument)
print(accumulator)

For this I took my original processor and turned it into a method. Then I ran it a bunch of times changing one line at at time.

def simulate(memory):
    instruction_pointer = 0
    accumulator  = 0

    instructions_executed = []
    terminated = True

    while instruction_pointer < len(memory):
        if instruction_pointer in instructions_executed:
            terminated = False
            break
        else:
            instructions_executed.append(instruction_pointer)
        opp, argument = memory[instruction_pointer].split(' ')
        if opp == 'nop':
            instruction_pointer = instruction_pointer + 1
        elif opp == 'acc':
            accumulator = accumulator + int(argument)
            instruction_pointer = instruction_pointer + 1
        elif opp == 'jmp':
            instruction_pointer = instruction_pointer + int(argument)
        else:
            print('something fucked up')
    return terminated, accumulator
memory = input_data.split('\n')

for index, row in enumerate(memory):
    mem_copy = list(memory)
    terminated = None
    if 'nop' in row:
        mem_copy[index] = 'jmp' + mem_copy[index][3:]
        terminated, result = simulate(mem_copy)
    elif 'jmp' in row:
        mem_copy[index] = 'nop' + mem_copy[index][3:]
        terminated, result = simulate(mem_copy)
    else:
        pass
    if terminated:
        print(result)

• This is sort of how a processor works at a very low level. You want to read in an instruction one at a time, Do SOMETHING based on the code you get, and then move on. You'll need to define different actions for different opp codes.

• If it's anything like last year, they'll add on to this before the month is over, so consider spending extra time to make sure you understand it and will be able to modify it in the future.

• When you're changing the set of instructions for part B you need to make absolutely sure each test run only has 1 change. If you're not careful, you might end up accidentally applying multiple changes which will fuck up your results. Sometimes when you think you've copied data, you just actually just made a new variable that points to the exact same data. So if you change it, the changes will affect the original. There are ways around this, like in python you can copy a list by casting it as a list. For example in Python list_b = list_a would point to the same list. If you change one of them, the other will be affected. list_b = list(list_a) would create a new list with a copy of the original data. So now you can change them independently of each other. This distinction is known as copy by reference vs copy by value

• If you want to look ahead (assuming this does get reused, which isn't certain) you might want to look at some of the problems and solutions from last year.

def terminates(mySet, acc, ind, changed):
  if ind in mySet or ind >= len(lines):
    return (False, acc)
  mySet.add(ind)
  line = lines[ind]
  op, val = line.split(" ")
  if op == "acc":
    acc += int(val)
    ind += 1
  if op == "jmp":
    if not changed:
      t, a = terminates(copy(mySet), acc, ind + 1, True)
      if t: return (True, a)
    ind += int(val)
  if op == "nop":
    if not changed:
      t, a = terminates(copy(mySet), acc, ind + int(val), True)
      if t: return (True, a)
    ind += 1
  if ind >= len(lines):
    return (True, acc)
  return terminates(mySet, acc, ind, changed)

print(terminates(found, 0, 0, False))

from pprint import pprint
import sys


def parse_input(input_path):
    instructions = []
    with open(input_path) as input_file:
        for line in input_file:
            instruction, argument = line.split(' ')
            instructions.append((instruction, (int(argument))))

    return instructions


def evaluate(instructions):
    accumulator = 0
    pc = 0
    visited = set()
    while True:
        if pc in visited:
            return accumulator

        visited.add(pc)
        instruction, argument = instructions[pc]
        if instruction == 'acc':
            accumulator += argument
            pc += 1
        elif instruction == 'jmp':
            pc += argument
        elif instruction == 'nop':
            pc += 1
        else:
            raise ValueError(instruction)


def main():
    instructions = parse_input(sys.argv[1])
    pprint(instructions)

    result = evaluate(instructions)
    print(result)


if __name__ == '__main__':
    main()

--- 008a.py     2020-12-07 21:11:47.490915646 -0800
+++ 008b.py     2020-12-07 21:34:14.285000689 -0800
@@ -18,7 +18,7 @@
     visited = set()
     while True:
         if pc in visited:
-            return accumulator
+            raise ValueError()

         visited.add(pc)
         instruction, argument = instructions[pc]
@@ -32,12 +32,31 @@
         else:
             raise ValueError(instruction)

+        if pc >= len(instructions):
+            return accumulator
+

 def main():
     instructions = parse_input(sys.argv[1])
     pprint(instructions)

-    result = evaluate(instructions)
+    result = None
+
+    for i, (instruction, argument) in enumerate(instructions):
+        if instruction == 'acc':
+            print(f'line {i+1}: acc')
+            continue
+
+        opposite = 'jmp' if instruction == 'nop' else 'nop'
+        modified_instructions = instructions.copy()
+        modified_instructions[i] = (opposite, argument)
+        try:
+            result = evaluate(modified_instructions)
+            print(f'line {i+1}: {result}')
+        except ValueError:
+            print(f'line {i+1}: infinite loop')
+            pass
+
     print(result)

#![feature(str_split_once)]
use std::collections::HashSet;

#[derive(PartialEq, Eq, Copy, Clone)]
pub enum BootCodeOperation {
    Acc,
    Jmp,
    Nop,
}

pub type InstructionArgument = i64;

#[derive(PartialEq, Eq, Copy, Clone)]
pub struct BootCodeInstruction {
    pub operation: BootCodeOperation,
    pub argument: InstructionArgument,
}

impl BootCodeInstruction {
    pub fn from_line(line: &str) -> BootCodeInstruction {
        let (op_str, arg_str) = line.split_once(' ').unwrap();

        let operation = match op_str {
            "nop" => BootCodeOperation::Nop,
            "acc" => BootCodeOperation::Acc,
            "jmp" => BootCodeOperation::Jmp,
            _ => panic!("Invalid op code")
        };

        let argument = arg_str.parse::<i64>().unwrap();

        BootCodeInstruction { operation, argument }
    }
}

pub type Program = Vec<BootCodeInstruction>;

pub fn load_program(lines: &Vec<String>) -> Program {
    lines.iter().map(|x| BootCodeInstruction::from_line(x)).collect()
}

pub struct State {
    program: Program,
    instruction_pointer: usize,
    acc: i64,
}

impl State {
    pub fn new(program: Program) -> State {
        State { program, instruction_pointer: 0, acc: 0 }
    }

    pub fn tick(&mut self) -> (i64, Option<usize>) {
        let current_instruction = self.program[self.instruction_pointer];

        match current_instruction.operation {
            BootCodeOperation::Acc => {
                self.acc += current_instruction.argument;
                self.instruction_pointer += 1;
            },
            BootCodeOperation::Jmp => {
                self.instruction_pointer = (
                    self.instruction_pointer as i64 + current_instruction.argument
                ) as usize;
            },
            BootCodeOperation::Nop => {
                self.instruction_pointer += 1;
            }
        }

        let next_instruction = match self.instruction_pointer >= self.program.len() {
            true => None,
            false => Some(self.instruction_pointer),
        };

        (self.acc, next_instruction)
    }
}

pub fn loop_detecting_runner(mut state: State) -> (bool, i64) {
    let mut executed_instructions = HashSet::new();

    while let (acc, Some(next_instruction)) = state.tick() {
        if executed_instructions.contains(&next_instruction) {
            return (true, acc);
        } else {
            executed_instructions.insert(next_instruction);
        }
    }

    (false, state.acc)
}

use std::io;
use std::io::prelude::*;

use day8::*;

fn part1(lines: &Vec<String>) -> i64 {
    let program = load_program(&lines);
    let state = State::new(program);

    let (_loop_detected, acc) = loop_detecting_runner(state);

    acc
}

fn part2(lines: &Vec<String>) -> i64 {
    let program = load_program(&lines);

    for (i, instr) in program.iter().enumerate() {
        let mut new_program = program.clone();
        match instr.operation {
            BootCodeOperation::Nop => {
                new_program[i].operation = BootCodeOperation::Jmp;
            },
            BootCodeOperation::Jmp => {
                new_program[i].operation = BootCodeOperation::Nop;
            },
            BootCodeOperation::Acc => {},
        }

        let state = State::new(new_program);

        let (loop_detected, acc) = loop_detecting_runner(state);

        if !loop_detected {
            return acc;
        }
    }

    panic!();
}

fn main() {
    let stdin = io::stdin();
    let lines: Vec<String> = stdin
        .lock()
        .lines()
        .collect::<Result<_, _>>()
        .unwrap();

    println!("Part 1: {}", part1(&lines));
    println!("Part 2: {}", part2(&lines));
}

#!/usr/bin/env python3

import sys

def follow(instr):
    current = 0
    acc = 0

    while instr[current][0] != 'DID':
        if instr[current][0] == 'nop':
            instr[current][0] = "DID"
            current += 1
        elif instr[current][0] == 'acc':
            acc += instr[current][1]
            instr[current][0] = "DID"
            current += 1
        elif instr[current][0] == 'jmp':
            instr[current][0] = "DID"
            current += instr[current][1]

    return acc

def main():
    instr = []
    for line in sys.stdin:
        instr.append(line.strip().split())
        instr[-1][1] = int(instr[-1][1])

    print(follow(instr))

if __name__ == '__main__':
    main()

#!/usr/bin/env python3

import sys

def follow(instr):
    visited = []
    current = 0
    acc = 0

    while current not in visited:
        if current == len(instr) - 1:
            return acc, current
        if instr[current][0] == 'nop':
            visited.append(current)
            current += 1
        elif instr[current][0] == 'acc':
            acc += instr[current][1]
            visited.append(current)
            current += 1
        elif instr[current][0] == 'jmp':
            visited.append(current)
            current += instr[current][1]

    return acc, current

def find_success(instr):
    finish = len(instr) - 1

    for i in instr:
        if i[0] == 'nop':
            i[0] = 'jmp'
            acc, fin = follow(instr)
            if fin == finish:
                return acc
            i[0] = 'nop'
        elif i[0] == 'jmp':
            i[0] = 'nop'
            acc, fin = follow(instr)
            i[0] = 'jmp'
            if fin == finish:
                return acc

def main():
    instr = []
    for line in sys.stdin:
        instr.append(line.strip().split())
        instr[-1][1] = int(instr[-1][1])

    print(find_success(instr))

if __name__ == '__main__':
    main()

#!/usr/local/bin/csi -s
(import
 (chicken format)
 (chicken io)
 (srfi 133))

(define (read-input #!optional (port (current-input-port)))
  (let loop ((input (read-list port))
             (acc '()))
    (if (null? input)
        (reverse-list->vector acc)
        (loop (cddr input) (cons (vector (car input) (cadr input) #f) acc)))))

(define (reset-instructions! instructions)
  (vector-for-each (cut vector-set! <> 2 #f) instructions))

(define (solve1 instructions)
  (let loop ((accumulator 0)
             (ip 0))
    (if (>= ip (vector-length instructions))
        (values #t accumulator)
        (let ((insn (vector-ref instructions ip)))
          (if (vector-ref insn 2)
              (values #f accumulator)
              (begin
                (vector-set! insn 2 #t)
                (case (vector-ref insn 0)
                  ((nop) (loop accumulator (add1 ip)))
                  ((acc) (loop (+ accumulator (vector-ref insn 1)) (add1 ip)))
                  ((jmp) (loop accumulator (+ ip (vector-ref insn 1)))))))))))

(define (flip-and-try instructions ip from to)
  (vector-set! (vector-ref instructions ip) 0 to)
  (let-values (((terminated? acc) (solve1 instructions)))
    (vector-set! (vector-ref instructions ip) 0 from)
    (values terminated? acc)))

(define (solve2 instructions)
  (let loop ((ip 0))
    (reset-instructions! instructions)
    (if (>= ip (vector-length instructions))
        #f
        (case (vector-ref (vector-ref instructions ip) 0)
          ((acc) (loop (add1 ip)))
          ((nop jmp) =>
           (lambda (op)
             (let*-values (((from to) (if (eq? op 'nop)
                                          (values 'nop 'jmp)
                                          (values 'jmp 'nop)))
                           ((terminated? acc)
                            (flip-and-try instructions ip from to)))
               (if terminated?
                   acc
                   (loop (add1 ip))))))))))

(define instructions (read-input))
(let-values (((_ accumulator) (solve1 instructions)))
  (printf "Part 1: ~A~%" accumulator))
(printf "Part 2: ~A~%" (solve2 instructions))

I took a more stateful and possibly more enterprisey approach with this problem and made a class. The solution is more verbose than the others here, but I hope the additional structure will make it easier to modify and extend for future use (should we come across another IntCode problem).

import sys

# Class

class Console:
    def __init__(self):
        self.accumulator = 0
        self.code        = []
        self.counter     = 0
        self.operations  = {
            'nop': self.do_nop,
            'acc': self.do_acc,
            'jmp': self.do_jmp,
        }

    def load(self, stream=sys.stdin):
        for line in sys.stdin:
            operation, argument = line.strip().split()
            self.code.append((
                operation, int(argument)
            ))

    def do_nop(self, argument):
        self.counter += 1
    
    def do_acc(self, argument):
        self.accumulator += argument
        self.counter     += 1

    def do_jmp(self, argument):
        self.counter += argument

    def run(self):
        history = set()
        while self.counter not in history and self.counter < len(self.code):
            history.add(self.counter)
            operation, argument = self.code[self.counter]
            self.operations[operation](argument)

# Main Execution

def main():
    console = Console()
    console.load()
    console.run()

    print(console.accumulator)

if __name__ == '__main__':
    main()

For the second part, I just brute-forced the solution by modifying each nop or jmp instruction (one at a time) and checking if the console terminates. I'm just putting a diff here because the code is already pretty long, but the full source can be found in the Repo Link.

--- day08-A.py	2020-12-08 08:48:55.067011484 -0500
+++ day08-B-stripped.py	2020-12-08 09:11:51.343416414 -0500
@@ -32,20 +32,38 @@
     def do_jmp(self, argument):
         self.counter += argument
 
-    def run(self):
+    def run(self, reset=False):
+        if reset:
+            self.accumulator = 0
+            self.counter     = 0
+
         history = set()
         while self.counter not in history and self.counter < len(self.code):
             history.add(self.counter)
             operation, argument = self.code[self.counter]
             self.operations[operation](argument)
 
+        return self.counter >= len(self.code)
+
 # Main Execution
 
 def main():
     console = Console()
     console.load()
-    console.run()
 
+    original_code = console.code[:]
+    for instruction, (operation, argument) in enumerate(original_code):
+        if operation == 'nop':
+            continue
+
+        new_operation             = 'jmp' if operation == 'nop' else 'nop'
+        console.code[instruction] = (new_operation, argument)
+
+        if console.run(reset=True):
+            break
+
+        console.code[instruction] = (operation, argument)
+            
     print(console.accumulator)
 
 if __name__ == '__main__':

use i16 as Number;
use std::collections::HashSet;
use std::time::Instant;

#[derive(Copy, Clone)]
pub enum Instruction {
    Nop,
    Acc(Number),
    Jmp(Number),
}

impl From<&str> for Instruction {
    fn from(input: &str) -> Self {
        // let x: Vec<&str> = input.split(" ").collect();

        let cmd = &input[0..3];
        let my_val = input[4..].parse::<Number>().unwrap();

        match cmd {
            "nop" => Instruction::Nop,
            "acc" => Instruction::Acc(my_val),
            "jmp" => Instruction::Jmp(my_val),
            _ => panic!(),
        }
    }
}

pub struct GameConsole {
    pc: Number,
    accumulator: Number,
    instructions: Vec<Instruction>,
}

impl GameConsole {
    pub fn from_instructions(input: Vec<Instruction>) -> Self {
        Self {
            pc: 0,
            accumulator: 0,
            instructions: input,
        }
    }

    pub fn step(&mut self) -> Option<Number> {
        let pc = self.pc as usize;
        match &self.instructions.get(pc)? {
            Instruction::Nop => {}
            Instruction::Acc(x) => self.accumulator += x,
            Instruction::Jmp(x) => self.pc += x - 1,
        }

        self.pc += 1;
        if self.instructions.get(self.pc as usize).is_some() {
            Some(self.pc)
        } else {
            None
        }
    }

    pub fn first_unrepeated(&mut self) -> Option<Number> {
        let mut h = HashSet::<Number>::new();
        while let Some(x) = self.step() {
            if !h.insert(x) {
                return Some(self.accumulator);
            }
        }
        None
    }
}

struct SwapIter<'a> {
    vec: Vec<Instruction>,
    input: Vec<&'a str>,
    last: usize,
}
impl Iterator for SwapIter<'_> {
    type Item = Vec<Instruction>;

    fn next(&mut self) -> Option<Self::Item> {
        for (idx, elem) in self.input.iter().enumerate().skip(self.last) {
            let cmd = &elem[0..3];

            self.last += 1;

            if let Some(v) = match cmd {
                "jmp" => Some("nop"),
                "nop" => Some("jmp"),
                _ => None,
            } {
                let mut new_lines = self.vec.clone();
                let binding: &str = &self.input[idx].replace(cmd, v);
                new_lines[idx] = binding.into();

                return Some(new_lines);
            }
        }

        None
    }
}

fn generate_alternative_inputs(input: &str) -> SwapIter {
    let lines = input
        .lines()
        .into_iter()
        // .map(Into::into)
        .collect::<Vec<&str>>();

    let vec = lines.iter().map(|&x| x.into()).collect();
    SwapIter { input: lines, last: 0, vec }
}

fn part_1(input: &str) -> Option<Number> {
    let p1 = input
        .lines()
        .into_iter()
        .map(Into::into)
        .collect::<Vec<Instruction>>();

    let mut gc = GameConsole::from_instructions(p1);
    gc.first_unrepeated()
}

fn part_2(input: &str) -> Option<Number> {
    let generator = generate_alternative_inputs(input);

    let consoles = generator.map(GameConsole::from_instructions);

    for mut console in consoles {
        if console.first_unrepeated().is_none() {
            return Some(console.accumulator);
        }
    }

    None
}

fn main() {
    // 1451, 1160
    let input = std::fs::read_to_string("input/08.txt").unwrap();
    let start = Instant::now();
    println!("{} in {:?}", part_1(&input).unwrap(), Instant::now() - start);
    println!("{} in {:?}", part_2(&input).unwrap(), Instant::now() - start);
}

1451 in 82µs
1160 in 3.1124ms

(define (get-lines parse-line file)
  (with-input-from-file file
    (lambda ()
      (let loop ((line (read-line))
                 (lines '()))
        (if (eof-object? line)
            (reverse lines)
            (loop (read-line)
                  (cons (parse-line line) lines)))))))

(define (make-ins op val) (cons op val))
(define (get-op ins) (car ins))
(define (get-val ins) (cdr ins))

(define (parse-ins line)
  (let* ((split ((string-splitter) line))
         (op (string->symbol (car split)))
         (val (string->number (cadr split))))
    (make-ins op val)))

(define (execute ins-lst)
  (let loop ((acc 0)
             (counter 0)
             (visited '()))
    (cond ((member counter visited) (cons 'loop acc))
          ((= counter (length ins-lst)) (cons 'ok acc))
          (else (let* ((ins (list-ref ins-lst counter))
                       (op (get-op ins))
                       (val (get-val ins)))
                  (case op
                    ((nop) (loop acc
                                 (+ counter 1)
                                 (cons counter visited)))
                    ((acc) (loop (+ acc val)
                                 (+ counter 1)
                                 (cons counter visited)))
                    ((jmp) (loop acc
                                 (+ counter val)
                                 (cons counter visited)))))))))

(define (one ins-lst)
  (cdr (execute ins-lst)))

(define (flip-ins ins)
  (let ((op (get-op ins))
        (val (get-val ins)))
    (make-ins (if (eq? op 'jmp) 'nop 'jmp)
              val)))

(define (replace-n lst val n)
  (cond ((null? lst) '())
        ((= n 0) (cons val (cdr lst)))
        (else (cons (car lst)
                    (replace-n (cdr lst)
                               val
                               (- n 1))))))

(define (two ins-lst)
  (let loop ((ins-change-pairs
              (filter-map (lambda (i ins)
                            (and (or (eq? (get-op ins) 'jmp)
                                     (eq? (get-op ins) 'nop))
                                 (cons i (flip-ins ins))))
                          (iota (length ins-lst))
                          ins-lst)))
    (let* ((rep-index (caar ins-change-pairs))
           (rep-ins (cdar ins-change-pairs))
           (ex-res (execute (replace-n ins-lst rep-ins rep-index))))
      (if (eq? (car ex-res) 'ok)
          (cdr ex-res)
          (loop (cdr ins-change-pairs))))))

(define (run lines)
    (display "One: ")
    (display (one lines))
    (newline)
    (display "Two: ")
    (display (two lines))
    (newline))

(run (get-lines parse-ins "input"))

pub mod assemblyvm {

    #[derive(Clone)]
    pub struct Instruction {
        pub instr: String,
        pub value: i64,
        pub runs: u64,
    }
    impl From<&String> for Instruction {
        fn from(input: &String) -> Self {
            let mut parts = input.split_ascii_whitespace();
            Self {
                instr: parts.next().unwrap().parse().unwrap(),
                value: parts.next().unwrap().parse().unwrap(),
                runs: 0,
            }
        }
    }

    #[derive(Clone)]
    pub struct AssemblyVM {
        pub ptr: i64,
        pub accum: i64,
        pub code: Vec<Instruction>,
        pub code_default: Vec<Instruction>,
        pub loop_detected: bool,
        pub active: bool,
        // Options
        pub break_on_loop: bool,
        pub debug: bool,
    }
    impl AssemblyVM {
        pub fn new(code: Vec<String>) -> Self {
            let code: Vec<_> = code.iter().map(Instruction::from).collect();

            Self {
                ptr: 0,
                accum: 0,
                code: code.clone(),
                code_default: code.clone(),
                loop_detected: false,
                active: true,
                // Options
                break_on_loop: false,
                debug: false,
            }
        }

        pub fn reset(&mut self) {
            self.ptr = 0;
            self.accum = 0;
            self.code = self.code_default.clone();
            self.loop_detected = false;
            self.active = false;
        }
    
        pub fn run(&mut self) {
            self.active = true;
            loop {
                let ptr = self.ptr as usize;
                if ptr >= self.code.len() { break; }
                let instr = &self.code[ptr];
                if self.break_on_loop && self.code[ptr].runs == 1 {
                    self.loop_detected = true;
                    self.active = false;
                    break;
                }
                
                match instr.instr.as_ref() {
                    "acc" => { self.accum += instr.value; self.ptr += 1; },
                    "jmp" => self.ptr += instr.value,
                    "nop" => self.ptr += 1,
                    other => panic!("ERROR: Unknown instruction: {}", other),
                }
                self.code[ptr].runs += 1;
            } 
        }
    }
}

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::time::Instant;

use assemblyvm::assemblyvm::AssemblyVM;
extern crate assemblyvm;

fn day08(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    // Initialize & Configure VM
    let mut vm = AssemblyVM::new(input);
    vm.break_on_loop = true;
    vm.run();
    println!("Part 1: {}", vm.accum); // 1087
    vm.reset();

    // Part 2
    for i in 0..vm.code.len() {
        match vm.code[i].instr.as_ref() {
            "acc" => continue,
            "jmp" => vm.code[i].instr = "nop".to_string(),
            "nop" => vm.code[i].instr = "jmp".to_string(),
            other => unreachable!("Fail: {}", other),
        };
        vm.run();
        if !vm.loop_detected { break; }
        vm.reset();
    }
    println!("Part 2: {}", vm.accum); // 780
    
    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    let start = Instant::now();
    day08(&filename).unwrap();
    println!("Total time: {:?}", Instant::now() - start);
}

const fs = require('fs');
const readline = require('readline');

let bootCodeArray = []

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		bootCodeArray.push(line);
	}
}

function parseLine(line) {
	let regex = /^(\w+) ([+-]\d+)$/;
	let found = line.match(regex);
	let action = found[1];
	let amount = parseInt(found[2]);
	return { action, amount };
}

class ExecutionError extends Error {}

function executeLine(parsedLine) {
	switch (parsedLine.action) {
		case 'nop': return { acc: 0, shift: 1 };
		case 'jmp': return { acc: 0, shift: parsedLine.amount };
		case 'acc': return { acc: parsedLine.amount, shift: 1 };
		default: return new ExecutionError("Error parsing execution from line " + parsedLine);
	}
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	let accumulator = 0;
	let operatingIndex = 0;
	let indexHistory = [];
	while (true) {
		if (indexHistory.includes(operatingIndex)) {
			console.log("Finished after " + indexHistory.length + " steps! Accumulator value is " + accumulator);
			return;
		}
		let currentInstruction = executeLine(parseLine(bootCodeArray[operatingIndex]));
		indexHistory.push(operatingIndex);
		accumulator += currentInstruction.acc;
		operatingIndex += currentInstruction.shift;
	}
})();

const fs = require('fs');
const readline = require('readline');

let bootCodeArray = []

async function openFileForReading(file) {
	const fileStream = fs.createReadStream(file);

	const rl = readline.createInterface({
		input: fileStream,
		crlfDelay: Infinity
	});

	for await (const line of rl) {
		bootCodeArray.push(line);
	}
}

function parseLine(line) {
	let regex = /^(\w+) ([+-]\d+)$/;
	let found = line.match(regex);
	let action = found[1];
	let amount = parseInt(found[2]);
	return { action, amount };
}

class ExecutionError extends Error {}

function executeLine(parsedLine) {
	switch (parsedLine.action) {
		case 'nop': return { acc: 0, shift: 1 };
		case 'jmp': return { acc: 0, shift: parsedLine.amount };
		case 'acc': return { acc: parsedLine.amount, shift: 1 };
		default: return new ExecutionError("Error parsing execution from line " + parsedLine);
	}
}

(async function mainExecution() {
	await openFileForReading('input.txt');
	let jmpNopArray = [];
	let tmpIndex = 0;
	for (const line of bootCodeArray) {
		let parsed = parseLine(line);
		if (parsed.action == 'nop' || parsed.action == 'jmp') {
			jmpNopArray.push(tmpIndex);
		}
		tmpIndex++;
	}
	let accumulator = 0;
	let operatingIndex = 0;
	let indexHistory = [];
	let completeRunning = false;
	let jmpNopIndex = 0;
	while (true && !completeRunning) {
		if (operatingIndex >= bootCodeArray.length) {
			console.log("Finished running in " + indexHistory.length + " steps by changing instruction # " + jmpNopArray[jmpNopIndex] + ", accumulator value is " + accumulator);
			return;
		}
		if (indexHistory.includes(operatingIndex)) {
			// infinite loop, restart
			accumulator = 0;
			operatingIndex = 0;
			indexHistory = [];
			jmpNopIndex++;
			continue;
		}
		let currentInstruction = executeLine(parseLine(bootCodeArray[operatingIndex]));
		if (operatingIndex == jmpNopArray[jmpNopIndex]) {
			let parsed = parseLine(bootCodeArray[operatingIndex]);
			if (parsed.action == 'nop') {
				currentInstruction = executeLine({ action: 'jmp', amount: parsed.amount });
			} else if (parsed.action == 'jmp') {
				currentInstruction = executeLine({ action: 'nop', amount: parsed.amount });
			}
		}
		indexHistory.push(operatingIndex);
		accumulator += currentInstruction.acc;
		operatingIndex += currentInstruction.shift;
	}
})();

function parseInput(input) {
  let lines = input.split('\n').map(l => {
    const [, instr, param] = l.match(/(.*) (.*)/)
    return { instr, param: Number(param) }
  })

  return lines
}

function run(prog) {
  let ptr = 0
  let acc = 0
  let seen = []

  while (true) {
    if (!prog[ptr]) return { halts: true, acc }
    if (seen[ptr]) return { halts: false, acc }

    const { instr, param } = prog[ptr]
    seen[ptr] = true

    if (instr === 'jmp') {
      ptr += param
    }

    if (instr === 'acc') {
      acc += param
      ptr++
    }

    if (instr === 'nop') {
      ptr++
    }
  }
}

export function solvePart1(input) {
  let prog = parseInput(input)
  return run(prog).acc
}

export function solvePart2(input) {
  let prog = parseInput(input)

  for (let i = 0; i < prog.length; i++) {
    let { instr, param } = prog[i]

    if (instr.match(/(nop|jmp)/)) {
      const progCopy = [...prog]
      progCopy[i] = {
        instr: instr === 'nop' ? 'jmp' : 'nop',
        param,
      }

      const result = run(progCopy)
      if (result.halts) return result.acc
    }
  }
}

package main

import "fmt"
import "bufio"
import "os"
import "strings"
import "strconv"

const ACC = 1
const JUMP = 2
const NOOP = 3

func main() {
        scanner := bufio.NewScanner(os.Stdin)

        instructions := make([][]int,0)
        for scanner.Scan() {

                line := scanner.Text()
                tokens := strings.Split(line, " ")
                instr := NOOP
                switch tokens[0] {
                case "acc": instr = ACC
                case "jmp": instr = JUMP
                }
                arg, _ := strconv.Atoi(tokens[1])
                instruction := make([]int,2)
                instruction[0] = instr
                instruction[1] = arg
                instructions = append(instructions, instruction)
        }

        executed := make(map[int]bool)

        acc := 0
        inc := 1
        pos := 0
        for _, exists := executed[pos]; !exists && pos < len(instructions); _, exists = executed[pos] {
                executed[pos] = true
                switch instruction := instructions[pos]; instruction[0] {
                case ACC:
                        acc += instruction[1]
                        inc = 1
                case JUMP:
                        inc = instruction[1]
                case NOOP:
                        inc = 1
                }

                pos += inc
        }

        fmt.Println(acc)

package main

import "fmt"
import "bufio"
import "os"
import "strings"
import "strconv"

const ACC = 1
const JUMP = 2
const NOOP = 3

func execute(pos int, acc int, instructions [][]int, executed map[int]bool, evaluateAlternative bool, c chan int) {

        inc := 1
        for _, exists := executed[pos]; !exists && pos < len(instructions); _, exists = executed[pos] {
                executed[pos] = true
                switch instruction := instructions[pos]; instruction[0] {
                case ACC:
                        acc += instruction[1]
                        inc = 1
                case JUMP:
                        inc = instruction[1]

                        if evaluateAlternative {
                                cloneExecuted := copy(executed)
                                go execute(pos + 1, acc, instructions, cloneExecuted, false, c)
                        }

                case NOOP:
                        inc = 1
                        if evaluateAlternative {
                                cloneExecuted := copy(executed)
                                go execute(pos + instruction[1], acc, instructions, cloneExecuted, false, c)
                        }
                }

                pos += inc
        }
        if pos == len(instructions) {
                c <- acc
        }
}

func copy(toCopy map[int]bool) map[int]bool {
        result := make(map[int]bool)
        for k, v := range toCopy {
                result[k] = v
        }
        return result
}

func main() {
        scanner := bufio.NewScanner(os.Stdin)
        instructions := make([][]int,0)
        for scanner.Scan() {
                line := scanner.Text()
                tokens := strings.Split(line, " ")
                instr := NOOP
                switch tokens[0] {
                case "acc": instr = ACC
                case "jmp": instr = JUMP
                }

                arg, _ := strconv.Atoi(tokens[1])
                instruction := make([]int,2)
                instruction[0] = instr
                instruction[1] = arg
                instructions = append(instructions, instruction)
        }

        executed := make(map[int]bool)

        c := make(chan int, 1)
        go execute(0, 0, instructions, executed, true, c)

        fmt.Println(<- c)
}

#!/usr/bin/env ruby
require "ostruct"

input = File.read(ARGV[0] || "test.txt")

def run(code)
  acc = 0
  pc = 0
  hits = Hash.new(0)

  while instr = code[pc] do
    hits[pc] += 1

    if hits[pc] >= 2
      return [:loop, acc]
    end

    case instr.opcode
    when "acc"
      acc += instr.value
      pc += 1
    when "nop"
      pc += 1
    when "jmp"
      pc += instr.value
      next
    end
  end

  return [:ok, acc]
end

code = input.lines.map(&:strip).map { |l| o, v = l.split(' '); OpenStruct.new(opcode: o, value: v.to_i) }
puts "Part 1"
puts run(code)[1]

puts "Part 2"

def flip(instr)
  case instr.opcode
  when "nop"
    instr.opcode = "jmp"
  when "jmp"
    instr.opcode = "nop"
  end
  return instr
end

result = -1
code.each do |instr|
  flip(instr)
  status, result = run(code)

  break if status == :ok
  flip(instr) #flip back before moving on
end
puts result

# main.jl
include("Assembly.jl")
import .Assembly

function main()

    input = []
    open("Day08/input.txt") do fp
        input = Assembly.parse_instruction.(split.(readlines(fp), ' '))
    end

    machine = Assembly.MachineState(input, 1, 0)

    result_1 = infinite_loop_finder(machine)
    println("Part 1 result is ", result_1)

end

# Find the infinite loop by comparing current instruction pointer locations to
# ones that have come before
function infinite_loop_finder(machine::Assembly.MachineState)
    old_pointers = Set([machine.instruction_pointer])
    old_accumulator = machine.accumulator
    no_repeat = true

    while no_repeat
        machine = Assembly.advance(machine)
        if machine.instruction_pointer in old_pointers
            no_repeat = false
        else
            push!(old_pointers, machine.instruction_pointer)
            old_accumulator = machine.accumulator
        end
    end

    return old_accumulator
end

main()

# Assembly.jl
module Assembly

# Make sure other things can use types
export Instruction, MachineState, Nop, Acc, Jmp

# Make sure other things can use methods
export parse_instruction, advance

# Make some fun types to define different instructions
abstract type Instruction end

# Make a type to define the state machine
struct MachineState
    instructions::Array{Instruction}
    instruction_pointer::Int64
    accumulator::Int64
end

struct Noop <: Instruction end

struct Accumulate <: Instruction
    value::Int64
end

struct Jump <: Instruction
    value::Int64
end

# How to convert from the input format to instructions we know of
function parse_instruction(input)::Instruction
    if input[1] == "nop"
        return Noop()
    elseif input[1] == "acc"
        return Accumulate(parse(Int64, input[2]))
    elseif input[1] == "jmp"
        return Jump(parse(Int64, input[2]))
    end
    throw(DomainError(input, "No recognizeable commands!"))
end

# Convenience function to execute the machine in it's current state
function advance(machine::MachineState)::MachineState
    return advance(machine, machine.instructions[machine.instruction_pointer])
end

# These functions define the changes to the machine state based on the instruction type
function advance(machine::MachineState, instruction::Noop)
    return MachineState(machine.instructions,
                        machine.instruction_pointer + 1,
                        machine.accumulator)
end

function advance(machine::MachineState, instruction::Jump)
    return MachineState(machine.instructions,
                        machine.instruction_pointer + instruction.value,
                        machine.accumulator)
end

function advance(machine::MachineState, instruction::Accumulate)
    return MachineState(machine.instructions,
                        machine.instruction_pointer + 1,
                        machine.accumulator + instruction.value)
end

end

--- a/Day08/Assembly.jl
+++ b/Day08/Assembly.jl
@@ -14,9 +14,19 @@ struct MachineState
     instructions::Array{Instruction}
     instruction_pointer::Int64
     accumulator::Int64
+
+    function MachineState(instructions::Array{Instruction})
+        return new(instructions, 1, 0)
+    end
+
+    function MachineState(instructions::Array{Instruction}, instruction_pointer::Int64, accumulator::Int64)
+        return new(instructions, instruction_pointer, accumulator)
+    end
 end
 
-struct Noop <: Instruction end
+struct Noop <: Instruction 
+    value::Int64
+end
 
 struct Accumulate <: Instruction
     value::Int64
@@ -29,7 +39,7 @@ end
 # How to convert from the input format to instructions we know of
 function parse_instruction(input)::Instruction
     if input[1] == "nop"
-        return Noop()
+        return Noop(parse(Int64, input[2]))
     elseif input[1] == "acc"
         return Accumulate(parse(Int64, input[2]))
     elseif input[1] == "jmp"
@@ -62,4 +72,9 @@ function advance(machine::MachineState, instruction::Accumulate)
                         machine.accumulator + instruction.value)
 end
 
+# Check if the machine is complete
+function complete(machine::MachineState)
+    return machine.instruction_pointer > length(machine.instructions)
+end
+
 end
\ No newline at end of file
diff --git a/Day08/main.jl b/Day08/main.jl
index 07c5bb9..218a980 100644
--- a/Day08/main.jl
+++ b/Day08/main.jl
@@ -8,17 +8,20 @@ function main()
         input = Assembly.parse_instruction.(split.(readlines(fp), ' '))
     end
 
-    machine = Assembly.MachineState(input, 1, 0)
+    machine = Assembly.MachineState(input)
 
-    result_1 = infinite_loop_finder(machine)
+    result_1, stack_trace = infinite_loop_finder(machine)
     println("Part 1 result is ", result_1)
 
+    result_2 = infinite_loop_fixer(machine, stack_trace)
+    println("Part 2 result is ", result_2)
+
 end
 
 # Find the infinite loop by comparing current instruction pointer locations to
 # ones that have come before
 function infinite_loop_finder(machine::Assembly.MachineState)
-    old_pointers = Set([machine.instruction_pointer])
+    old_pointers = [machine.instruction_pointer]
     old_accumulator = machine.accumulator
     no_repeat = true
 
@@ -26,13 +29,45 @@ function infinite_loop_finder(machine::Assembly.MachineState)
         machine = Assembly.advance(machine)
         if machine.instruction_pointer in old_pointers
             no_repeat = false
+
+        elseif Assembly.complete(machine)
+            return machine.accumulator, nothing
         else
             push!(old_pointers, machine.instruction_pointer)
             old_accumulator = machine.accumulator
         end
     end
 
-    return old_accumulator
+    return old_accumulator, old_pointers
+end
+
+# Go backward through a given stack trace and flip flop instructions until you
+# get a set of instructions that halts
+function infinite_loop_fixer(original_machine::Assembly.MachineState, stack_trace)
+
+    stack_trace = reverse(stack_trace)
+    original_instructions = original_machine.instructions
+    for idx in stack_trace
+        new_instructions = original_instructions
+        if isa(new_instructions[idx], Assembly.Noop)
+            new_instructions[idx] = Assembly.Jump(new_instructions[idx].value)
+        elseif isa(new_instructions[idx], Assembly.Jump)
+            new_instructions[idx] = Assembly.Noop(new_instructions[idx].value)
+        else
+            continue
+        end
+
+        new_machine = Assembly.MachineState(new_instructions)
+
+        accumulator, test_stack = infinite_loop_finder(new_machine)
+
+        if isa(test_stack, Nothing)
+            return accumulator
+        end
+    end
+
+    return nothing
+
 end
 
 main()