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

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

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

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) 

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

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) 

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

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 } 

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