DEV Community

Cover image for Advent of Code 2020 Solution Megathread - Day 8: Handheld Halting
Ryan Palo
Ryan Palo

Posted on • Updated on

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
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (25)

Collapse
 
neilgall profile image
Neil Gall • Edited

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

}
Enter fullscreen mode Exit fullscreen mode

Full code

Collapse
 
aspittel profile image
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))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
benwtrent profile image
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
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
bgaster profile image
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)
Enter fullscreen mode Exit fullscreen mode
Collapse
 
mustafahaddara profile image
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;
};
Enter fullscreen mode Exit fullscreen mode
Collapse
 
kudostoy0u profile image
Kudos Beluga • Edited

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")))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
readyready15728 profile image
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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
readyready15728 profile image
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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
dirkfraanje profile image
Dirk Fraanje (the Netherlands) • Edited

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

Enter fullscreen mode Exit fullscreen mode
Collapse
 
galoisgirl profile image
Anna • Edited

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.
Enter fullscreen mode Exit fullscreen mode
Collapse
 
harrygibson profile image
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}")
Enter fullscreen mode Exit fullscreen mode
Collapse
 
mellen profile image
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;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
_bigblind profile image
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()
Enter fullscreen mode Exit fullscreen mode
Collapse
 
sleeplessbyte profile image
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
Enter fullscreen mode Exit fullscreen mode
Collapse
 
kudostoy0u profile image
Kudos Beluga • Edited

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);
}
Enter fullscreen mode Exit fullscreen mode