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

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

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

[Kudos Beluga]

Here's a javascript solution. Toggle part2 to false or true depending on what part you're on.

let fs = require("fs"), acc = 0, taken = [],part2=true;
const check = (data,index,returnfunc=()=>{}) => {
if (taken.indexOf(index) > -1) returnfunc(acc)
  else {
  taken.push(index)
  let dedata = data[index]
  if (!dedata) console.log(acc)
  else {
  switch (dedata.slice(0,3)) {
    case "nop": check(data,index+1,returnfunc)
    break;
    case "acc": acc = acc + Number(dedata.match(/(?<=.{3} ).+/i)[0])
     check(data,index+1,returnfunc)
    break;
    case "jmp": check(data,index+Number(dedata.match(/(?<=.{3} ).+/i)[0]),returnfunc)
    break;
  }}}}
  const controller = data => {
  const returnfunc = val => {if (!part2) console.log(val)}
  if (part2) {
   for (let i in data) {
     let modifieddata = [...data];
     if ((data[i].slice(0,3) != "acc")) {
    if (data[i].slice(0,3) == "nop") modifieddata[i] = "jmp " + data[i].slice(4,data[i].length) 
    else modifieddata[i] = "nop " + data[i].slice(4,data[i].length) 
    taken = [], acc = 0, check(modifieddata,0) 
     }}} else check(data,0,returnfunc) }
fs.readFile("input.txt","utf8", (err,data) => controller(data.split("\n")))

[readyready15728]

Ruby, part 1:

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

[readyready15728]

Ruby, part 2:

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

[Dirk Fraanje (the Netherlands)]

My solution in C#
Tried to make it look decent with the Operation enum and an Instruction class:

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

[Anna]

COBOL. I'm struggling... nothing yesterday and only part 1 today

   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.

[Harry Gibson]

This was much more enjoyable after the utter faff that was day 7

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

[Matt Ellen]

More javascript, less regex. I get the feeling that I'm going to have to give up on my regex quest.

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

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

[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

[Kudos Beluga]

Functional Programming approach with relatively fast Rust code

use std::fs;
fn parse(toparse:&str) -> i64 { toparse.parse::<i64>().expect("Failed to parse number") }
fn part1(data: &Vec<(i64,i64)>, taken: &mut Vec<i64>,index: i64, acc: i64,part2:bool) -> i64 { 
  if taken.contains(&index) {
    if !part2 {acc} else {0}
  } else {
    if data.get(index as usize) == None { return acc };
    let cidx = data[index as usize];
    taken.push(index);
    match cidx.0 {
    2 => part1(&data,taken,index+1,acc+cidx.1,part2),
    0 => part1(&data,taken,index+cidx.1,acc,part2),
    _ => part1(&data,taken,index+1,acc,part2)
    }}}
fn part2(mut data: Vec<(i64,i64)>) -> i64 {
  let datalen: usize = data.len();
  for i in 0..datalen {
    let currentelem = data[i];
    let switch: i64 = match currentelem.0 {
      0 => 1,
      1 => 0,
      _ => continue
    };
    data[i] = (switch,currentelem.1);
    let val = part1(&data, &mut Vec::new(), 0i64, 0i64, true);
    data[i] = (currentelem.0,currentelem.1);
    if val != 0 { return val };
  }return 0;}
fn main() {
  let data = fs::read_to_string("./day8.txt").unwrap().split("\n").collect::<Vec<_>>().iter().map(|x| {
    let twoparts = x.split(" ").collect::<Vec<_>>();
    let part1 = match twoparts[0] {
      "jmp" => 0,
      "nop" => 1,
      "acc" => 2,
      _ => 666
    };
    (part1,parse(twoparts[1]))
  }).collect::<Vec<_>>();
  let part1answer = part1(&data,&mut Vec::new(),0i64,0i64,false);
  let part2answer = part2(data);
  println!("Answer for Part 1: {}\nAnswer for Part 2: {}",part1answer,part2answer);
}

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

[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!

[Yuan Gao]

I solved Part 2 in python but uh... in a slightly unconventional way. I re-wrote the CPU so that it used Redis for memory instead of variables, wrote functions so it could operate one cycle at a time every time the script was run, built it into a Docker image, and pushed it to a registry, and then wrote an Airflow DAG to orchestrate running of the CPU inside a kubernetes cluster.

And then had it brute-force the solution by running it one cycle per Kubernetes Pod, deployed by Airflow, until it found the answer and sent it to me via Slack.

Blog: dev.to/meseta/advent-of-code-day-0...

[Ryan Palo]

Omg you’re a hero. This is so very impressive

[Ryan Palo]

Had a much better time today. I'm very happy with how this came out.

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

[Kai]

Writing today's solution went pretty fast. But oh man, it takes longer and longer to write these step-by-step tutorials. I'll have to see whether Life™ allows me to continue this until Xmas:

[Advent of Code 2020] Day 8 Step-by-Step Tutorial (TypeScript)

Kai ・ Dec 8 ・ 9 min read

#adventofcode #tutorial #typescript #javascript

[Thibaut Patel]

My Javascript walkthrough: