use std::collections::HashSet;
use std::mem::swap;

#[derive(Debug, PartialOrd, PartialEq, Clone)]
enum ActionType {
    Acc,
    Jmp,
    Nop,
}

#[derive(Debug, PartialOrd, PartialEq, Clone)]
struct Action {
    num: i32,
    action: ActionType,
}

impl Action {
    fn run(&self, pos: &i32, accumulator: &i32) -> (i32, i32) {
        match self.action {
            ActionType::Acc => (pos + 1, accumulator + self.num),
            ActionType::Jmp => (pos + self.num, accumulator.clone()),
            ActionType::Nop => (pos + 1, accumulator.clone()),
        }
    }
}

fn run_actions(input: &[Action]) -> (i32, bool, Vec<usize>) {
    let mut actions_taken = HashSet::new();
    let mut action_order = vec![];
    let mut curr_action: usize = 0;
    let mut acc: i32 = 0;
    loop {
        let action = match input.get(curr_action) {
            Some(a) => a,
            None => return (acc, true, action_order),
        };
        let (new_action, new_acc) = action.run(&(curr_action as i32), &acc);
        action_order.push(new_action as usize);
        if actions_taken.contains(&new_action) {
            return (acc, false, action_order);
        }
        curr_action = new_action as usize;
        acc = new_acc;
        actions_taken.insert(new_action);
    }
}

#[aoc(day8, part1)]
fn last_value_before_rerun(input: &Vec<Action>) -> i32 {
    run_actions(input.as_slice()).0
}

#[aoc(day8, part2)]
fn fix_program(input: &Vec<Action>) -> i32 {
    let (_, _, mut action_order) = run_actions(input.as_slice());
    action_order.reverse();
    for action in action_order
        .iter()
        .filter(|a| input.get(**a).unwrap().action != ActionType::Acc)
    {
        let to_swap: &Action = input.get(*action).unwrap();
        let swapped = match to_swap.action {
            ActionType::Nop => Action {
                num: to_swap.num,
                action: ActionType::Jmp,
            },
            ActionType::Jmp => Action {
                num: to_swap.num,
                action: ActionType::Nop,
            },
            _ => unreachable!(),
        };
        let (acc, finished, _) = run_actions(
            [&input[0..*action], &[swapped], &input[*action + 1..]]
                .concat()
                .as_slice(),
        );
        if finished {
            return acc;
        }
    }
    0
}

-- anamorphism for lists, used to generate our program traces and modifications
unfoldr :: (b -> Maybe (a, b)) -> (b -> [a])
unfoldr f b = case f b of
                Just (a, b') -> a : unfoldr f b'
                Nothing -> []

-- our 3 known opcodes
data Op = NOp Int | Acc Int | Jmp Int
    deriving (Show, Eq)

type Program = [Op]
type PC = Int

-- Simple parser
lexer = Token.makeTokenParser (TP.emptyDef { Token.reservedNames   = [ "nop", "acc", "jmp" ] })
reserved   = Token.reserved   lexer -- op code
integer    = Token.integer    lexer -- integer
whiteSpace = Token.whiteSpace lexer -- whitespace

-- parse individual opcode
pOpcode :: TP.Parser (Int -> Op)
pOpcode = (reserved "nop" >> return NOp) <|> (reserved "acc" >> return Acc) <|> (reserved "jmp" >> return Jmp)

-- parse an individual instruction
pInstruction :: TP.Parser Op
pInstruction = 
    do op <- pOpcode
       whiteSpace
       op . fromIntegral <$> integer

-- parse all ops
parseOps :: String -> [Op]
parseOps = either (error . show) id . TP.parse (TP.many1 (whiteSpace >> pInstruction)) ""

-- given a PC and a set of visited PC, have we been there before?
halt :: PC -> DS.Set Int -> Bool
halt = DS.member

-- execute a single op, returning a new acc and a function to compute next PC
executeOp :: Op -> Int -> (Int, PC -> PC)
executeOp (NOp _) acc = (acc, (+1))
executeOp (Acc inc) acc = (acc+inc, (+1))
executeOp (Jmp i) acc = (acc, (+i))

-- step a single op for a given program, at PC, seen PCs, and current Acc
step :: (Program, PC, DS.Set Int, Int) -> Maybe ((Bool, Int), (Program, PC, DS.Set Int, Int))
step (ps, pc, seen, acc) 
    | pc >= length ps = Nothing
    | otherwise = let (acc', next) = executeOp (ps!!pc) acc
                      pc' = next pc
                  in Just ((halt pc' seen, acc'), (ps, pc', DS.insert pc' seen, acc') )

-- modify an op (NOP => JMP and JMP => NOP), if possible
modOp :: Op -> Maybe Op
modOp (NOp i) = Just (Jmp i)
modOp (Acc inc) = Nothing
modOp (Jmp i) = Just (NOp i)

-- generate a modified program, if possible, given a Program and PC
mods :: (Program, PC) -> Maybe (Maybe Program, (Program, PC))
mods (ps, pc) = if pc < length ps
                then Just (maybe (Nothing, (ps, pc+1)) aux (modOp (ps!!pc)))
                else Nothing
    where
        aux op = (Just (take pc ps ++ [op] ++ drop (pc+1) ps), (ps, pc+1))

-- produce all traces of a programs execution
execute :: Program -> [(Bool, Int)]
execute ps = unfoldr step (ps, 0, DS.empty, 0)

-- find acc at the point when a single op is executed twice
part1 = snd . head . dropWhile (not . fst) . execute

-- find a acc for a modified program that terminates
part2 = fromMaybe 0 . head . dropWhile (==Nothing) . map (p . execute) . 
            foldr (\a b -> maybe b (:b) a) [] . unfoldr mods . (\ps -> (ps,0))
    where
        p [(False, v)] = Just v 
        p ((True,_):_) = Nothing
        p (_:xs)       = p xs

-- run task 1 and task 2 for AOC ay 8
main = do ops <- readFile "day8_input" <&> parseOps
          print (part1 ops)
          print (part2 ops)

lines = []
with open('input.txt') as file:
    for line in file:
        line = line.rstrip().split(' ')
        lines.append([line[0], int(line[1])])


def move(lines, part_1=False):
    seen = set()
    accumulator = 0
    idx = 0
    while True:
        if idx >= len(lines):
            return accumulator
        move, arg = lines[idx]
        if idx in seen:
            return accumulator if part_1 else False
        seen.add(idx)
        if move == 'nop':
            idx += 1
        elif move == 'acc':
            accumulator += arg
            idx += 1
        elif move == "jmp":
            idx += arg


def flip(val):
    return 'jmp' if val == 'nop' else 'nop'


def change_piece(lines):
    for idx, turn in enumerate(lines):
        if turn[0] == 'nop' or turn[0] == 'jmp':
            prev = turn[0]
            lines[idx][0] = flip(turn[0])
            if accumulator:= move(lines):
                return accumulator
            lines[idx][0] = prev

print("Part 1", move(lines, True))
print("Part 2", change_piece(lines))

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

namespace AdventOfCode2020
{

    enum Operation
    {
        nop,
        acc,
        jmp
    }
    class Instruction
    {
        public Operation Operation { get; set; }
        public int Argument { get; set; }
        public bool IsExecuted { get; set; }
    }
    static class Day8
    {
        static List<Instruction> Instructions = new List<Instruction>();
        static int accumulator = 0;
        static int instructionPosition = 0;
        //InstructionChanged is used to show which instruction had to be changed
        static Instruction InstructionChanged;
        public static void Execute()
        {
            List<string> input = new List<string>(File.ReadAllLines("C:\\Users\\DirkFraanje\\Documents\\adventofcodeday8.txt"));

            //Added a imer just for fun
            var timer = new Stopwatch();
            timer.Start();
            //First create a nice list of instructions from the inputfile
            foreach (var instruction in input)
            {
                Instructions.Add(CreateNewInstruction(instruction));
            }
            //Run recursive method to find the instruction that has to be changed
            FindInstructionToChange();
            //Stop the timer, show the answer and just for fun the instruction that has to be changed
            timer.Stop();
            Console.WriteLine($"Answer: {accumulator} ");
            Console.WriteLine($"Instruction to change: {InstructionChanged.Operation} {InstructionChanged.Argument}");
            Console.WriteLine($"Executed in: {timer.ElapsedMilliseconds} milliseconds");
        }

        private static void FindInstructionToChange()
        {
            var i = 0;
            while (true)
            {
                var instruction = Instructions[i];
                switch (Instructions[i].Operation)
                {
                    case Operation.nop:
                        instruction.Operation = Operation.jmp;
                        if (RunBootCodeSuccesful())
                        {
                            //Before returning the answer change the answer back to it's original Operation so it can be showed in the console
                            instruction.Operation = Operation.nop;
                            InstructionChanged = instruction;
                            return;
                        }
                        else
                            instruction.Operation = Operation.nop;
                        break;
                    case Operation.acc:
                        break;
                    case Operation.jmp:
                        instruction.Operation = Operation.nop;
                        if (RunBootCodeSuccesful())
                        {
                            //Before returning the answer change the answer back to it's original Operation so it can be showed in the console
                            instruction.Operation = Operation.jmp;
                            InstructionChanged = instruction;
                            return;
                        }
                        else
                            instruction.Operation = Operation.jmp;
                        break;
                    default:
                        break;
                }
                i++;
                //Reset everything to it's default
                accumulator = 0;
                instructionPosition = 0;
                Instructions.ForEach(x => x.IsExecuted = false);
            }
        }

        private static bool RunBootCodeSuccesful()
        {
            while (true)
            {
                var instruction = Instructions[instructionPosition];
                switch (instruction.Operation)
                {
                    case Operation.nop:
                        instructionPosition++;
                        break;
                    case Operation.acc:
                        accumulator += instruction.Argument;
                        instructionPosition++;
                        break;
                    case Operation.jmp:
                        instructionPosition += instruction.Argument;
                        break;
                    default:
                        break;
                }
                instruction.IsExecuted = true;
                if (instructionPosition > Instructions.Count - 1)
                    return true;
                var nextInstruction = Instructions[instructionPosition];
                if (nextInstruction.IsExecuted)
                    return false;
            }
        }

        static Instruction CreateNewInstruction(string instructionline)
        { 
            var instruction = new Instruction();
            var splitOperationAndArgument = instructionline.Split(' ');
            switch (splitOperationAndArgument[0])
            {
                case "nop":
                    instruction.Operation = Operation.nop;
                    break;
                case "acc":
                    instruction.Operation = Operation.acc;
                    break;
                case "jmp":
                    instruction.Operation = Operation.jmp;
                    break;
                default:
                    break;
            }
            instruction.Argument = int.Parse(splitOperationAndArgument[1]);
            return instruction;
        }
    }
}

use aoc_runner_derive::{aoc, aoc_generator};
use regex::Regex;

struct Program {
    instructions: Vec<Instruction>,
    accumulator: isize,
    fp: isize,
    clean_exit: bool,
}

impl Program {
    fn new(instructions: Vec<Instruction>) -> Program {
        Program {
            instructions: instructions,
            accumulator: 0,
            fp: 0,
            clean_exit: true,
        }
    }
    fn run_until_cycle(&mut self) {
        loop {
            let mut inst = self.instructions.get_mut(self.fp as usize);
            match inst {
                Some(inst) => {
                    inst.visit_count += 1;
                    if inst.visit_count == 2 {
                        self.clean_exit = false;
                        return;
                    }
                    match &inst.opcode[..] {
                        "acc" => {
                            self.accumulator += inst.position;
                            self.fp += 1;
                        }
                        "jmp" => self.fp += inst.position,
                        "nop" => self.fp += 1,
                        _ => panic!("Unexpected instruction!"),
                    }
                }
                None => return,
            }
        }
    }
}

#[derive(Clone)]
struct Instruction {
    opcode: String,
    position: isize,
    visit_count: u8,
}

#[aoc_generator(day8)]
fn parse_input_day8(input: &str) -> Vec<Instruction> {
    let instruction_re =
        Regex::new("^(?P<opcode>\\w{3}) (?P<pos>[+-]\\d+)").expect("Couldn't create regex!");
    input
        .lines()
        .map(|line| {
            let captures = instruction_re.captures(line).expect("Didn't match regex!");
            Instruction {
                opcode: String::from(captures.name("opcode").unwrap().as_str()),
                position: str::parse(captures.name("pos").unwrap().as_str()).unwrap(),
                visit_count: 0,
            }
        })
        .collect()
}

#[aoc(day8, part1)]
fn read_accumulator_at_cycle(input: &Vec<Instruction>) -> isize {
    let insts = input.clone();
    let mut pg = Program::new(insts);
    pg.run_until_cycle();
    pg.accumulator
}

#[aoc(day8, part2)]
fn correct_broken_op(input: &Vec<Instruction>) -> isize {
    let mut pg: Program;
    let mut result: isize = 0;
    for (pos, inst) in input.iter().enumerate() {
        if &inst.opcode[..] == "nop" {
            let mut insts = input.clone();
            insts.get_mut(pos).unwrap().opcode = String::from("jmp");
            pg = Program::new(insts);
            pg.run_until_cycle();
            if pg.clean_exit {
                result = pg.accumulator;
                break;
            }
        }
        if &inst.opcode[..] == "jmp" {
            let mut insts = input.clone();
            insts.get_mut(pos).unwrap().opcode = String::from("nop");
            pg = Program::new(insts);
            pg.run_until_cycle();
            if pg.clean_exit {
                result = pg.accumulator;
                break;
            }
        }
    }

    result
}

#include "Day8.h"

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

#include "parsing.h"

/// Day 8: Handheld Halting
/// 
/// Figure out how to break a handheld game out of an infinite loop!

/// The type of operation that is used
typedef enum {
  OP_NOP,  ///< No operation
  OP_ACC,  ///< Adjust acc by arg
  OP_JMP,  ///< Jump to arg location, relative to current ip
} Opcode;

/// A full instruction line in the program
typedef struct {
  Opcode op;  ///< The operation to be done
  int arg;    ///< A positive or negative integer argument
} Instruction;

/// A program that keeps track of whether it has already run code
typedef struct {
  Instruction* program;   ///< List of instructions to be run
  int ip;                 ///< Index of the current instruction to run
  int acc;                ///< Acc value adjusted by the acc opcode
  int lines;              ///< Number of lines in the program
  bool* line_run;         ///< List of booleans denoting whether each line has run yet
} Interpreter;

/// Check if the current line has already been run
#define HAS_ALREADY_RUN(interp) (interp.line_run[interp.ip])

/// Label this line as already run
#define MARK_AS_RUN(interp) (interp.line_run[interp.ip] = true)

/// Create a new interpreter from an input file
static Interpreter new_interpreter(const char* filename) {
  FILE* fp;
  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("Couldn't open input file.\n");
    exit(EXIT_FAILURE);
  }

  Interpreter interpreter;
  int lines = count_lines(fp);
  Instruction* program = (Instruction*)malloc(sizeof(Instruction) * lines);

  for (int i = 0; i < lines; i++) {
    char op[4] = {0};
    int arg = 0;
    fscanf(fp, "%s %d\n", op, &arg);
    Instruction instruction = {0};
    switch (op[0]) {
      case 'n':
        instruction.op = OP_NOP;
        break;
      case 'a':
        instruction.op = OP_ACC;
        break;
      case 'j':
        instruction.op = OP_JMP;
        break;
      default:
        printf("Unrecognized opcode %s.\n", op);
        exit(EXIT_FAILURE);
    }
    instruction.arg = arg;
    program[i] = instruction;
  }

  fclose(fp);
  interpreter.ip = 0;
  interpreter.acc = 0;
  interpreter.lines = lines;
  interpreter.line_run = (bool*)malloc(sizeof(bool) * lines);
  memset(interpreter.line_run, 0, sizeof(bool) * lines);
  interpreter.program = program;
  return interpreter;
}

/// Free an interpreter's malloced memory
void free_interpreter(Interpreter* interpreter) {
  free(interpreter->program);
  interpreter->program = NULL;
  free(interpreter->line_run);
  interpreter->line_run = NULL;
}

/// Run the instruction under the IP
void tick(Interpreter* interpreter) {
  Instruction instruction = interpreter->program[interpreter->ip];
  switch (instruction.op) {
      case OP_NOP: interpreter->ip++; break;
      case OP_ACC: 
        interpreter->acc += instruction.arg;
        interpreter->ip++;
        break;
      case OP_JMP: interpreter->ip += instruction.arg; break;
    }
}

/// What is the value of the acc when the first loop is encountered?
int part1(const char* filename) {
  Interpreter interpreter = new_interpreter(filename);

  while (true) {
    if (HAS_ALREADY_RUN(interpreter)) {
      return interpreter.acc;
    } else {
      MARK_AS_RUN(interpreter);
    }

    tick(&interpreter);
  }
}

/// Makes a standalone copy of an interpreter
Interpreter copy_interpreter(Interpreter* orig) {
  Interpreter new;
  new.ip = orig->ip;
  new.acc = orig->acc;
  new.lines = orig->lines;
  new.line_run = (bool*)malloc(sizeof(bool) * new.lines);
  memcpy(new.line_run, orig->line_run, sizeof(bool) * new.lines);
  new.program = (Instruction*)malloc(sizeof(Instruction) * new.lines);
  memcpy(new.program, orig->program, sizeof(Instruction) * new.lines);
  return new;
}

/// If you change one of the JMP to a NOP or vice versa, the program
/// will exit normally.  When it actually does that, what is the
/// value in acc?
int part2(const char* filename) {
  Interpreter base = new_interpreter(filename);

  for (int i = 0; i < base.lines; i++) {
    if (base.program[i].op == OP_ACC) continue;
    Interpreter interpreter = copy_interpreter(&base);
    if (interpreter.program[i].op == OP_JMP) {
      interpreter.program[i].op = OP_NOP;
    } else {
      interpreter.program[i].op = OP_JMP;
    }

    while (true) {
      if (HAS_ALREADY_RUN(interpreter)) {
        break;
      } else if (interpreter.ip >= interpreter.lines) {
        return interpreter.acc;
      } else {
        MARK_AS_RUN(interpreter);
      }

      tick(&interpreter);
    }

    free_interpreter(&interpreter);
  }
  return -1;
}

/// Run both days.
int day8() {
  printf("====== Day 8 ======\n");
  printf("Part 1: %d\n", part1("data/day8.txt"));
  printf("Part 2: %d\n", part2("data/day8.txt"));
  return EXIT_SUCCESS;
}

def execute_program(lines):
    lines_executed = set()
    cursor = 0
    accumulator = 0

    def acc(lines, cursor, accumulator):
        return (cursor + 1, accumulator + int(lines[cursor][1]))

    def jmp(lines, cursor, accumulator):
        return (cursor + int(lines[cursor][1]), accumulator )

    def nop(lines, cursor, accumulator):
        return (cursor + 1, accumulator)

    terminated = False
    while not terminated and cursor not in lines_executed:
        instruction = lines[cursor][0]
        lines_executed.add(cursor)

        operations = {
            'jmp': jmp,
            'acc': acc,
            'nop': nop,
        }
        operation = operations[instruction]
        cursor, accumulator = operation(lines, cursor, accumulator)

        # Terminate if end at program
        terminated = cursor == len(lines)
    return terminated, accumulator

def part1(lines):
    _, result = execute_program(lines)
    return result
print part1(lines)

def part2(lines):
    for i in range(len(lines)):
        # Copy lines so that changes don't persist.
        local_lines = [x for x in lines]

        # Switch statement jmp/nop
        if 'jmp' in local_lines[i][0]:
            local_lines[i] = ('nop', local_lines[i][1])
        elif 'nop' in local_lines[i][0]:
            local_lines[i] = ('jmp', local_lines[i][1])

        terminated, result = execute_program(local_lines)

        if terminated:
            break
    return result
print "Solution part 2: %d" % part2(lines)

use std::collections::HashSet;
use std::fs::File;
use std::io::prelude::*;

mod parser;
use parser::*;

// --- file read

fn read_file(filename: &str) -> std::io::Result<String> {
    let mut file = File::open(filename)?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    Ok(contents)
}

// --- model

#[derive(Debug, Clone, Eq, PartialEq)]
enum Instruction {
    Acc(i64),
    Jmp(i64),
    Nop(i64)
}

type Program = Vec<Instruction>;

#[derive(Debug)]
struct Machine {
    instr_ptr: usize,
    accumulator: i64
}

#[derive(Debug, Eq, PartialEq)]
enum Termination {
    InfiniteLoop,
    EndOfProgram
}

impl Machine {
    fn new() -> Self {
        Machine {
            instr_ptr: 0,
            accumulator: 0
        }
    }

    fn run(&mut self, program: &Program) -> Termination {
        let mut visited = HashSet::new();

        loop {
            if self.instr_ptr >= program.len() {
                return Termination::EndOfProgram;
            }
            if !visited.insert(self.instr_ptr) {
                return Termination::InfiniteLoop
            }

            match program[self.instr_ptr] {
                Instruction::Acc(arg) => {
                    self.accumulator += arg;
                    self.instr_ptr += 1;
                }
                Instruction::Jmp(arg) => {
                    self.instr_ptr = ((self.instr_ptr as i64) + arg) as usize;
                }
                Instruction::Nop(_) => {
                    self.instr_ptr += 1;
                }
            }
        }
    }
}

// --- parser

fn parse_input(input: &str) -> ParseResult<Program> {
    let sign = either(
        any_char.pred(|c| *c == '+').means(1),
        any_char.pred(|c| *c == '-').means(-1)
    );
    let signed_integer = pair(sign, integer).map(|(s, i)| s * i);

    let acc = right(match_literal("acc "), signed_integer.clone()).map(Instruction::Acc);
    let jmp = right(match_literal("jmp "), signed_integer.clone()).map(Instruction::Jmp);
    let nop = right(match_literal("nop "), signed_integer).map(Instruction::Nop);
    let instruction = whitespace_wrap(either(either(acc, jmp), nop));

    zero_or_more(instruction).parse(input)
}


// --- problems

fn part1(program: &Program) -> i64 {
    let mut machine = Machine::new();
    machine.run(program);
    machine.accumulator
}

fn part2(program: &Program) -> Option<i64> {
    fn is_jmp(i: &Instruction) -> bool {
        if let Instruction::Jmp(_) = i { true } else { false }
    }

    program.iter()
        .enumerate()
        .filter(|(_, instr)| is_jmp(instr))
        .find_map(|(index, _)| {
            let mut modified: Program = program.to_vec();
            modified[index] = Instruction::Nop(0);

            let mut machine = Machine::new();
            if machine.run(&modified) == Termination::EndOfProgram {
                Some(machine.accumulator)
            } else {
                None
            }
        })
}

fn main() {
    let input = read_file("./input.txt").unwrap();
    let program: Program = parse_input(&input).unwrap().1;

    println!("part1 {:?}", part1(&program));
    println!("part2 {:?}", part2(&program));
}

#[cfg(test)]
mod tests {
    use super::*;

    fn test_program() -> Program {
        vec![
            Instruction::Nop(0),
            Instruction::Acc(1),
            Instruction::Jmp(4),
            Instruction::Acc(3),
            Instruction::Jmp(-3),
            Instruction::Acc(-99),
            Instruction::Acc(1),
            Instruction::Jmp(-4),
            Instruction::Acc(6)
        ]
    }

    #[test]
    fn test_parse_instructions() {
        let sample = "
            nop +0
            acc +1
            jmp +4
            acc +3
            jmp -3
            acc -99
            acc +1
            jmp -4
            acc +6
        ";
        let instructions = parse_input(sample);

        assert_eq!(instructions, Ok(("", test_program())));
    }

    #[test]
    fn test_running_until_instruction_visited_twice() {
        let mut machine = Machine::new();
        let term = machine.run(&test_program());

        assert_eq!(term, Termination::InfiniteLoop);
        assert_eq!(machine.accumulator, 5);
    }

    #[test]
    fn test_part2() {
        assert_eq!(part2(&test_program()), Some(8));        
    }

}

require 'set'

instructions = []

File.readlines('08.txt').each do |line|
  code, argument = line.split(' ')
  instructions.push [code, argument.to_i]
end

acc = 0
i = 0
visited = Set.new

until visited.include? i
  code, argument = instructions[i]
  visited.add i

  case code
  when 'nop'
    # Do nothing
    i += 1
  when 'acc'
    acc += argument
    i += 1
  when 'jmp'
    i += argument
  end
end

puts acc

require 'set'

instructions = []

File.readlines('08.txt').each do |line|
  code, argument = line.split(' ')
  instructions.push [code, argument.to_i]
end

swap_indices = instructions.each_with_index.select do |instruction, i|
  code = instruction[0]
  code == 'nop' or code == 'jmp'
end.map do |instruction, i|
  i
end

swap_indices.each do |j|
  acc = 0
  i = 0
  visited = Set.new
  new_instructions = Marshal.load(Marshal.dump(instructions))

  if new_instructions[j][0] == 'jmp'
    new_instructions[j][0] = 'nop'
  else
    new_instructions[j][0] = 'jmp'
  end

  until visited.include? i
    code, argument = new_instructions[i]
    visited.add i

    case code
    when 'nop'
      # Do nothing
      i += 1
    when 'acc'
      acc += argument
      i += 1
    when 'jmp'
      i += argument
    when nil
      # Stepped out of instructions array
      puts acc
      break
    end
  end
end

   IDENTIFICATION DIVISION.
   PROGRAM-ID. AOC-2020-08-1.
   AUTHOR ANNA KOSIERADZKA.

   ENVIRONMENT DIVISION.
   INPUT-OUTPUT SECTION.
   FILE-CONTROL.
       SELECT INPUTFILE ASSIGN TO "d08.input"
       ORGANIZATION IS LINE SEQUENTIAL.

   DATA DIVISION.
   FILE SECTION.
     FD INPUTFILE.
     01 INPUTRECORD. 
       05 INPUT-INSTRUCTION PIC X(3).
       05 INPUT-SPACE PIC X.
       05 INPUT-SIGN PIC X(1).
       05 INPUT-ARG PIC 9(3).

   WORKING-STORAGE SECTION.
     01 FILE-STATUS PIC 9 VALUE 0.
     01 WS-CODE OCCURS 625 TIMES.
       05 WS-INSTRUCTION PIC X(3).
       05 WS-SIGN PIC X.
       05 WS-ARG PIC 9(3).
       05 WS-DONE PIC 9 VALUE 0.
     01 WS-I PIC X(3).
     01 WS-ACC PIC S9(6) VALUE 0.

   LOCAL-STORAGE SECTION.
     01 I UNSIGNED-INT VALUE 1.
     01 ARG UNSIGNED-INT VALUE 0.
     01 CODE-POS UNSIGNED-INT VALUE 1.

   PROCEDURE DIVISION.
   001-MAIN.
       OPEN INPUT INPUTFILE.
       PERFORM 002-READ UNTIL FILE-STATUS = 1.
       CLOSE INPUTFILE.
       PERFORM 004-RUN-CODE.
       DISPLAY WS-ACC.
       STOP RUN.

   002-READ.
        READ INPUTFILE
            AT END MOVE 1 TO FILE-STATUS
            NOT AT END PERFORM 003-PROCESS-RECORD
        END-READ.

   003-PROCESS-RECORD.
       MOVE INPUT-INSTRUCTION TO WS-INSTRUCTION(I).
       MOVE INPUT-SIGN TO WS-SIGN(I).
       MOVE INPUT-ARG TO WS-ARG(I).
       ADD 1 TO I.

   004-RUN-CODE.
       PERFORM 005-RUN-INSTRUCTION UNTIL WS-DONE(CODE-POS) = 1.

   005-RUN-INSTRUCTION.
       MOVE 1 TO WS-DONE(CODE-POS).
       MOVE WS-INSTRUCTION(CODE-POS) TO WS-I.
       COMPUTE ARG = FUNCTION NUMVAL(WS-ARG(CODE-POS)).

       IF WS-I = "nop" THEN 
          ADD 1 TO CODE-POS
       END-IF.

       IF WS-I = "acc" THEN 
          IF WS-SIGN(CODE-POS) = "+" THEN
            COMPUTE WS-ACC = WS-ACC + ARG
          ELSE 
            COMPUTE WS-ACC = WS-ACC - ARG
          END-IF
          ADD 1 TO CODE-POS
       END-IF.

       IF WS-I = "jmp" THEN 
          IF WS-SIGN(CODE-POS) = "+" THEN
            COMPUTE CODE-POS = CODE-POS + ARG
          ELSE 
            COMPUTE CODE-POS = CODE-POS - ARG
          END-IF
       END-IF.

import { SolveFunc } from './types';

export const solve: SolveFunc = (lines) => {
  lines = lines.filter((l) => l.length > 0);

  for (let i = 0; i < lines.length; i++) {
    const line = lines[i];
    if (line.startsWith('acc')) {
      continue;
    }
    const chunks = line.split(' ');
    const newLine = [swap(chunks[0]), chunks[1]].join(' ');
    const oldLine = line;
    lines[i] = newLine;

    const res = vm(lines);
    if (res === -1) {
      lines[i] = oldLine;
      continue;
    }
    return res;
  }
};

const swap = (op) => {
  if (op === 'nop') {
    return 'jmp';
  } else {
    return 'nop';
  }
};
const vm = (lines: string[]): number => {
  //   console.log(lines);
  let acc = 0;
  let i = 0;
  const seen = new Set();
  while (i < lines.length) {
    if (seen.has(i)) {
      return -1; // ew
    }
    seen.add(i);

    const [op, arg] = lines[i].split(' ');

    if (op === 'nop') {
      // pass
      i++;
    } else if (op === 'acc') {
      acc += parseInt(arg);
      i++;
    } else if (op === 'jmp') {
      i += parseInt(arg);
    }
  }
  return acc;
};

public record Instruction(string Operation, int Value);

public class BootSequence
    {
        List<int> history = new();

        public int Accumulator { get; private set; }

        public bool Run(Instruction[] instructions)
        {
            int i = 0;
            while(i < instructions.Length)
            {
                if (history.Contains(i))
                {
                    return false;
                }

                switch (instructions[i].Operation)
                {
                    case "nop":
                        history.Add(i);
                        i++;
                        break;
                    case "acc":
                        history.Add(i);
                        Accumulator += instructions[i].Value;
                        i++;
                        break;
                    case "jmp":
                        history.Add(i);
                        i += instructions[i].Value;
                        break;
                    default:
                        break;
                }
            }

            return true;
        }
    }

public class Part1 : Puzzle<IEnumerable<Instruction>, int>
    {
        public override int SampleAnswer => 5;

        public override IEnumerable<Instruction> ParseInput(string rawInput)
            => rawInput
                .Split(Environment.NewLine)
                .Where(line => line.Length > 0)
                .Select(ParseInstruction);

        Instruction ParseInstruction(string line)
        {
            string op = line[..3];
            int.TryParse(line[4..], out int val);

            return new Instruction(op, val);
        }

        public override int Solve(IEnumerable<Instruction> input)
        {
            var bootSeq = new BootSequence();
            bootSeq.Run(input.ToArray());
            return bootSeq.Accumulator;
        }
    }

    public class Part2 : Part1
    {
        public override int SampleAnswer => 8;

        public override int Solve(IEnumerable<Instruction> input)
        {
            int count = input.Count();
            for (int i = 0; i < count; i++)
            {
                var aInput = input.ToArray();
                var bootSeq = new BootSequence();

                SwapOp(ref aInput[i]);

                if (bootSeq.Run(aInput))
                {
                    return bootSeq.Accumulator;
                };
            }

            throw new Exception("no solution found!");
        }

        private void SwapOp(ref Instruction instruction)
        {
            instruction = instruction with { Operation = instruction.Operation == "nop" ? "jmp" : "nop" };
        }
    }

function accumulatorp1()
{
  let input = document.querySelector('pre').innerHTML.trim();

  let instructions = input.split('\n');

  let sum = 0;

  for(let ii = 0; ii < instructions.length; ii++)
  {
    let [ins, val] = instructions[ii].split(' ');
    if(ins == '')
    {
      break;
    }
    switch(ins)
    {
      case 'acc':
        sum += parseInt(val, 10);        
        break;
      case 'jmp':
        ii += (parseInt(val, 10)-1);
        break;
    }

    instructions[ii] = '';
  }

  return sum;
}

function accumulatorp2()
{
  let input = document.querySelector('pre').innerHTML.trim();

  let instructions = input.split('\n');

  let sum = 0;

  for(let wrong = 0; wrong < instructions.length; wrong++)
  {
    let fail = false;
    let [wins, wval] = instructions[wrong].split(' ');
    let inscpy = instructions.slice();
    sum = 0;
    if(wins == 'nop')
    {
      inscpy[wrong] = 'jmp ' + wval;
    }
    else if(wins == 'jmp')
    {
      inscpy[wrong] = 'nop ' + wval;
    }

    for(let ii = 0; ii < inscpy.length; ii++)
    {
        let [ins, val] = inscpy[ii].split(' ');
        if(ins == '')
        {
        fail = true;
        break;
        }
        switch(ins)
        {
        case 'acc':
            sum += parseInt(val, 10);        
            break;
        case 'jmp':
            ii += (parseInt(val, 10)-1);
            break;
        }

        inscpy[ii] = '';
    }
    if(!fail)
    {
      break;
    }
  }

  return sum;
}

defmodule BootLoader do
  def instr("nop " <> _value, acc, ptr) do {acc, ptr + 1} end
  def instr("acc " <> value, acc, ptr) do
    {acc + String.to_integer(value), ptr + 1}
  end
  def instr("jmp " <> value, acc, ptr) do
    {acc, ptr + String.to_integer(value)}
  end

  def execute(lines, seen, acc, ptr) do
    IO.puts("Executing #{ptr}")
    cond do
      ptr in seen ->
        IO.puts("already seen!")
        false
      ptr == length(lines) ->
        IO.puts("final result #{acc}")
        true
      true ->
        {new_acc, new_ptr} = instr(Enum.at(lines, ptr), acc, ptr)
        execute(lines, [ptr | seen], new_acc, new_ptr)
    end
  end

  def get_replacement("nop" <> x) do
    "jmp" <> x
  end

  def get_replacement("jmp" <> x) do
    "nop" <> x
  end

  def get_replacement(foo) do foo end

  def try_replacement(lines, rep_index) do
    rep = get_replacement(Enum.at(lines, rep_index))
    lines2 = List.replace_at(lines, rep_index, rep)
    if not execute(lines2, [], 0, 0) do
      try_replacement(lines, rep_index + 1)
    end
  end

  def main() do
    {:ok, code} = File.read("8.txt")
    lines = String.split(code, "\n")
    lines = List.delete_at(lines, length(lines)-1)
    IO.puts("program size: #{length(lines)}")
    try_replacement(lines, 0)
  end
end

BootLoader.main()

require 'benchmark'

class Instruction
  attr_reader :operation, :argument

  def self.fix(instruction)
    new(instruction.operation == 'nop' ? 'jmp' : 'nop', instruction.argument)
  end

  def initialize(operation, argument)
    self.operation = operation
    self.argument = argument
  end

  private

  attr_writer :operation, :argument
end

class Program
  def self.from_lines(lines)
    Program.new(lines.map { |line| Instruction.new(*line.split(' ')) })
  end

  def initialize(instructions)
    self.instructions = instructions
    self.pointer = 0
    self.accumulator = 0
    self.ran = {}
  end

  def current
    self[pointer]
  end

  def ran_to_completion?
    pointer >= instructions.length || pointer < 0
  end

  def ran_current_instruction?
    self.ran[self.pointer]
  end

  def fork
    ForkedProgram.new(instructions, pointer, accumulator, ran)
  end

  def run!
    return accumulator if ran_to_completion?
    return false if ran_current_instruction?

    if forkable?
      forked_result = fork.run!

      return forked_result if forked_result != false
    end

    mark_as_ran!

    case current.operation
    when 'nop'
      self.pointer += 1
    when 'acc'
      self.accumulator += current.argument.tr('+', '').to_i
      self.pointer += 1
    when 'jmp'
      self.pointer += current.argument.tr('+', '').to_i
    else
      raise "Unknown operation #{current.operation}(#{current.argument})"
    end

    run!
  end

  protected

  attr_accessor :instructions, :pointer, :accumulator, :ran

  def forked?
    false
  end

  private

  def [](instruction)
    instructions[instruction]
  end

  def []=(instruction, replacement)
    instructions[instruction] = replacement
  end

  def mark_as_ran!
    ran[pointer] = true
  end

  def forkable?
    return false if forked?

    current.operation == 'nop' || current.operation == 'jmp'
  end
end

class ForkedProgram < Program
  def initialize(instructions, pointer, accumulator, ran)
    self.instructions = instructions.dup
    self.ran = ran.dup
    self.pointer = pointer
    self.accumulator = accumulator

    fix!
  end

  def fork
    raise "Can't fork a forked program"
  end

  protected

  def forked?
    true
  end

  private

   def fix!
    self[pointer] = Instruction.fix(current)
  end
end


instructions = File
  .read('input.txt')
  .split(/\n/)

Benchmark.bmbm do |b|
  b.report do
    program = Program.from_lines(instructions)
    puts program.run!

  end
end

def boot(bootcode):
    acc = 0
    visited = set()
    pos = 0

    while True:
        if pos >= len(bootcode):
            return (acc, True)
        if pos in visited:
            return (acc, False)
        op, n = bootcode[pos].split(' ')
        n = int(n)
        visited.add(pos)
        if op == "nop":
            pos += 1
        elif op == "acc":
            acc += n
            pos += 1
        elif op == "jmp":
            pos += n    


def swap_op(line):
    op, n = line.split(' ')
    if op == "nop": op = "jmp"
    elif op == "jmp": op = "nop"
    # leave acc unaffected
    return " ".join((op, n))
    #return "jmp" if op == "nop" else "nop"


def fix(bootcode):
    val, terminated = boot(bootcode)
    if terminated: return val, terminated
    for i, l in enumerate(bootcode):
        # don't modify the original
        code_copy = [l for l in bootcode]
        code_copy[i] = swap_op(l)
        val, terminated = boot(code_copy)
        if terminated: return val, terminated
        #bootcode[i] = swap_op(l)
    return val, False



bootcode = [r.strip() for r in open('input.txt')]

acc, term = boot(bootcode)
print(f"Part 1: the original bootcode terminates {'' if term else 'ab'}normally with accumulator value {acc}")

acc, term = fix(bootcode)
print(f"Part 2: the fixed bootcode terminates {'' if term else 'ab'}normally with accumulator value {acc}")