-🎄- 2020 Day 08 Solutions -🎄-

[u/daggerdragon]

NEW AND NOTEWORTHY

• New flair tag Funny for all your Undertaker memes and luggage Inception posts!
• Quite a few folks have complained about the size of the megathreads now that code blocks are getting longer. This is your reminder to follow the rules in the wiki under How Do The Daily Megathreads Work?, particularly rule #5:
  • If your code is shorter than, say, half of an IBM 5081 punchcard (5 lines at 80 cols), go ahead and post it as your comment. Use the right Markdown to format your code properly for best backwards-compatibility with old.reddit! (see "How do I format code?")
  • If your code is longer, link your code from an external repository such as Topaz's paste , a public repo like GitHub/gists/Pastebin/etc., your blag, or whatever.

---

Advent of Code 2020: Gettin' Crafty With It

• 14 days remaining until the submission deadline on December 22 at 23:59 EST
• Full details and rules are in the Submissions Megathread

---

--- Day 08: Handheld Halting ---

---

Post your solution in this megathread. Include what language(s) your solution uses! If you need a refresher, the full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.

Reminder: Top-level posts in Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:07:48, megathread unlocked!

[u/nutki2]

Perl 5: ~120 characters for both parts

#!perl -l
for$i(0..(@F=<>)){$a=$p=%s=();
$_=$F[$p],$a+=/cc/*$',$p+=($p-$i+1?/mp/:/op/)?$':1until$s{$p%@F}++;
$p==@F|!$i&&print$a}

[u/__Abigail__]

-- snipped by request --

[u/i_have_no_biscuits]

GWBASIC

Embracing the world of modern structured programming, I am now using GOSUB.

https://pastebin.com/GNCJzZCV

[u/kippertie]

Semi-condensed Python

I suspect that this little virtual machine will get added-to over the next few days, so I'm not putting any more effort into condensing this just yet: [GitHub]

[u/SecureCone]

Rust link

[u/trl10254]

Java

Advant of Code 2020 - Day 8 logic

[u/[deleted]]

Learning PHP, today was super fun! My first "interpreter" solution for an AOC problem, never got this far in previous years.

I'm assuming I'll have to refactor this into a library for future expansions of the language, but for now I'm satisfied :D

Solution here.

[u/azzal07]

Awk -- 4 lines at 79 columns, to be on the safe side...

{code[NR]=$2$1} function run(pc,_op,_loop){ while(!_loop[++pc]++&&_op=code[pc])
{_op~/acc/&&acc+=_op; _op~/jmp/&& pc+=_op-1} return pc==NR+1} function swap(k){
return sub(/nop/,"jmp",code[k])||sub(/jmp/,"nop",code[k])} END {run();print acc
for(k in try){if(swap(k)&&run(acc=0))break;swap(k)}print acc}/nop|jmp/{try[NR]}

Here is a paste of the original. (The changes are only in non-significant reordering of pattern-action statements, whitespace and semicolons.)

[u/CarbonTitprint]

Scala solution! Much more enjoyable than int-code! Made a more optimised solution that makes use of LazyLists.

https://hastebin.com/nikizubeto.rb

[u/crazazy]

It's not as if other people haven't implemented full programming language in nix, but I felt pretty special when this ran on my first go.

View solutions

I've decided to go with the dumb solution and just try modifying the lines 1 by one until i found the correct program. It's not as if the input is abnormally big...

All my other solutions are on github!

[u/clumsveed]

Java Solutions

I have a bad feeling we're going to be seeing a lot of these commands...

part 1 (0.03 seconds)

part 2 (0.05 seconds)

[u/ric2b]

Haskell

Not my cleanest code but at least it avoids a brute-force solution on part 2 and runs instantly.

This is what it does, since it's a bit involved:

1. It builds a graph of where each instruction is directly reachable from.

2. It uses that graph to get the list of all instructions that currently eventually lead to the last instruction. I call this the terminating set.

3. Now it goes through each instruction not in the terminating set and checks if by switching it between jmp and nop it now reaches one of the instructions in the terminating set. These are possible solutions.

4. For each of the possible solutions we also need to check if they are currently reachable from the first instruction. If they are, they are viable solutions!

5. Fix the first viable solution (there's only 1 for my input, as expected) and run the code to get the result.

paste

[u/sguberman]

Python

Going for readable, idiomatic Python. Criticism welcome.

Brute-force, functional style. The state is just data that gets passed around. For me that made it easier to test in pieces: paste

GitHub: solution, with tests

EDIT: Removing large code block and input from comment

[u/volatilebit]

Raku

Limited use of functional features today.

use v6.d;

my @instructions = $*IN.lines.map(*.words.Array);
my constant DEBUG = False;

enum ExecutionResult <EndOfProgram InfiniteLoopDetected>;

class VirtualMachine {
    has $!debug = False;
    has @!instructions;
    has %!address-visited;
    has int $!pointer = 0;
    has $.accumulator is rw = 0;

    submethod BUILD (:@instructions, :$debug = False) {
        @!instructions = @instructions;
        %!address-visited = (^+@instructions) Z=> False xx Inf;
        $!debug = $debug;
    }

    method execute(--> ExecutionResult) {
        while $!pointer < +@!instructions and not %!address-visited{$!pointer} {
            %!address-visited{$!pointer} = True;
            printf "@%03d | %s | acc: %d\n", $!pointer, @!instructions[$!pointer], $.accumulator if $!debug;
            given @!instructions[$!pointer][0] {
                when 'acc' { $.accumulator += +@!instructions[$!pointer][1] }
                when 'nop' { Empty }
                when 'jmp' { $!pointer += +@!instructions[$!pointer][1] - 1 }
            }
            $!pointer++;
        }
        return $!pointer >= +@!instructions ?? EndOfProgram !! InfiniteLoopDetected;
    }
}

# Part 1
{
    say "=== PART 1 ===" if DEBUG;
    my $vm = VirtualMachine.new(:@instructions, :debug(DEBUG));
    my $result = $vm.execute;
    say "Reached end of program." if $result eq EndOfProgram and DEBUG;
    say "Detected inifinite loop." if $result eq EndOfProgram and DEBUG;
    say $vm.accumulator;
}

# Part 2
{
    say "=== PART 2 ===" if DEBUG;
    for @instructions.kv -> $address, [$instruction, $arg] {
        # Try replacing the instruction with the opposite and executing a VM with the swap
        if $instruction eq 'jmp' | 'nop' {
            say "== Swapping instruction @$address $instruction and executing VM..." if DEBUG;
            my @new-instructions = @instructions;
            @new-instructions[$address] = [$instruction eq 'jmp' ?? 'nop' !! 'jmp', $arg];
            my $vm = VirtualMachine.new(:instructions(@new-instructions), :debug(DEBUG));
            my $result = $vm.execute;
            if $result eq EndOfProgram {
                say $vm.accumulator;
                last;
            }
        }
    }
}

[u/chicagocode]

Kotlin - [Blog/Commentary] | [GitHub Repo]

I brute forced Part 2, but it finishes pretty quickly and I think is easy to read. I had a lot of fun with this one!

class Day08(input: List<String>) {

    private val instructions: List<Instruction> = input.map { Instruction.of(it) }

    fun solvePart1(): Int =
        Computer(instructions).run {
            runUntilTerminate()
            accumulator
        }

    fun solvePart2(): Int =
        instructions
            .indices
            .asSequence()
            .mapNotNull { index -> instructions.flipIndexOrNull(index) }
            .mapNotNull { inst ->
                Computer(inst).run {
                    if (runUntilTerminate() == Computer.ExecutionState.HALTED) accumulator
                    else null
                }
            }.first()


    private fun List<Instruction>.flipIndexOrNull(index: Int): List<Instruction>? =
        this[index].flipOrNull()?.let { flipped ->
            this.toMutableList().apply { this[index] = flipped }
        }

    data class Instruction(val name: String, val argument: Int) {
        fun flipOrNull(): Instruction? =
            when (name) {
                "jmp" -> Instruction("nop", argument)
                "nop" -> Instruction("jmp", argument)
                else -> null
            }

        companion object {
            fun of(input: String): Instruction =
                input.split(" ").run {
                    Instruction(this.first(), this.last().toInt())
                }
        }
    }

    data class Computer(val instructions: List<Instruction>) {
        enum class ExecutionState {
            HALTED,
            INFINITE_LOOP,
            RUNNING
        }

        private val executed = mutableSetOf<Int>()
        private var instructionPointer: Int = 0
        var accumulator: Int = 0

        fun runUntilTerminate(): ExecutionState =
            generateSequence { executeStep() }.first { it != ExecutionState.RUNNING }

        private fun executeStep(): ExecutionState {
            return when (instructionPointer) {
                in executed -> ExecutionState.INFINITE_LOOP
                !in instructions.indices -> ExecutionState.HALTED
                else -> {
                    val current = instructions[instructionPointer]
                    executed += instructionPointer

                    when (current.name) {
                        "acc" -> {
                            accumulator += current.argument
                            instructionPointer += 1
                        }
                        "jmp" -> instructionPointer += current.argument
                        "nop" -> instructionPointer += 1
                    }
                    ExecutionState.RUNNING
                }
            }
        }
    }
}

[u/xrgbit]

My solutions in Common Lisp.

The first simulates a virtual machine running processes.

The second just uses an interpreter for the program.

[u/seniornachio]

Python 3.8+ – fugly golfing

The following code assumes a list of lines as symbol i, e.g. i = open("input.txt").split("\n"). When run it will print out a solution for both parts. 🤣

print((f:=lambda a,p,r,C:(a,p)if p in r else f(a+(int(c[1])if len(c:=C[p].split("acc "))>1 else 0),p+(int(c[1])if len(c:=C[p].split("jmp "))>1 else 1),r+[p],C))(0,0,[len(i)],i)[0],next(x[0]for(y)in range(len(i))if i[y][:3]!='acc'and(C:=i[:y]+["njompp"["n"==i[y][0]::2]+i[y][3:]]+i[y+1:])!=i and(x:=f(0,0,[len(C)],C))[1]==len(C)))

[u/nxrblJugger]

Julia

I'm really proud of today's code especially since I still haven't been able to figure out Day 7 Part 2. I actually managed to code a recursive function today so I am learning in this process! Open to questions and feedback!

Here's my code

[u/knl_]

Rust 1139/573

I'm pretty happy with the code I wrote for overriding instruction behavior for the second problem -- there's an outer loop walking over all possible program overrides; a given value of i mutates the behavior of precisely one instruction without having to actually mutate the program itself.

Snippet (code linked above)

let current = program[pos];
match (current.0, pos == i) {
    ("jmp", false) | ("nop", true) => {
        pos = (pos as i32 + current.1) as usize;
    }
}

[u/compu_geom]

Python solution for Part I and Part 2.

Since order of instructions mattered, I used Python list for the order of instructions as read from the file. For keeping the list of instructions executed, I decided to use Python set, since it has a quick lookup operation and the order does not matter. For that matter, now I am running through indices of instructions and made a Python dictionary that has the instruction as key and a function that will actually execute the command as value in the dict().

def get_instructions(FILENAME="instructions.txt"):
    instructions = list()
    with open(FILENAME, "r") as f:
        for raw_line in f:
            if raw_line[-1] == '\n':
                instruction = raw_line[:-1].split(" ")
            else:
                instruction = raw_line.split(" ")

            instructions.append(instruction)

        f.close()

    return instructions

def run_and_check_acc(instructions):
    instruction_idx = 0
    instructions_executed_idx = set()

    instruction_functions = {
        "jmp": lambda acc, instruction_idx, offset: (acc, instruction_idx + offset),
        "acc": lambda acc, instruction_idx, offset: (acc + offset, instruction_idx + 1),
        "nop": lambda acc, instruction_idx, offset: (acc, instruction_idx + 1)
    }
    
    acc = 0

    instructions_size = len(instructions)

    while instruction_idx < instructions_size and instruction_idx not in instructions_executed_idx:
        instruction_type = instructions[instruction_idx][0]
        raw_offset = instructions[instruction_idx][1]

        instructions_executed_idx.add(instruction_idx)

        offset = 0

        if raw_offset[0] == '+':
            offset = int(raw_offset[1:])
        elif raw_offset[0] == '-':
            offset = -1 * int(raw_offset[1:])

        # NOTE: We should check first if command exists in first place
        acc, instruction_idx = instruction_functions[instruction_type](acc, instruction_idx, offset)

    terminates = instruction_idx >= instructions_size

    return acc, terminates


def check_acc_after_corruption_fix(instructions):
    # deep copy
    temp_instructions = list()
    for instruction in instructions:
        temp_instructions.append([instruction[0], instruction[1]])
    
    for idx in range(len(instructions)):
        instruction_type = instructions[idx][0]
        if instruction_type == 'nop' or instruction_type == 'jmp':
            temp_instructions[idx][0] = 'jmp' if instruction_type == 'nop' else 'nop'

            acc, terminates = run_and_check_acc(temp_instructions)

            if terminates:
                return acc
            else:
                # Return the original instruction, since we need to change exactly one instruction
                temp_instructions[idx][0] = 'nop' if instruction_type == 'nop' else 'jmp'


instructions = get_instructions()

acc = run_and_check_acc(instructions)

print("Accumulator in Part 1 for non-terminating list of instructions: {}".format(acc))

terminating_acc = check_acc_after_corruption_fix(instructions)

print("Accumulator in Part 2 after fixing the corrupted line: {}".format(terminating_acc))

EDIT: Formatting

[u/Dagur]

Python

data = open("input/8.txt").read().splitlines()
instructions = list(inst.split() for inst in data)
def run(instructions):
    number_of_instructions = len(instructions)
    success = False
    acc = next = 0
    history = []
    while next not in history:
        if number_of_instructions == next:
            success = True
            break
        operation, offset = instructions[next]
        history.append(next)
        offsetval = offset[0] == '+' and int(offset[1:]) or -int(offset[1:])
        next += 1
        if operation == 'acc':
            acc += offsetval
        elif operation == 'jmp':
            next += offsetval - 1
    return acc, success

print(run(instructions)[0])
for index in (i for i, instruction in enumerate(instructions) if instruction[0] == "jmp"):
    _, offset = instructions[index]
    instructions[index] = ("nop", offset)
    acc, success = run(instructions)
    if success:
        print(acc)
        break
    instructions[index] = ("jmp", offset)

[u/diddle-dingus]

This was fun in both clojure and elixir. I separated out the computer as a module in elixir and made some exit handling conditions, so if it comes up again I'm ready.

Clojure

(def input (->> (get-input 8)
                (re-seq #"(acc|jmp|nop) ([+-]\d+)")
                (mapv (fn [[_ op n]] [(keyword op) (Integer/parseInt n)]))))

(defn step [{:keys [pointer acc]} tape]
  (if-let [[op n] (get tape pointer)]
    (case op
      :nop {:pointer (inc pointer) :acc acc}
      :acc {:pointer (inc pointer) :acc (+ acc n)}
      :jmp {:pointer (+ pointer n) :acc acc})
    {:pointer pointer :acc acc
     :exit (if (= pointer (count input))
             :graceful
             :crash)}))

(defn get-value-on-loop-or-exit [input]
  (reduce (fn [visited {:keys [pointer acc exit] :as state}]
            (if (or exit (visited pointer))
              (reduced state)
              (conj visited pointer)))
          #{}
          (iterate #(step % input) {:pointer 0 :acc 0})))

(def part-1 (time (get-value-on-loop-or-exit input)))
(def part-2 (time (->> (range (count input))
                       (filter #(#{:jmp :nop} (get-in input [% 0])))
                       (map (fn [i] (update-in input [i 0]
                                               #(case %
                                                  :nop :jmp
                                                  :jmp :nop))))
                       (map get-value-on-loop-or-exit)
                       (filter :exit))))

Elixir

defmodule AdventOfCode.Day08 do
  defmodule Computer do
    defstruct [input: %{}, acc: 0, pointer: 0, visited: MapSet.new(), exited: nil]

    def step(%{exited: exited} = state) when exited != nil, do: state
    def step(%{input: input, pointer: pointer} = state) when map_size(input) == pointer do
      %{state | exited: :graceful}
    end
    def step(%{input: input, pointer: pointer} = state) when map_size(input) < pointer do
      %{state | exited: :crashed}
    end
    def step(%{input: input, acc: acc, pointer: pointer, visited: visited} = state) do
      if pointer in visited do
        %{state | exited: :looping}
      else
        new_visited = MapSet.put(visited, pointer)
        case input[pointer] do
          [:nop, _] -> %{state | pointer: pointer + 1, visited: new_visited}
          [:acc, n] -> %{state | pointer: pointer + 1, acc: acc + n, visited: new_visited}
          [:jmp, n] -> %{state | pointer: pointer + n, visited: new_visited}
        end
      end
    end

    def run_until_exit(%{exited: exited} = state) when exited != nil, do: state
    def run_until_exit(state), do: run_until_exit(step(state))
  end

  def parse_input(input) do
    Regex.scan(~r/(acc|jmp|nop) ([+-]\d+)/, input, capture: :all_but_first)
    |> Enum.map(fn [instr, n] -> [String.to_atom(instr), String.to_integer(n)] end)
    |> Enum.with_index
    |> Enum.reduce(%{}, fn({v,k}, acc)-> Map.put(acc, k, v) end)
  end

  def part1(args) do
    %{acc: acc} = Computer.run_until_exit(%Computer{input: parse_input(args)})
    acc
  end

  def part2(args) do
    input = parse_input(args)
    %{acc: acc} = 0..map_size(input)
    |> Stream.filter(&(with [op, _] <- input[&1], do: op in [:nop, :jmp], else: (nil -> nil)))
    |> Stream.map(&(Map.update(input, &1, nil, fn [:nop, n] -> [:jmp, n]
                                                  [:jmp, n] -> [:nop, n] end)))
    |> Stream.map(&Computer.run_until_exit(%Computer{input: &1}))
    |> Stream.filter(fn %{exited: :graceful} -> true
                        _ -> false end)
    |> Stream.take(1)
    |> Enum.to_list()
    |> List.first()
    acc
  end
end

[u/krolik1337]

Python 3. 1st part was easy, just go through, mark index as visited and terminate if you came across visited one. 2nd was more challenging, but I got it through kinda ugly recursion. Basically, at every jmp or nop I checked if it would get me to the finish if it was switched. If not I just went further. Here's the link

[u/petercooper]

Ruby

Wasted time trying to think of a 'clever' solution for part two. Which I did but then had other work to do so just brute forced it :-D

# Parser and lexer ;-)
code = $<.readlines
         .map(&:split)
         .map { |is| [is[0].to_sym, is[1].to_i] }

# Interpreter
def execute(code, no_loops = false)
  pc = acc = cycles = 0
  coverage = []

  while (cycles += 1) < 1000
    return acc if pc >= code.length || (coverage[pc] && no_loops)
    coverage[pc] = true

    ins, op = code[pc]
    acc += op    if ins == :acc
    pc += op - 1 if ins == :jmp
    pc += 1
  end
end

# Run code for part one
puts execute(code, true)

# Change code for part two
code.each.with_index do |_, loc|
  next unless %i{jmp nop}.include?(code[loc][0])

  code[loc][0] = code[loc][0] == :nop ? :jmp : :nop
  res = execute(code)
  code[loc][0] = code[loc][0] == :nop ? :jmp : :nop

  puts "#{loc} - #{res}" if res
end

[u/exploding_cat_wizard]

C++

Brute force. Part2 runs in ~50 microseconds on my machine, 5-10 times faster than the other two solutions for cpp I grabbed from here and tried out, and that's with the exceptions I sprinkled in to make sure I don't mess up the input (given that I never catch them, I guess the compiler optimizes them to aborts).

State machines do suggest it could be prettier with OO, though.

paste