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

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

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)

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

   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.

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

require 'set'

instructions = []

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

acc = 0
i = 0
visited = Set.new

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

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

puts acc

require 'set'

instructions = []

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

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

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

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

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

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

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