Advent of Code 2020 Solution Megathread - Day 8: Handheld Halting

I don't know about you, but I struggled to bend C to my will yesterday. Had to do it in Python to stay on top, but now that I've done it in Python, I think I could probably make the C code (that I cleverly deleted all trace of) work. So that's great. Anyways, today is a new day!

The Puzzle

I'm so very happy. This makes up for anything that yesterday did to me. In today’s puzzle, we're debugging machine code! I honestly love all of the puzzles like this. I loved the Intcode challenges from last year, and I'm hoping there are more of these to come. We're writing a sort of machine-code interpreter to parse through and evaluate this code to help a kid play his handheld game on the plane! It's for a good cause!

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

I've got a dope new automated tool to help me fetch and tabulate the number different language submissions each day! It helps the tool if you either write what language you used in your comment or (even better) make your code block language specific with syntax highlighting.

Updated 03:08PM 12/12/2020 PST.

Language	Count
Python	4
Ruby	3
Rust	3
JavaScript	3
C#	1
Haskell	1
TypeScript	1
COBOL	1
Fsharp	1

Merry Coding!

Comments

[Neil Gall]

I knew Rust would shine for the machine simulations. Let's hope for more of these.

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));        
    }

}

Full code

[Ali Spittel]

Python!

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))

[Mustafa Haddara]

as soon as i saw this, i remembered the IntCode shenanigans from last year...can't wait til we're forking off 4 copies of this VM to run in parallel or talk to each other or whatever :)

ts solution was pretty compact here, although I got tripped up by the sneaky blank line at the end of the input! I've been doing this for a few years and we're 8 days in, you'd think I'd remember that by now haha.

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;
};

[Benjamin Trent]

Rust! I am doing WAY too much object copying. I think I could get the same results by passing vector of references around. But, wanted to not think too much :)

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
}

[Benedict Gaster]

hello! Sorry did not post yesterday as was visiting my mum in hospital, but completed day 7 this morning, which I have to say was a bit messy!

Day 8 on the other hand seems a lot of fun and I'm remembering more Haskel (and cateory theory) each new day. It's been a while :-) Anywhy, below is today's soloution(s). I did give into using Parser combinators as it just seemed simplier, but other than that it is all fairly standard.

-- 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)

[Mike Gasparelli]

Well this felt a lot easier than yesterday... Looking forward to see whether we're going to be expanding on this one in the coming days...

BootSequence

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;
        }
    }

Part1

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;
        }
    }

Part 2

    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" };
        }
    }

[Christopher Nilsson]

Python

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)

My solution for day 08, where I have tried to make it easy to extend. Just in case we have to continue building on this another day 😬 (getting some intcode flashbacks from 2019...)

[Frederik 👨‍💻➡️🌐 Creemers]

Here's my solution for part 2 in Elixir. It shares most of its code with part 1, so I don't think it's all that interesting to share both.

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()

[Christopher Kruse]

Rust solution.

I spent longer than I care to admit trying to figure out the best way to access/use the data from the initial input in a mutable way: I started with returning the Program from the input parser, but nothing could be mutable that way; I tried boxes, I tried Rc, (both of which I haven't really played around with before); finally settled on making them Clone-able and just duplicating it for the run.

There's some control flow stuff in here that I'm sure there are better ways of solving (if you know or have a suggestion, please drop it in!).

Also gave me nightmares of last year's opcode parser... 😱

As always, on Github.

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
}

[Neil Gall]

I think the insight you need is to separate the mutable from the immutable state. The program is immutable (except for the modifications in part 2) but the machine state is mutable. The instructions are immutable but the record of visiting them is mutable. Cloning the whole program and changing one instruction is the right approach however. Good work!

[Derk-Jan Karrenbeld]

Another OOP solution in Ruby.

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