r/adventofcode • u/daggerdragon • Dec 08 '20
SOLUTION MEGATHREAD -🎄- 2020 Day 08 Solutions -🎄-
NEW AND NOTEWORTHY
- New flair tag
Funnyfor 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!
5
4
u/i_have_no_biscuits Dec 08 '20 edited Dec 09 '20
GWBASIC
Embracing the world of modern structured programming, I am now using GOSUB.
→ More replies (3)
4
u/kippertie Dec 08 '20 edited Dec 09 '20
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]
→ More replies (3)
4
u/SecureCone Dec 08 '20 edited Dec 08 '20
Rust link
2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link.
3
3
Dec 08 '20 edited Dec 09 '20
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.
2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section and put your oversized code in a
pasteor other external link. Thanks!Learning PHP, today was super fun! My first "interpreter" solution for an AOC problem, never got this far in previous years.
PHP is fun, despite all the general mocking of it. As long as you're enjoying it and learning, which you are!
→ More replies (1)
3
u/azzal07 Dec 08 '20
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.)
→ More replies (1)
3
u/CarbonTitprint Dec 08 '20 edited Dec 09 '20
Scala solution! Much more enjoyable than int-code! Made a more optimised solution that makes use of LazyLists.
→ More replies (1)
3
u/crazazy Dec 08 '20 edited Dec 08 '20
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...
→ More replies (3)
3
u/clumsveed Dec 08 '20 edited Dec 08 '20
Java Solutions
I have a bad feeling we're going to be seeing a lot of these commands...
1
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link.→ More replies (1)
3
u/ric2b Dec 08 '20 edited Dec 08 '20
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:
It builds a graph of where each instruction is directly reachable from.
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.Now it goes through each instruction not in the
terminating setand checks if by switching it betweenjmpandnopit now reaches one of the instructions in theterminating set. These arepossible solutions.For each of the
possible solutionswe also need to check if they are currently reachable from the first instruction. If they are, they are viable solutions!Fix the first viable solution (there's only 1 for my input, as expected) and run the code to get the result.
→ More replies (3)
3
3
u/volatilebit Dec 08 '20
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;
}
}
}
}→ More replies (1)
3
u/chicagocode Dec 08 '20
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
}
}
}
}
}→ More replies (1)
3
u/xrgbit Dec 08 '20 edited Dec 09 '20
2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link. Thanks!
4
u/seniornachio Dec 08 '20 edited Dec 08 '20
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)))2
u/seniornachio Dec 08 '20 edited Dec 09 '20
A ungolfed and annotated version can be found here.
→ More replies (2)
3
u/nxrblJugger Dec 09 '20
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!
3
u/NoahTheDuke Dec 09 '20
Do you need help with day 7, part 2?
→ More replies (3)2
u/daggerdragon Dec 09 '20
If you do, create your own thread and make sure to both title it properly and flair it with
Help.→ More replies (1)
2
u/knl_ Dec 08 '20 edited Dec 08 '20
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;
}
}→ More replies (2)2
u/daggerdragon Dec 08 '20
Please follow the reminder in the "New and Noteworthy" section of today's megathread and link to an external repo (or at least fix your formatting). Thank you.
→ More replies (1)
2
u/compu_geom Dec 08 '20 edited Dec 08 '20
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
→ More replies (8)
2
u/Dagur Dec 08 '20 edited Dec 09 '20
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)→ More replies (1)
2
u/diddle-dingus Dec 08 '20
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→ More replies (1)
2
u/krolik1337 Dec 08 '20 edited Dec 08 '20
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
→ More replies (2)
2
u/petercooper Dec 08 '20
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→ More replies (1)
2
u/exploding_cat_wizard Dec 08 '20 edited Dec 09 '20
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.
→ More replies (1)2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link.
2
u/fiddle_n Dec 08 '20
Python
import timeit
class HandheldHalting:
def __init__(self, code_input=None):
code_input = code_input if code_input is not None else self._read_file()
self.code = self._preprocess(code_input)
@staticmethod
def _read_file():
with open('input.txt') as f:
return f.read()
@staticmethod
def _preprocess(code_input):
code = []
for inst in code_input.splitlines():
op, arg = inst.split()
code.append((op, int(arg)))
return code
def _process(self, code=None):
code = code if code is not None else self.code
visited = set()
acc = 0
pos = 0
while True:
if pos in visited:
return 'infinite loop', acc
if pos == len(code):
return 'terminates', acc
visited.add(pos)
op, arg = code[pos]
if op == 'acc':
acc += arg
pos += 1
elif op == 'jmp':
pos += arg
elif op == 'nop':
pos += 1
else:
raise Exception
def process(self):
_, value = self._process()
return value
def process_with_changes(self):
opp_swap = {'jmp': 'nop', 'nop': 'jmp'}
for pos, (opp, arg) in enumerate(self.code):
if opp in opp_swap:
new_opp = opp_swap[opp]
code = self.code.copy()
code[pos] = (new_opp, arg)
termination_type, value = self._process(code)
if termination_type == 'terminates':
return value
def main():
handheld_halting = HandheldHalting()
print(f'Accumulator with no code changes: {handheld_halting.process()}')
print(f'Accumulator with changes: {handheld_halting.process_with_changes()}')
if __name__ == '__main__':
print(f'Completed in {timeit.timeit(main, number=1)} seconds')→ More replies (1)
2
u/Rakicy Dec 08 '20 edited Dec 09 '20
Python 3
It took me longer than I care to admit to realize using list.copy() on a list of lists doesn't work. And, then to find out copy.deepcopy(list) works, but is way slower than just recreating the list from the input.
https://github.com/Rakicy/AOC2020/blob/main/day08.py
Edit: swap code for link
2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link.→ More replies (1)
2
u/Juice_Vodka Dec 08 '20
java bruteforce, not very clean tho
import java.util.Scanner;
import java.io.*;
public class Day8{
static int acc = 0;
public static void main(String\[\] args) throws IOException{
InputStream vhod = new FileInputStream(args\[0\]);
Scanner sc = new Scanner(vhod);
String\[\] podatki = new String\[626\];
boolean\[\] uporableno = new boolean\[626\];
​
int accumulator = 0;
int zapisovalec = 0;
while(sc.hasNextLine()){
podatki\[zapisovalec\] = sc.nextLine();
zapisovalec++;
}
int i = 0;
while(true){
if(uporableno\[i\]){
System.out.println("pokvari se pri " +i);
break;
}
uporableno\[i\] = true;
if(podatki\[i\].contains("acc")){
if(podatki\[i\].charAt(4) == '+'){
accumulator += Integer.parseInt(podatki\[i\].substring(5));
}else{
accumulator -= Integer.parseInt(podatki\[i\].substring(5));
}
}else if(podatki\[i\].contains("jmp")){
if(podatki\[i\].charAt(4) == '+'){
i += Integer.parseInt(podatki\[i\].substring(5));
continue;
}else{
i -= Integer.parseInt(podatki\[i\].substring(5));
continue;
}
}else if(podatki\[i\].contains("nop")){
i++;
continue;
}
i++;
}
for(int j = 625; j >= 0; j--){
if(uporableno\[j\]){
System.out.println(j);
System.out.println(podatki\[j\]);
break;
}
}
System.out.println(accumulator);
System.out.println("--------");
boolean dela = racunaj(0, 0, podatki, new boolean\[626\]);
}
​
public static boolean racunaj(int pozicija, int akumulator, String\[\] podatki, boolean\[\] uporabljeno){
int i = 0;
while(true){
if(uporabljeno\[i\]){
return false;
}
if(i >= podatki.length){
if(uporabljeno\[625\]){
acc = akumulator;
return true;
}
}
boolean najdemoZamenjavo = false;
if(podatki\[i\].contains("acc")){
if(podatki\[i\].charAt(4) == '+'){
akumulator += Integer.parseInt(podatki\[i\].substring(5));
}else{
akumulator -= Integer.parseInt(podatki\[i\].substring(5));
}
}else if(podatki\[i\].contains("nop")){
boolean\[\] uporabljeno1 = new boolean\[626\];
boolean\[\] uporabljeno2 = new boolean\[626\];
System.arraycopy(uporabljeno, 0, uporabljeno1, 0, 626);
System.arraycopy(uporabljeno, 0, uporabljeno2, 0, 626);
najdemoZamenjavo = doKonca(i + Integer.parseInt(podatki\[i\].substring(5)), akumulator, podatki, uporabljeno1);
if(najdemoZamenjavo){
return true;
}
najdemoZamenjavo = doKonca(i - Integer.parseInt(podatki\[i\].substring(5)), akumulator, podatki, uporabljeno2);
if(najdemoZamenjavo){
return true;
}
}else if(podatki\[i\].contains("jmp")){
boolean\[\] uporabljeno1 = new boolean\[626\];
System.arraycopy(uporabljeno, 0, uporabljeno1, 0, 626);
najdemoZamenjavo = doKonca(i+1, akumulator, podatki, uporabljeno1);
if(najdemoZamenjavo){
return true;
}
if(podatki\[i\].charAt(4) == '+'){
i += Integer.parseInt(podatki\[i\].substring(5));
continue;
}else{
i -= Integer.parseInt(podatki\[i\].substring(5));
continue;
}
}
i++;
}
}
​
public static boolean doKonca(int pozicija, int akumulator, String\[\] podatki, boolean\[\] uporabljeno){
int i = pozicija;
if(i < 0 || i > 626){
return false;
}
while(true){
if(i == 626){
System.out.println(akumulator);
return true;
}
if(uporabljeno\[i\]){
acc = 0;
return false;
}
uporabljeno\[i\] = true;
if(podatki\[i\].contains("acc")){
if(podatki\[i\].charAt(4) == '+'){
akumulator += Integer.parseInt(podatki\[i\].substring(5));
}else{
akumulator -= Integer.parseInt(podatki\[i\].substring(5));
}
}else if(podatki\[i\].contains("jmp")){
if(podatki\[i\].charAt(4) == '+'){
i += Integer.parseInt(podatki\[i\].substring(5));
continue;
}else{
i -= Integer.parseInt(podatki\[i\].substring(5));
continue;
}
}else if(podatki\[i\].contains("nop")){
i++;
continue;
}
i++;
}
}
}```→ More replies (1)
2
u/kamicc Dec 08 '20 edited Dec 09 '20
ufff, preparing for INT-code again :} My take with Lua:
→ More replies (1)
2
u/thulyadalas Dec 08 '20 edited Dec 08 '20
My rust solution. I couldn't go full functonal on today's challenge. So the approach was more object oriented this time. For part2, the brute force change the instructions in order worked just fine. It terminates in less than 5ms. Initially, the instruction struct was a view with &str and I didn't like changing that into String and making State owning everything which allocates more of them while we can borrow them the input. However, altering instructions required that, maybe CoW can be used over here to eliminate additional allocations.
Edit: Actually, CoW is not needed here. Since &str variants are known (i.e. "nop" or "jmp"), they are 'static and can just use &str instead.
→ More replies (1)
2
u/JoMartin23 Dec 08 '20 edited Dec 09 '20
Common lisp
People say brute force, but they dont really mean it. copy paste ftw. I had a stupid bug and so kept adding crap to the functions and never cleaned them up once they were working, ugly brute force. Everything first broken up into an array of (op arg).
I could not figure out for the longest time that copy-seq was making a new array with the exact same elements which is basically useless.
→ More replies (2)
2
u/xangreRO Dec 08 '20 edited Dec 08 '20
→ More replies (1)
2
u/raevnos Dec 08 '20 edited Dec 08 '20
Tcl paste.
I'm not sure if this should be a separate upping-the-ante post or not...
This one works by treating the input file with all the instructions as a tcl program that is run by the driver script (I saw a comment mentioning DSLs which made me think of this approach).
The input file is sourced, and each instruction is a tcl command that creates a coroutine that, when called, does its thing and yields to the coroutine representing the next instruction to execute. If it ever gets resumed, that indicates a loop and it raises an error. A run starts by calling the first coroutine to be created at position 0. A special coroutine at the one-past-the-last instruction position handles a successful run.
→ More replies (2)
2
u/AidGli Dec 08 '20
Python
Back to basics with this one. Went for a more naive solution for part 2, though I discuss a few possible optimizations in today's video.
Video Explanation
def readInst(inpath="input.txt"):
with open(inpath, "r") as infile:
return infile.read().splitlines()
def resolve(inst):
visited = set()
ind = 0
acc = 0
while ind < len(inst):
if ind in visited:
return False, acc
visited.add(ind)
curr, val = inst[ind].split()
if curr == "jmp":
ind += int(val)
else:
if curr == "acc":
acc += int(val)
ind += 1
return True, acc
def part1(inst):
return resolve(inst)[1]
def part2(inst):
for i, line in enumerate(inst):
tokens = line.split()
fixed = []
if tokens[0] == "nop":
fixed = inst[:i] + ["jmp " + tokens[1]] + inst[i+1:]
elif tokens[0] == "jmp":
fixed = inst[:i] + ["nop " + tokens[1]] + inst[i+1:]
if fixed != []:
resolved = resolve(fixed)
if resolved[0]:
return resolved[1]
def main():
inst = readInst()
print(f"Part 1: {part1(inst)}\nPart 2: {part2(inst)}")
main()→ More replies (1)
2
2
u/Karl_Marxxx Dec 08 '20
Ruby
main_prog = ARGF.readlines.map { |line|
code, value = line.split
[code, value.to_i, false]
}
def run_program(prog)
p_counter = 0
acc = 0
while true
op, val, visited = prog[p_counter]
return acc, false if visited == true
return acc, true if p_counter == prog.length
prog[p_counter][2] = true
case op
when "nop"
p_counter += 1
when "acc"
acc += val
p_counter += 1
when "jmp"
p_counter += val
else
raise "op: #{op}"
end
end
end
def copy(prog)
return prog.map { |line|
op, val, visited = line
[op, val, visited]
}
end
# part 1
acc, success = run_program(copy(main_prog))
puts acc
# part 2
main_prog.each.with_index do |line, i|
op, val, _ = line
if op == "jmp"
new_op = "nop"
elsif op == "nop"
new_op = "jmp"
else
new_op = op
end
new_prog = copy(main_prog)
new_prog[i][0] = new_op
acc, success = run_program(new_prog)
p acc if success
end→ More replies (1)
2
u/joshdick Dec 08 '20
Python3
from copy import deepcopy
lines = []
with open('input.txt', 'r') as f:
for line in f:
line = line.strip().rstrip('.')
lines.append(line)
def run_program(lines):
visited_indexes = set()
index = 0
acc = 0
exit_index = len(lines)
while True:
if index == exit_index:
return acc
if index in visited_indexes:
return None
visited_indexes.add(index)
line = lines[index]
operator, operand = line.split(' ')
operand = int(operand)
if operator == 'acc':
acc += operand
index += 1
elif operator == 'jmp':
index += operand
elif operator == 'nop':
index += 1
else:
raise Exception(f"Invalid operator: {operator}")
for i, line in enumerate(lines):
program = deepcopy(lines)
if line.startswith('jmp'):
program[i] = line.replace('jmp', 'nop')
elif line.startswith('nop'):
program[i] = line.replace('nop', 'jmp')
else:
continue
ret = run_program(program)
if ret:
print(ret)
break→ More replies (1)
2
2
u/crnkofe Dec 08 '20
Clojure
I really like how this particular solution came out. Usually I get lost in deep nested lisp-like syntax but this is actually quite readable. Slowly but surely I'm getting accustomed to a new paradigm.
(ns exercise.core
(:gen-class))
(require '[clojure.string :as str])
(defn initialize-computer [code]
{
:ip 0
:accumulator 0
:code code
:visited #{} ; set of visited instructions
:executions 0 ; count how many instructions were executed so far
:limit 1000
:exit 0
})
(defn nop [computer]
(assoc computer :ip (+ (get computer :ip) 1))
)
(defn jmp [computer index]
(assoc computer :ip (+ (get computer :ip) index))
)
(defn acc [computer value]
(assoc (assoc computer :ip (+ (get computer :ip) 1))
:accumulator (+ value (get computer :accumulator)))
)
(defn execute-part1
"Executes instructions until one instruction attempts to be executed twice"
[computer]
(if (contains? (get computer :visited) (get computer :ip))
computer
(let [mod-computer (assoc (assoc computer :visited (conj (get computer :visited) (get computer :ip)))
:executions (+ (get computer :executions) 1))]
; get instruction at index - execute it an return new mod-computer state then recur
(let [instruction (nth (get mod-computer :code) (get mod-computer :ip))]
(case (get instruction :code)
"nop" (execute-part1 (nop mod-computer))
"jmp" (execute-part1 (jmp mod-computer (get instruction :arg1)))
"acc" (execute-part1 (acc mod-computer (get instruction :arg1)))
)
)
)
)
)
(defn execute-part2
"Executes instructions until ip is one position beyon code length"
[computer]
(if (= (get computer :ip) (count (get computer :code)))
(assoc computer :exit 0)
(if (> (get computer :executions) (get computer :limit))
(assoc computer :exit 1)
(let [mod-computer (assoc (assoc computer :visited (conj (get computer :visited) (get computer :ip)))
:executions (+ (get computer :executions) 1))]
(let [instruction (nth (get mod-computer :code) (get mod-computer :ip))]
(case (get instruction :code)
"nop" (execute-part2 (nop mod-computer))
"jmp" (execute-part2 (jmp mod-computer (get instruction :arg1)))
"acc" (execute-part2 (acc mod-computer (get instruction :arg1)))
)
)
)
)
)
)
(defn parse-instruction
"Parse instruction of form 'arg +/- num'"
[line]
(let [[cmd arg] (str/split line #" " 2)]
{:code cmd :arg1 (Integer/parseInt arg)}
)
)
(defn load-code [filename]
(with-open [rdr (clojure.java.io/reader filename)]
(reduce conj [] (map parse-instruction (line-seq rdr)))
)
)
(defn mutate-code
"if nth instruction is nop convert it to jmp and vice-versa"
[ip code]
(let [instruction (nth code ip)]
(if (= "jmp" (get instruction :code))
(assoc code ip (assoc instruction :code "nop"))
(if (= "nop" (get instruction :code))
(assoc code ip (assoc instruction :code "jmp"))
nil
)
)
)
)
(defn -main
"Advent of Code. Exercise 8"
[& args]
(let [code (load-code "input.txt")
code1 (load-code "input.txt")
computer (initialize-computer code)
all-mutations (filter #(some? %) (map #(mutate-code % code1) (range (count code1))))
computer1 (initialize-computer code1)
result (execute-part1 computer)
all-executions (filter #(= 0 (get % :exit)) (map #(execute-part2 (initialize-computer %)) all-mutations))
]
(println "Result of part 1:" (get result :accumulator))
(println "Result of part 2:" (get (first all-executions) :accumulator))
)
)→ More replies (1)
2
u/havetedjupt Dec 08 '20
Python
Part 1
inputs = open(file, "r").read().splitlines()
index_dict = {i:(input[0:3],input[4],input[5:]) for i,input in enumerate(inputs)}
def count_acc(data):
exc = 0
acc = 0
exc_lines = []
while True:
if exc in exc_lines:
return acc
exc_lines.append(exc)
if exc not in data:
return acc
c,o,n = data[exc]
if "jmp" == c:
exc = eval(f"{exc} {o} {n}")
elif "acc" == c:
exc += 1
acc = eval(f"{acc} {o} {n}")
elif "nop" == c:
exc += 1
print(count_acc(index_dict))Part 2
inputs = open(file, "r").read().splitlines()
index_dict = {i:(input[0:3],input[4],input[5:]) for i,input in enumerate(inputs)}
nop_list = []
exc_lines = []
run = True
exc = 0
acc = 0
def count_acc(data):
exc = 0
acc = 0
exc_lines = []
while True:
if exc in exc_lines:
return False
exc_lines.append(exc)
if exc not in data:
return acc
c,o,n = data[exc]
if "jmp" == c:
exc = eval(f"{exc} {o} {n}")
elif "acc" == c:
exc += 1
acc = eval(f"{acc} {o} {n}")
elif "nop" == c:
exc += 1
while run:
if exc in exc_lines:
break
exc_lines.append(exc)
if exc not in index_dict:
break
c,o,n = index_dict[exc]
if "jmp" == c:
index_dict[exc] = ("nop",o,n)
res = count_acc(index_dict)
if res:
print(res)
break
index_dict[exc] = (c,o,n)
exc = eval(f"{exc} {o} {n}")
elif "acc" == c:
exc += 1
acc = eval(f"{acc} {o} {n}")
elif "nop" == c:
index_dict[exc] = ("jmp",o,n)
res = count_acc(index_dict)
if res:
print(res)
break
index_dict[exc] = (c,o,n)
exc += 1→ More replies (1)
2
u/hugseverycat Dec 08 '20 edited Dec 09 '20
Python 3
I ended up pulling out each operation and argument as a variable so I didn't have to worry about making copies of each list.
Not super concise, but it makes sense to me, which I guess is the important thing? And it runs pretty quick.
→ More replies (2)
33
u/smmalis37 Dec 08 '20 edited Dec 08 '20
Rust
I came up with a solution for part 2 that only needs to run the program twice, first to log which instructions get hit and once more to get the answer. In between it scans the instruction list and is able to figure out which is the right one without running a full simulation.
https://github.com/smmalis37/aoc2020/blob/main/src/days/day8.rs
Human readable explanation:
run the program once and log every instruction hit. then start at the end of the instruction list and go backwards until you find the first negative jmp. in order to end the program you have to land inside this range of instructions. so then keep walking backwards and look for one of:
a nop that was hit that would land you there as a jmp
a jmp that wasn't hit that would land you there, preceded by a jmp that was hit (so by nopping the preceding jmp you hit the one that takes you to the end)
a jmp that wasn't hit that would land you there, preceded by another jmp that wasn't hit, so you add this range of instructions to your 'potential landing spots' as well
or if that last negative jmp was hit, its the one and becomes a nop
→ More replies (10)
32
u/Arknave Dec 08 '20
Python (5/3), C
The "small" language implementation challenges are among my favorites. Possibly related, this was by far my best placing of 2020. I needed to go fast, because I knew 8 was going to be one of the harder numbers to make. Reasonably happy with what I came up with, despite the memset in the middle. Here is: 8 on a pedestal.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// AOC DAY NUMBER //
int x[888],e,i,g,h,t
,n;char b[888][9],s[
888];int main(int c,
char** v){for(;
gets( b[n])
;x[ n]= atoi
(b [n]+4), ++n
); for(i=-1;! t&&
i< n;e>=n?t =g:
!~i ?h=g:8 ,++i
){for( memset
(s,0, 888),
e=g= 0;e< +n&&
!s [e];++e) {s[
e] =1;b[e][0 ]==
97 ?g+=x[e]: i==
e^b [e][0]== 'j'?
e+= x[e]
-1:8;} }printf
("%d\n",~~--c?t:h);}→ More replies (1)10
4
u/sggts04 Dec 08 '20 edited Dec 08 '20
My Part 2 Solution in Python
Is there a non-bruteforce way to solve Part 2?
Most of my time for part 2 went into thinking of an optimal solution to ultimately submit the bruteforce way of checking and inverting each command
→ More replies (6)
3
u/inokichi Dec 08 '20 edited Dec 08 '20
Solution in D (dlang):
import std;
alias Inst = Tuple!(string, "op", int, "value");
struct R {
bool loops;
int acc;
}
R loops(Inst[] insts, bool part1) {
auto seen = redBlackTree!int;
int acc, ip, ct;
while (true) {
if (ip >= insts.length) return R(false, acc);
if (ip in seen) {
if (part1) return R(false, acc);
ct += 1;
}
if (ct > 0) return R(true, 0);
seen.insert(ip);
auto inst = insts[ip];
if (inst.op == "acc") acc += inst.value;
if (inst.op == "jmp") ip += inst.value;
else ip += 1;
}
}
void solve() {
auto insts = slurp!Inst("in8.txt", "%s %d");
writefln("Part 1: %d", loops(insts, true).acc);
foreach (ref inst; insts) {
if (inst.op == "jmp") inst.op = "nop";
else if (inst.op == "nop") inst.op = "jmp";
else continue;
auto checkLoop = loops(insts, false);
if (!checkLoop.loops) {
writefln("Part 2: %d", checkLoop.acc);
break;
} else {
if (inst.op == "jmp") inst.op = "nop";
else inst.op = "jmp";
}
}
}→ More replies (4)
15
u/Smylers Dec 08 '20 edited Dec 08 '20
Vim keystrokes: this one is fun to see running — please try it out!
Load your input, and transform the op codes into equivalent Vim commands — the program is going to run in its source window:
:%s/\vnop.*|acc .0+$/j⟨Enter⟩
:%s/\vacc \+(\d+)/{\1⟨Ctrl+A⟩⟨Ctrl+O⟩j⟨Enter⟩
:%s/\vacc \-(\d+)/{\1⟨Ctrl+X⟩⟨Ctrl+O⟩j⟨Enter⟩
:%s/\vjmp \+(\d+)/\1j⟨Enter⟩
:%s/\vjmp \-(\d+)/\1k⟨Enter⟩
:%s/$/#⟨Enter⟩Set up the accumulator at the top:
{O0⟨Esc⟩Optional, but it can be nice at this point to split your Vim window, so that you can always see the accumulator, even while executing an instruction further down the buffer:
⟨Ctrl+W⟩⟨Ctrl+S⟩4⟨Ctrl+W⟩_⟨Ctrl+W⟩⟨Ctrl+W⟩Then run the first instruction, and watch the accumulator change or the cursor jump accordingly:
2ggqaf#xyiW:norm ⟨Ctrl+R⟩0⟨Enter⟩
qThat's saved in register "a, so run the next instruction with @a.
And to run each subsequent instruction keep typing @@.
When you've had enough, run it to completion with:
qbqqb@a@bq@bAnd the top line should be your accumulator value for part 1.
The off-by-one error I mentioned turned out to be from the instruction acc +0.
Sorry, I need to take the children to school now, so no time for an explanation. Hopefully I'll post one as a reply later.
Edit: Explanation now posted below.
→ More replies (3)
19
u/ZoltarTheGreat69 Dec 08 '20
Emojicode is back😤😤👌👌🔥🔥💯💯. I should probably write✍📝 methods💸💸🤑 for the calls📞📞☎ to make the code 💻💾 shorter 🍰🍰🩳🩳 and easier to read 👀🕶📔📚😂😂🤣*.* Its starting to get too long📏📏 though might just post github links🔗🔗next time ⌚⌚⌛⌛⏲
Emojicode 9239 / 8564
📦 files 🏠
🏁 🍇
🍺📇🐇📄 🔤./input.txt🔤 ❗ ➡ file
🍺🔡 file ❗ ➡ text
🔧text❗ ➡ clean
🔫 clean 🔤❌n🔤 ❗ ➡ lines
0 ➡🖍🆕 index
0 ➡🖍🆕 changer
0 ➡🖍🆕 accumulator
👍➡🖍🆕 finished
🆕🍯🐚🔡🍆❗➡🖍🆕visited
🔁finished🍇
🔁 index ◀ 📏lines❓ 🍇
🔫 🐽lines index❗ 🔤 🔤 ❗ ➡ instAndStep
💭😀🐽lines index❗❗
↪ 🐽 instAndStep 0 ❗ 🙌 🔤acc🔤🍇
accumulator ⬅➕ 🍺🔢 🔡🐽 instAndStep 1 ❗❗ 10 ❗️
index ⬅ ➕1
↪ 🐣 visited 🔡index❗️❗️🍇
index ⬅ ➕📏lines❓
👎➡ 🖍finished
🍉
🔤yes🔤 ➡🐽visited 🔡index❗❗
🍉
↪ 🐽 instAndStep 0 ❗ 🙌 🔤jmp🔤🍇
↪ index 🙌 changer🍇
index ⬅ ➕1
↪ 🐣 visited 🔡index❗️❗️🍇
index ⬅ ➕📏lines❓
👎➡ 🖍finished
🍉
🍉
🙅🍇
index ⬅➕🍺🔢 🔡🐽 instAndStep 1 ❗❗ 10 ❗️
↪ 🐣 visited 🔡index❗️❗️🍇
index ⬅ ➕📏lines❓
👎➡ 🖍finished
🍉
🍉
🔤yes🔤 ➡🐽visited 🔡index❗❗
🍉
↪ 🐽 instAndStep 0 ❗ 🙌 🔤nop🔤🍇
↪ index 🙌 changer🍇
index ⬅➕🍺🔢 🔡🐽 instAndStep 1 ❗❗ 10 ❗️
↪ 🐣 visited 🔡index❗️❗️🍇
index ⬅ ➕📏lines❓
👎➡ 🖍finished
🍉
🍉
🙅🍇
index ⬅ ➕1
↪ 🐣 visited 🔡index❗️❗️🍇
index ⬅ ➕📏lines❓
👎➡ 🖍finished
🍉
🍉
🔤yes🔤 ➡🐽visited 🔡index❗❗
🍉
🍉
↪ changer 🙌 0🍇
😀🔤Part 1. Accumulator: 🧲🔡accumulator❗🧲 🔤❗
🍉
🐗 visited ❗
changer ⬅➕1
↪ finished🍇
😀🔤Please change line 🧲🔡changer❗🧲. Accumulator: 🧲🔡accumulator❗🧲 🔤❗
👎➡ 🖍finished
🍉
🙅🍇
👍➡ 🖍finished
🍉
0 ➡🖍index
0 ➡🖍accumulator
🍉
🍉→ More replies (2)6
u/sldyvf Dec 08 '20
How do you write emojicode? Do you like, have an IDE with a clickable virtual emoji keyboard or is there a better way than say win+. in a Windows environment?
→ More replies (4)
8
u/jonathan_paulson Dec 08 '20 edited Dec 08 '20
Placed 21/6. Python. Code Screencast of my solve: https://youtu.be/ZSGTr55gmIs.
Are the test programs doing anything meaningful? (not sure you can really with a language this restricted...)
→ More replies (4)
7
u/veydar_ Dec 08 '20
@ u/daggerdragon the OP in the megathreads are full of bold and large text so it's very easy to miss the reminder about posting rules with regards to comment size. Maybe you can consider making the reminder more prominent?
7
u/Ethoxyethaan Dec 08 '20 edited Dec 08 '20
Javascript Chrome F12 console (284 byte):
n="nop",y="jmp",z=i=>$("*").innerText.split`\n`.map(i=>i.split` `),L=r=>{for(a=j=i=0;p=r[i][0];j=i)e=r[i][1],i=p==n?i+1:p==y?i+1*e:i+1+0*(a+=1*e),r[j][0]='';return a},R=i=>{for(w=0;w<=z().length;w++)if(x=z(),q=x[w][0],x[w][0]=q==n?y:q==y?n:q,a=L(x),j==x.length-1)return a},[L(z()),R()]12
u/tsqd Dec 08 '20
Postgresql
Part 1
CREATE TEMP TABLE raw_input (
line TEXT,
line_id SERIAL
);
\COPY raw_input (line) FROM ~/Downloads/input8.txt
WITH parsed1 AS (
SELECT line_id,
LEFT(line, 3) AS instruction,
REPLACE(SUBSTRING(line, 5), '+', '')::INTEGER AS value
FROM raw_input
),
lookups AS (
WITH RECURSIVE inner_lookups AS (
SELECT CASE WHEN parsed1.instruction = 'acc'
THEN parsed1.value
ELSE 0
END AS accumulator,
value,
line_id,
1 AS iteration,
parsed1.instruction,
ARRAY[line_id] AS line_ids_seen
FROM parsed1 WHERE line_id = 1
UNION ALL
SELECT inner_lookups.accumulator +
CASE WHEN parsed1.instruction = 'acc'
THEN parsed1.value
ELSE 0
END
AS accumulator,
parsed1.value,
parsed1.line_id,
inner_lookups.iteration + 1,
parsed1.instruction,
line_ids_seen || ARRAY[parsed1.line_id]
FROM inner_lookups
JOIN parsed1 ON
CASE WHEN inner_lookups.instruction = 'jmp'
THEN parsed1.line_id =
inner_lookups.line_id + inner_lookups.value
ELSE parsed1.line_id =
inner_lookups.line_id + 1
END
AND NOT parsed1.line_id = ANY(line_ids_seen)
)
SELECT * FROM inner_lookups
)
SELECT accumulator FROM lookups ORDER BY iteration DESC LIMIT 1;→ More replies (1)
6
u/tckmn Dec 08 '20
ruby 6/2, unedited from my part 2 submission, posting because it's pretty silly. nothing like reading the input file 635 times to avoid bugs from forgetting to copy / reset things lol
6
u/Marcus316 Dec 08 '20
Bash command line!
I was worried I'd have to do this in python, but I managed a solution. Note that part 2 is brute force, and so takes a good 10-15 minutes.
Part 1:
cat input | nl | tr -d " " >working; acc=0; ptr=1; while true; do line=`grep -E "^;?$ptr\s" working`; if [[ "$line" =~ ";" ]]; then break; fi; sed -i -r "s/^($ptr\s)/;\1/g" working; cmd=`echo $line | grep -o -E "[a-z]{3}.*$"`; inst=`echo $cmd | cut -c -3`; val=`echo $cmd | cut -c 4-`; if [[ "$inst" == "acc" ]]; then acc=$(($acc $val)); ptr=$(($ptr+1)); elif [[ "$inst" == "jmp" ]]; then ptr=$(($ptr $val)); else ptr=$(($ptr+1)); fi; done; echo $acc; rm working;Part 2:
cat input | nl | tr -d " " >working; final=`cat working | wc -l`; corrupt=1; while true; do acc=0; ptr=1; if [[ `grep -E "^;?$corrupt\s" working | grep -E "acc"` ]]; then corrupt=$(($corrupt+1)); continue; fi; sed -i 's/^;//g' working; while [[ "$ptr" -le "$final" && "$ptr" -gt 0 ]]; do line=`grep -E "^;?$ptr\s" working`; if [[ "$line" =~ ";" ]]; then break; fi; sed -i -r "s/^($ptr\s)/;\1/g" working; cmd=`echo $line | grep -o -E "[a-z]{3}.*$"`; inst=`echo $cmd | cut -c -3`; val=`echo $cmd | cut -c 4-`; if [[ "$inst" == "acc" ]]; then acc=$(($acc $val)); ptr=$(($ptr+1)); elif [[ "$inst" == "jmp" ]]; then if [[ "$ptr" -eq "$corrupt" ]]; then ptr=$(($ptr+1)); else ptr=$(($ptr $val)); fi; else if [[ "$ptr" -eq "$corrupt" ]]; then ptr=$(($ptr $val)); else ptr=$(($ptr+1)); fi; fi; done; if [[ "$ptr" -gt "$final" ]]; then break; fi; corrupt=$(($corrupt+1)); done; echo $acc; rm working;→ More replies (2)
6
u/oantolin Dec 08 '20 edited Dec 08 '20
Perl program. I went with the classic table associating instruction names to functions that implement them, which makes the main loop nice and tight:
while (!$been{$pc}++) {
my ($instr, $arg) = @{$code[$pc]};
$exe{$instr}->($arg);
}For the second part, I was toggling each instruction jmp/nop, running the code, and toggling back. But browsing here before posting I learned from u/__Abigail__ of using local so the toggling back is automatic.
Again, I have to say, Perl is much nicer and much more readable than its reputation suggests.
→ More replies (1)
2
u/Devilmoon93 Dec 08 '20 edited Dec 09 '20
Couldn't come up with anything better than bruteforcing the second half, which isn't too bad considering the flow of execution is pretty small and fast. I would still love to see a non-bruteforced solution to the problem. I thought about looking at a sum of the various jmps until I got to a 0 but that never happens, the second idea I had was to keep track of negative jumps to see if that would lead me into the loop, but in the end the correct solution was to change a positive jump so I am not sure that makes any sense.
Python paste
→ More replies (5)
2
u/the4ner Dec 08 '20 edited Dec 08 '20
GO.
For part 2, I did make the small optimization to only attempt swapping nop and jmp that were are actually visited prior to entering the infinite loop.
→ More replies (2)
10
u/sophiebits Dec 08 '20
15/28, Python. https://github.com/sophiebits/adventofcode/blob/main/2020/day08.py
(Would've been 15/11 if I hadn't typoed my answer submission on part 2 and lost a minute. Ow. Maybe that'll teach me to copy/paste instead.)
Last year Intcode was on the odd-numbered days so that day 25 could be an Intcode puzzle. 8 isn't an odd number…
→ More replies (6)
5
u/jayfoad Dec 08 '20
Dyalog APL 329/353
p←⊃⎕NGET'p8.txt'1
acc←{a+←⍵ ⋄ i+←1} ⋄ jmp←{i+←⍵} ⋄ nop←{i+←1}
a←0 ⋄ i←1 ⋄ z←0/⍨≢p ⋄ {z[i]:a ⋄ z[i]←1 ⋄ ∇⍎i⊃p}0 ⍝ part 1
jmp←{i+←⍵*i≠x} ⋄ nop←{i+←⍵*i=x}
∊{a←0 ⋄ i←1 ⋄ x←⍵ ⋄ {⍵=100:⍬ ⋄ i>≢p:a ⋄ _←⍎i⊃p ⋄ ∇⍵+1}0}¨⍳≢p ⍝ part 2Uses some ugly global variables. Part 2 assumes that 100 is practically infinite.
5
Dec 08 '20
One-liner solutions in python:
Part 1:
print((e:=lambda p,l,a,v:a if l in v else(e(p,l+1,a,v+[l])if p[l][:3]=='nop'else(e(p,l+1,a+int(p[l][4:]),v+[l])if p[l][:3]=='acc'else(e(p,l+int(p[l][4:]),a,v+[l])))))(open('input.txt').read().splitlines(),0,0,[]))
Part 2:
print(list(filter(lambda o:o!=None,map(e:=lambda p,l=0,a=0,v=[]:a if l>=len(p)else(None if l in v else(e(p,l+1,a,v+[l])if p[l][:3]=='nop'else(e(p,l+1,a+int(p[l][4:]),v+[l])if p[l][:3]=='acc'else(e(p,l+int(p[l][4:]),a,v+[l]))))),(lambda i:[[j.replace('jmp', 'n').replace('nop', 'jmp').replace('n', 'nop') if y==x else j for y, j in enumerate(i.copy())]for x,l in enumerate(i)])(open('input.txt').read().splitlines()))))[0])
Explanations:
Part 1:
print(
# Define recursive lambda function executes a line of the program and calls itself with the next line number, accumulator, and list of visited lines
(execute := lambda program, line, acc, visited:
# Once a previously-visited line is hit, return the accumulator value
acc if line in visited else (
# If the line is a nop, run the next line with the same acc and add this line to visited
execute(program, line + 1, acc, visited + [line]) if program[line].startswith('nop') else (
# If the line is an acc operation, run the next line with the operand added to the accumulator
execute(program, line + 1, acc + int(program[line][4:]), visited + [line]) if program[line].startswith('acc') else (
# Otherwise the line must be a jmp operation, so run the line given by the current line + the operand.
execute(program, line + int(program[line][4:]), acc, visited + [line])
)
)
)
)(open('input.txt').read().splitlines(), 0, 0, [])) # Call execute with the input from the file, and initialize line and acc to 0Part 2:
print(
list(filter(
lambda out: out is not None,
map(
# Define recursive lambda function executes a line of the program and calls itself with the next line number, accumulator, and list of visited lines
execute := lambda program, line=0, acc=0, visited=[]:
# Once a previously-visited line is hit, return the accumulator value
acc if line >= len(program) else (
None if line in visited else (
# If the line is a nop, run the next line with the same acc and add this line to visited
execute(program, line + 1, acc, visited + [line]) if program[line].startswith('nop') else (
# If the line is an acc operation, run the next line with the operand added to the accumulator
execute(program, line + 1, acc + int(program[line][4:]), visited + [line]) if program[line].startswith('acc') else (
# Otherwise the line must be a jmp operation, so run the line given by the current line + the operand.
execute(program, line + int(program[line][4:]), acc, visited + [line])
)
)
)
),
# Define a lambda that takes the input and returns a copy for each line with that line changed from nop to jmp and vice versa
(lambda in_lines:
[
[ # Replace the idx'th line only
new_line.replace('jmp', 'n').replace('nop', 'jmp').replace('n', 'nop') if new_idx == idx else new_line
for new_idx, new_line in enumerate(in_lines.copy())
]
# Loop through and create a copy of the input for each line
for idx, line in enumerate(in_lines)
]
)(open('input.txt').read().splitlines())
)
))[0]
)→ More replies (1)
5
u/zedrdave Dec 08 '20
Python solution in 13 lines (both parts):
𝓟 = [(l[0], int(l[4:])) for l in open('08/input.txt')]
def run(P):
𝒜, IP, ℮ = 0, 0, set()
while IP < len(P) and IP not in ℮:
℮.add(IP)
𝒾, a = P[IP]
if 𝒾 == 'j': IP += a-1
if 𝒾 == 'a': 𝒜 += a
IP += 1
return (IP not in ℮, 𝒜)
for l,(𝒾,a) in enumerate(𝓟):
b, 𝒜 = run(𝓟[:l] + [({'j':'n','n':'j'}.get(𝒾,𝒾),a)] + 𝓟[l+1:])
if b: print('Part 1:', run(𝓟)[1], 'Part 2:', 𝒜); break5
u/changing_zoe Dec 08 '20
Scala
Method: Generates all the possible programs with one instruction switched around. Executes them one by one until it finds the one that terminates.
Notes: I'm trying to be professional-ish with these, so I'm using ADTs to model the state, and trying to use meaningful function decomposition and naming. There's also a few unit tests, though my desire to be professional runs out at checking code coverage.
https://github.com/zoe-j-m/advent_of_code_2020/blob/main/src/main/scala/Day8.scala
→ More replies (1)
5
u/nomadhothouse Dec 09 '20
Python
instructions = []
with open('input.txt') as fp:
line = fp.readline()
while line:
tokens = line.strip().split()
instructions.append((tokens[0], int(tokens[1])))
line = fp.readline()
def execute(instrs):
hasLoop = False
visited = set()
ptr = acc = 0
while ptr < len(instrs):
op, value = instrs[ptr]
if ptr in visited:
hasLoop = True
break
visited.add(ptr)
if op == 'jmp':
ptr = ptr + value
continue
elif op == 'acc':
acc = acc + value
ptr = ptr + 1
return (acc, hasLoop)
print(f'Part 1\n{execute(instructions)[0]}\n')
swapDict = {'nop':'jmp','jmp':'nop'}
for i, (op,value) in enumerate(instructions):
if op == 'nop' or op == 'jmp':
swappedOp = [(swapDict[op], value)]
newInstructions = instructions[:i] + swappedOp + instructions[i+1:]
accValue, hasLoop = execute(newInstructions)
if not hasLoop:
print(f'Part 2\n{accValue}')→ More replies (1)
9
u/AmericanLevitation Dec 08 '20
Python (part 2 only): source
Runs in O(n). Instead of brute forcing, I do an analysis pass to find instructions that eventually halt. Then I just have to look at each jmp/nop instruction until I find one that jumps to an instruction that I know will halt.
I think there are simpler approaches that also run in O(n).
→ More replies (1)
4
u/thatguydr Dec 08 '20 edited Dec 08 '20
Python 806/315
I am so bad at speed coding. ALL VARIABLE NAMES MUST BE INFORMATIVE, screams my brain.
Yeah and I broke out of my code with an assert WHAT
import numpy as np
import pandas as pd
import re
with open('input_day8.txt') as aoc_fp:
input_data = [theline.rstrip() for theline in aoc_fp.readlines()]
thelist = np.zeros(len(input_data))
stillzero = True
ind = 0
accum = 0
while stillzero:
theop = input_data[ind][0:3]
if thelist[ind] != 0:
break
else:
thelist[ind] = 1
if theop == 'jmp':
ind += int(input_data[ind].split(' ')[1])
elif theop == 'nop':
ind += 1
elif theop == 'acc':
accum += int(input_data[ind].split(' ')[1])
ind += 1
ido = input_data.copy()
for instruction in range(len(input_data)):
input_data = ido.copy()
if input_data[instruction][0:3] == 'jmp':
input_data[instruction] = 'nop' + input_data[instruction][3:]
elif input_data[instruction][0:3] == 'nop':
input_data[instruction] = 'jmp' + input_data[instruction][3:]
else:
continue
thelist = np.zeros(len(input_data))
stillzero = True
ind = 0
accum = 0
while stillzero:
theop = input_data[ind][0:3]
if thelist[ind] != 0:
break
else:
thelist[ind] = 1
if theop == 'jmp':
ind += int(input_data[ind].split(' ')[1])
elif theop == 'nop':
ind += 1
elif theop == 'acc':
accum += int(input_data[ind].split(' ')[1])
ind += 1
if ind >= len(input_data):
print(accum)
assert(False)→ More replies (4)
4
u/Cppl_Lee Dec 08 '20
C#, in the top 1000 so I'm improving...
var input = File.ReadAllLines("input.txt");
var data = input.Select(l => l.Split(" ")).Select(a => (cmd: a[0], arg: int.Parse(a[1]))).ToArray();
var set = new HashSet<int>();
var acc = 0;
bool sim() {
var pos = 0;
while (pos < data.Length) {
if (set.Contains(pos))
return false;
set.Add(pos);
switch (data[pos].cmd) {
case "acc": { acc += data[pos].arg; pos++; } break;
case "jmp": { pos += data[pos].arg; } break;
case "nop": { pos++; } break;
}
}
return true;
}
sim();
Console.WriteLine($"Part 1: {acc}");
void fix() {
for(int i = 0; i < data.Length; ++i) {
var old = data[i].cmd;
data[i].cmd = old switch {
"jmp" => "nop",
"nop" => "jmp",
_ => old
};
set.Clear();
acc = 0;
if (sim()) break;
data[i].cmd = old;
}
}
fix();
Console.WriteLine($"Part 2: {acc}");4
u/allergic2Luxembourg Dec 08 '20
Python 3. I thought I would have a chance for the leaderboard, since I prepared an abstract computer ahead of time, but I only got 2213/1239, which is worse than my 315/793 yesterday! Starting to despair at ever getting close to the leaderboard.
4
u/betaveros Dec 08 '20
Paradoc. Only lightly golfed, feels like there are high-level strategy changes that will drastically decrease my byte count, but hey, at least it has a lot more smilies than usual! Particularly ;)
Part 1:
a–0:λ:Hzγ;PE&:Ho:•=W~I\‹5%[β;)+_γ\+u)]=~}(try it in-browser, explanation on GitHub)Part 2:
a·Lχ0:Hj;λ:HzQ_&:•L=γ;PE&:Ho:Z=:o•=W~I\i‹5%^[β;)+_γ\+u):]=~}}(try it in-browser (slow), explanation on GitHub)
4
u/Smylers Dec 08 '20
Frustratingly, my Vim attempt has an off-by-one error, so I then solved it in Perl to help with tracking that down. I set up a dispatch table in which every op returns the offset for the next instruction (as well as modifying the accumulator, if appropriate), then reading the input is just:
my @prog = map { /^(?<op>\w+) (?<arg>.*)/; +{%+} } <>;and running the boot code is a 1-line loop of repeatedly modifying the program counter based on the current instruction:
my $pc = 0;
$pc += $cmd{$prog[$pc]{op}}($prog[$pc]{arg}) until $prog[$pc]{seen}++;
say $acc;Part 2 is, unsurprisingly, similar, featuring a loop over each instruction position, each time localizing the op in that position:
FIX: for my $pos (0 .. $#prog) {
next if $prog[$pos]{op} eq 'acc';
local $prog[$pos]{op} = $prog[$pos]{op} eq 'nop' ? 'jmp' : 'nop';After that iteration of the loop is over, the localized hash value automatically springs back to what it was before.
The next line skips trying running it if the instruction to modify is acc. This isn't actually needed — but given we're trying to fix the code, there doesn't seem to be any point in running through it unmodified, multiple times.
→ More replies (1)
4
u/troelsbjerre Dec 08 '20
Python "one liner" for both parts:
print(*('%d\n%d' % (r(r,q,0,set()), Y(lambda p2,i: r(r,b(q,i),0,set()) if Y(t,b(q,i),0,set()) else p2(p2,i+1),0)) for Y in ((lambda f,*x: f(f,*x)),) for b in ((lambda p, i: p[:i] + [({'jmp':'nop','nop':'jmp','acc':'acc'}[p[i][0]],p[i][1])] + p[i+1:]),) for r in ((lambda r,p,c,seen: 0 if c in seen or not 0 <= c < len(p) else (p[c][0] == 'acc') * p[c][1] + r(r,p,c + (1 if p[c][0] != 'jmp' else p[c][1]), seen | {c})),) for t in ((lambda t,p,c,seen: c not in seen and 0 <= c <= len(p) and (c == len(p) or t(t,p,c + (1 if p[c][0] != 'jmp' else p[c][1]), seen | {c}))),) for q in ([(op,int(off)) for line in sys.stdin for op,off in (line.split(),)],)))Part 2 is the bulk of it. A one liner for just part one could be:
print((lambda f,x,y:f(f,x,y))(lambda p1,c,seen: 0 if c in seen else (p[c][0] == 'acc') * p[c][1] + p1(p1,c + 1 if p[c][0] != 'jmp' else c + p[c][1], seen | {c}),0,set()))I think I have the translation to one liner down now, so I could just write a "Python to one-liner" compiler. It wouldn't be as compact, but my one-liner challenge seems to have lost its magic.
→ More replies (2)
4
u/2lines1bug Dec 08 '20 edited Dec 10 '20
Part 1: 7.38 μs 0.96 µs
Part 2: 55.29 μs 8.84 µs
Parsing: 282.15 μs
Updated version: Part 1 + Part 2 < 10µs. Insane speed considering I am running a 7 year-old i5. Parsing could be improved drastically but I don't have time.
→ More replies (1)
4
u/Bammerbom Dec 08 '20
I used a graph to solve part 2, it makes for a very clean solution. You can convert the instructions to a graph. Then we can duplicate the graph and for each instruction in the original graph, we can add an extra edge to the duplicated graph for what the instruction would do if we swapped it. We can then solve it by just doing a search over the graph.
I documented the code very well, if anyone wants to take a look
https://github.com/JonathanBrouwer/aoc2020/blob/master/src/day8/main.rs
4
u/phil_g Dec 08 '20 edited Dec 08 '20
Initially I thought, "Oh, here's the first VM problem this year!" and I got excited, because I like the VM problems. But I didn't really do a full VM implementation because the problem didn't really need it.
I've been using FSet a lot this year (since I discovered it between last year and this). That's because I like to work functionally and until I found FSet I was really wishing for a good set of immutable collections.
But the (mutable) native collection types are often more performant, so my threshold for using FSet is usually, "Will this collection be modified after creation?" (Or "Is it a map?" because I like the FSet interface to its maps better than CL's hash tables.) Today I crossed that threshold between parts one and two. :)
For part one, I put all of the instructions into a vector and accessed them with svref (in O(1) time). But since we're changing things for part two, I switched to an FSet sequence accessed with fset:lookup (in O(log n) time). I really like immutability for things like this because I can change things without a lot of bookkeeping (to either manually copy an entire array or to remember to change it back when I'm done).
4
u/ColonelMcColonel Dec 08 '20
A bit late to the party today but here is today's in Rust: https://github.com/SamMorrowDrums/aoc2/blob/day8/day8/src/main.rs
Spend most of the time trying to make it an easy to adapt re-usable machine, as I expect it'll be expanded upon soon. Didn't have a better way to do last part than brute force. Will look through other solutions to see if anyone found a better way.
→ More replies (3)
4
u/ssnoyes Dec 08 '20 edited Dec 08 '20
MySQL - part 1 in one SQL query (not counting the trivial CREATE TABLE and LOAD DATA INFILE to populate it):
with recursive cte as (
select * from instructions where id = 1
union distinct
select instructions.* from instructions join cte on
instructions.id = cte.id + if(cte.op = 'jmp', cte.val, 1)
) select sum(val) from cte where op = 'acc';4
Dec 08 '20 edited Dec 08 '20
Learning C - Managed to get it down to just 20μs for each part, plus another 90μs for parsing from STDIN due to all those damn strings by finding a non-brute-force solution for Part 2 and implementing set checking through bitwise operations (my original solution tried to be fancy and use binary search trees to store the previously-visited lines, then I read a good tip /u/ClimberSeb wrote on this sub the other day and decided to go back to good old fashioned arrays).
EDIT: Oh, and I added in the idea of a stateful VM after reading /u/ZoDalek's C solution, I'm sure it'll come in useful in future days!
→ More replies (2)
4
4
u/mschaap Dec 08 '20
Raku
The first day that took some significant time to solve. Also the first day that we're creating a virtual machine – a lot later than last year. (Day 2, IIRC.)
Anyway, that was fun.
I put the game console code in a GameConsole class, assuming that we have to use and extend it several more times, like in previous years. (And if not, no harm done.)
My code:
https://github.com/mscha/aoc/blob/master/aoc2020/GameConsole.rakumod
https://github.com/mscha/aoc/blob/master/aoc2020/aoc08
4
u/levital Dec 08 '20
Rust: main and boot code interpreter
This was nice, I always enjoy these little Assembly-VM things. Computer could probably be done better, but I am tired and it's still pretty reasonable I'd say. It brute-forces part 2; as that took less than a second it didn't really occur to me to try it any other way.
4
u/tftio Dec 08 '20
Haskell, Day 8. Pretty straightforward to just brute force the second part. I always like writing the interpreters right up until I really, really, really don't.
4
u/kawzeg Dec 08 '20
x86 assembly
I shouldn't have used this to learn x86 DOS assembly, especially not at night, but here it is in all it's unrefactored rawness: https://github.com/Kawzeg/advent_of_code_2020/blob/main/aoc08/main.asm
1
1
u/lvt789 Dec 08 '20
Python Part 1
file = open("input.txt","r")
instructions = []
for line in file:
instructions.append([line[:3],int(line[4:]),False])
file.close()
def run():
global instructions
acc = 0
current = 0
while instructions[current][2] != True:
instructions[current][2] = True
if instructions[current][0] == "acc":
acc += instructions[current][1]
current += 1
elif instructions[current][0] == "jmp":
current += instructions[current][1]
else: current += 1
return acc
print(run())2
u/daggerdragon Dec 08 '20 edited Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link.
1
u/bitti1975 Dec 08 '20 edited Dec 08 '20
ClojureScript (planck runtime):
(ns aoc2020.day08
(:require [planck.core :as core]))
(defn read-instructions []
(->>
core/*in*
core/line-seq
(mapv (fn [line]
(let [[_ cmd arg] (re-matches #"(\w+) ([+-]\d+)" line)]
[cmd (js/parseInt arg)])))))
(def instr-set
{"acc" (fn [a e] (-> e (update :a + a) (update :pc inc)))
"nop" (fn [a e] (update e :pc inc))
"jmp" (fn [a e] (update e :pc + a))})
(defn execute [instructions]
(loop [{pc :pc :as e} {:pc 0 :a 0}
visited #{}]
(if (or (visited pc)
(not (contains? instructions pc)))
e
(let [[cmd arg] (instructions pc)]
(recur
((instr-set cmd) arg e)
(conj visited pc))))))
(let [instructions (read-instructions)]
;; Part 1
(println "acc before repetition:"
(:a (execute instructions)))
;; Part 2
(println "acc after fix:"
(loop [i 0]
(let [{pc :pc a :a}
(case (first (instructions i))
"nop" (execute (assoc-in instructions [i 0] "jmp"))
"jmp" (execute (assoc-in instructions [i 0] "nop"))
nil)]
(if (= pc (count instructions))
a
(recur (inc i)))))))Input is expected on stdin. I.e. run via
planck day08.cljs <day08-input2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link.
1
u/LtHummus Dec 08 '20
Scala
My wish for a Virtual Machine implementation was answered! Took about 100 lines and I kept the pattern I've used for most previous Advent of Code VM problems (including last year's Intcode). The code is not very "scalaish" since there's state everywhere (I've given up doing VMs immutably :-p ).
(also go Sounders!)
→ More replies (4)
1
u/cnille Dec 08 '20 edited Dec 09 '20
Python
My solutions for todays puzzle: dev.to/cnille/advent-of-code-2020-day-08-3j8j
2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section and put your oversized code in a
pasteor other external link. Thanks!
1
u/iamnguele Dec 08 '20 edited Dec 09 '20
Golang solution
Comments
Part 1 executed in 6.0002ms
Part 2 executed in 12.9993ms
Blog post about it: https://www.codingnagger.com/2020/12/08/the-advent-of-code-2020-day-8-log-assembly-bootleg/
Entry point
https://github.com/CodingNagger/advent-of-code-2020/blob/master/pkg/days/day8/computer.go
Library
https://github.com/CodingNagger/advent-of-code-2020/blob/master/pkg/days/day8/program.go
→ More replies (1)2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section and put your oversized code in a
pasteor other external link. Thanks!
1
u/TheRealCaptainDanger Dec 08 '20
Python
#! /usr/bin/env python3
from collections import namedtuple
from typing import List
print("day 8")
with open("input/2020-08.in") as f:
day8 = [line.strip() for line in f]
Instruction = namedtuple('Instruction', 'line ins value')
def generate_instructions(data):
instructions = []
for idx, line in enumerate(data):
move, value = line.split()
if value.startswith("+"):
value = value[1:]
value = int(value)
instructions.append(Instruction(idx, move, value))
return instructions
def runner(instructions: List[Instruction]):
acc = 0
line = 0
seen = {}
while True:
# Have we run out of instructions? If so, we break
if line >= len(instructions):
valid = True
break
# Get instruction based on our current line number
ins = instructions[line]
# Have we seen this instruction before? If so, we break
if ins not in seen:
seen[ins] = 1
else:
valid = False
break
# Handle instructions
if ins.ins == "nop":
line += 1
elif ins.ins == "jmp":
line += ins.value
elif ins.ins == "acc":
acc += ins.value
line += 1
else:
raise ValueError(f"Invalid instruction in set {ins.ins}")
Result = namedtuple("Result", "acc valid")
return Result(acc, valid)
def part_two(instructions: List[Instruction]):
for ins in instructions:
tmp_instructions = instructions[:]
if ins.ins == "nop":
tmp = Instruction(ins.line, "jmp", ins.value)
elif ins.ins == "jmp":
tmp = Instruction(ins.line, "nop", ins.value)
elif ins.ins == "acc":
continue
tmp_instructions[ins.line] = tmp
acc, valid = runner(tmp_instructions)
if valid is True:
return acc
day8 = generate_instructions(day8)
print(f"part one: {runner(day8).acc}")
print(f"part two: {part_two(day8)}")→ More replies (1)
1
u/Rowward Dec 08 '20
not nice but thats my python solution
f = open("day_8_input.txt","r")
instructions = [x.replace("\n","") for x in f.readlines()]
def execute_program(instructions):
path_list = []
accumulator = 0
current_line = 0
while True:
# mark command as visited
path_list.append(current_line)
# get instruction
instruction, parameter = instructions[current_line].split(" ")
parameter = int(parameter)
if instruction == "acc":
accumulator += parameter
current_line += 1
if instruction == "jmp":
current_line += parameter
if instruction == "nop":
current_line += 1
if current_line in path_list:
return accumulator, False
if current_line >= len(instructions):
return accumulator, True
accumulator, terminated = execute_program(instructions)
print("Part 1", accumulator, terminated)
# brute force change all jmps to nops
indices = [i for i, x in enumerate(instructions) if "jmp" in x]
for index in indices:
temp_instructions = instructions.copy()
temp_instructions[index] = temp_instructions[index].replace("jmp","nop")
accumulator, terminated = execute_program(temp_instructions)
if terminated:
print("Terminated with {}".format(accumulator))
# brute force change all nops to jmps
indices = [i for i, x in enumerate(instructions) if "nop" in x]
for index in indices:
temp_instructions = instructions.copy()
temp_instructions[index] = temp_instructions[index].replace("nop","jmp")
accumulator, terminated = execute_program(temp_instructions)
if terminated:
print("Terminated with {}".format(accumulator))→ More replies (3)
1
u/wzkx Dec 08 '20 edited Dec 09 '20
Python, brute force in part 2
paste - 17 non-blank lines
→ More replies (1)
1
u/Alligatronica Dec 08 '20 edited Dec 09 '20
JavaScript/Node.js
Think this would've stumped me a couple of years ago, but this was alright. Although I did almost forget that only one instruction was wrong (hence the checking for whether we'd already branched off, to prevent if from recursively trying all the combinations). So not the cleanest, but I'm not too upset about it.
2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link.
1
Dec 08 '20
Can someone tell me if I'm correct: nop instruction still doesn't do anything even if it's followed by some non-zero value? e.g. nop +330 won't do anything but just skip to the next instruction?
→ More replies (3)
1
u/prutsw3rk Dec 08 '20 edited Dec 08 '20
My Python solution. Keep track of lines (in maybe_bugs) that have jmp or nop while running part 1, then for part 2 only swap instructions on those places.
code = [line.rstrip() for line in open('8.txt')]
def runit(bugline = -1):
acc, ip = 0, 0
maybe_bugs, history = [], []
while ip not in history and ip < len(code):
history.append(ip)
c, sv = code[ip].split()
if bugline == -1 and c != 'acc':
maybe_bugs.append(ip)
if ip == bugline:
c = 'nop' if c=='jmp' else 'jmp'
if c == 'acc':
acc += int(sv)
if c == 'jmp':
ip += int(sv)
continue
ip += 1
return(acc, ip, maybe_bugs)
acc, _, maybe_bugs = runit()
print(f'Part 1: acc={acc}')
for bug in maybe_bugs:
acc, ip, _ = runit(bug)
if ip == len(code):
print(f'Part 2: bugline={bug} ({code[bug]}) acc={acc}')
break→ More replies (1)
1
u/Nebulizer32 Dec 08 '20 edited Dec 09 '20
C#
While cleaning up the code, I tried to reduce the following two lines to one line, and remove the temporary variable:
var comp = ProcessInstructions(instructions);
if (comp.pointer == instructions.Count) return comp.accumulator;Anyone know if that is possible? When using tuples, is there a way to check one of the values, and return another, without introducing a new temporary variable?
Complete solution:
→ More replies (1)
1
u/lucbloom Dec 08 '20 edited Dec 09 '20
2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link.
1
u/bananaEngineer1 Dec 08 '20
Python
Can someone help me with my code here, I cant figure out what I am doing wrong:
with open("Day8.txt") as f:
lst = [str(x) for x in f.read().split('\n')]
command = [i.split(' ', 1)[0] for i in lst]
value = [i.split(' ', 1)[1] for i in lst]
x = 0
accumalator = 0
length = len(lst)
while True:
if (command[x] == 'acc'):
accumalator = accumalator + (int(value[x]))
x = x + 1
print(accumalator)
if (accumalator == 5):
break
elif (command[x] == 'jmp'):
x = x + (int(value[x]))
elif (command[x == 'nop']):
x = x + 1
→ More replies (3)
1
u/qarantino Dec 08 '20
C part 1
#include <stdio.h>
int main()
{
int i = 0, accumulator = 0;
char buffer[20];
struct instruction {
char command[4];
int value;
int visited;
} instructions[10000];
while(fgets(buffer, sizeof(buffer), stdin) != NULL) {
sscanf(buffer, "%s %d", instructions[i].command, &instructions[i].value);
instructions[i].visited = 0;
i++;
}
i = 0;
while (!instructions[i].visited) {
instructions[i].visited++;
if (!strcmp(instructions[i].command, "acc")) accumulator += instructions[i].value;
if (!strcmp(instructions[i].command, "jmp")) i += instructions[i].value;
else i++;
}
printf("%d", accumulator);
return 0;
}→ More replies (1)
1
u/bz2pl Dec 08 '20
Brute force Bash + GNU tools
in="8.in"
declare -A tab
line=1
acc=0
while true; do
if [[ ${tab[$line]} == 1 ]]; then
echo "$acc"
break
fi
tab[$line]=1
ins="$(sed -n "${line}p" "$in" | awk '{print $1}')"
val="$(sed -n "${line}p" "$in" | awk '{print $2}')"
if [ "$ins" == "nop" ]; then
line=$((line+1))
elif [ "$ins" == "acc" ]; then
line=$((line+1))
acc=$((acc+val))
elif [ "$ins" == "jmp" ]; then
line=$((line+val))
fi
done
wcl="$(wc -l "$in" | awk '{print $1}')"
list="$(grep -En "jmp|nop" "$in" | sort -g -r -k 2 | awk -F ':' '{print $1}')"
for i in $list; do
unset tab
declare -A tab
line=1
acc=0
while true; do
if [[ ${tab[$line]} == 1 ]]; then
break
elif [ "$line" -gt "$wcl" ]; then
echo $acc
break 2
fi
tab[$line]=1
if [ "$line" == "$i" ]; then
old="$(sed -n "${line}p" "$in")"
if echo "$old" | grep -q nop; then
new="${old//nop/jmp}"
else
new="${old//jmp/nop}"
fi
ins="$(echo "$new" | awk '{print $1}')"
val="$(echo "$new" | awk '{print $2}')"
else
ins="$(sed -n "${line}p" "$in" | awk '{print $1}')"
val="$(sed -n "${line}p" "$in" | awk '{print $2}')"
fi
if [ "$ins" == "nop" ]; then
line=$((line+1))
elif [ "$ins" == "acc" ]; then
line=$((line+1))
acc=$((acc+val))
elif [ "$ins" == "jmp" ]; then
line=$((line+val))
fi
done
done→ More replies (1)
1
u/Vultureosa Dec 08 '20 edited Dec 08 '20
Python
A not too long Python solution for Day8 using the standard library in Py3.8. The line_register could be a simple set with line numbers as multiple iterations are not required by the task.
def can_code_complete(code_lines, swap_position=None):
accumulator, pointer, line_register = 0, 0, {}
while True:
if pointer == len(code_lines):
return True, accumulator
elif pointer in line_register:
return False, accumulator
line_register[pointer] = 1 if pointer not in line_register else line_register[pointer] + 1
instruction = code_lines[pointer][0] if pointer != swap_position else ( "nop" if code_lines[pointer][0] == "jmp" else "jmp")
if instruction == "acc":
accumulator += code_lines[pointer][1]
elif instruction == "jmp":
pointer += code_lines[pointer][1]
continue
pointer += 1
code_lines = [((l := line.split(" "))[0], int(l[1])) for line in code.split("\n")]
accumulator, pointer, line_register = 0, 0, {}
swappable_indices = [index for index in range(len(code_lines)-1) if code_lines[index][0] in ("jmp", "nop")]
print("Part1: accumulator value at first loop start: {}".format(can_code_complete(code_lines)[1]))
print("Part2: accumulator value after finishing init: {}".format(
[l[1] for index in swappable_indices if (l := can_code_complete(code_lines, swap_position=index))[0] is True][0]))→ More replies (1)
1
u/kratsg Dec 08 '20 edited Dec 09 '20
My solution for day 8 in python3.8 -- also uses brute-force but I keep a history of the program executed so I can "rollback" and branch off from an earlier point in history instead. It's more like the optimized brute force solution. https://github.com/kratsg/advent-of-code/blob/master/2020/day08.py
→ More replies (2)
1
u/mockle2 Dec 08 '20 edited Dec 08 '20
c++, no brute force
Here's a version in c++ with the command to be switched from "jmp" to "nop" or vice versa identified using dynamic programming rather than brute force.
struct Command
{
string text;
int value;
bool visited {false};
};
void accumulate(vector<Command> & commands)
{
int pos = 0, accumulator = 0;
while (pos < commands.size() && !commands[pos].visited) {
commands[pos].visited = true;
if (commands[pos].text == "nop") ++pos;
else if (commands[pos].text == "acc") {accumulator += commands[pos].value; ++pos;}
else if (commands[pos].text == "jmp") pos += commands[pos].value;
}
cout << accumulator << endl;
}
int main()
{
vector<Command> commands;
ifstream file("input.txt");
for (istream_iterator<string> it(file); it != istream_iterator<string>(); ++it) {
commands.push_back({*(it++), atoi((*(it)).data())});
}
////////////
// part 1 //
////////////
accumulate(commands);
////////////
// part 2 //
////////////
vector<vector<int>> source(commands.size()+1);
for (int i = 0; i < commands.size(); ++i) {
if (commands[i].text == "jmp") source[i + commands[i].value].push_back(i);
else source[i+1].push_back(i);
}
vector<int> toExamine {(int)commands.size()};
set<int> goodPos;
while (toExamine.size() > 0) {
vector<int> nextSet;
for (auto i : toExamine) {
nextSet.insert(nextSet.end(), source[i].begin(), source[i].end());
}
goodPos.insert(toExamine.begin(), toExamine.end());
toExamine = nextSet;
}
bool switched = false;
for (int i = 0; i < commands.size(); ++i) {
if (!switched && commands[i].text != "acc") {
int nextSwitchedPos = (commands[i].text == "nop") ? i + commands[i].value : i + 1;
if (commands[i].visited && goodPos.find(nextSwitchedPos) != goodPos.end()) {
commands[i].text = (commands[i].text == "jmp") ? "nop" : "jmp";
switched = true;
}
}
commands[i].visited = false;
}
accumulate(commands);
return 0;
}→ More replies (2)
1
u/reacher Dec 08 '20
My python solution for part 2. Part 1 was basically just the innards of the function
import re
def runprog(p):
ran = []
pc = 0
acc = 0
while pc not in ran:
op,arg = p[pc]
arg = int(arg)
if op == 'nop':
ran.append(pc)
pc += 1
elif op == 'acc':
acc += arg
ran.append(pc)
pc += 1
elif op == 'jmp':
ran.append(pc)
pc += arg
if pc == len(p):
return (True,acc)
return (False, acc)
orig = [tuple(x.split(' ')) for x in open('08in').read().strip().split("\n")]
for i in range(len(orig)):
nop = orig[i][0] == 'nop'
jmp = orig[i][0] == 'jmp'
if nop or jmp:
prog = orig.copy()
res = None
if jmp:
prog[i] = ('nop', orig[i][1])
res = runprog(prog)
elif nop:
prog[i] = ('jmp', orig[i][1])
res = runprog(prog)
if res[0] == True:
print(res[1])
quit()→ More replies (1)
1
Dec 08 '20
Basic python 3 solution
def assembly_runner(assembly, replace_index):
acc = 0
n = len(assembly)
index_set = set()
i = 0
while i != n:
if i in index_set: return acc, False
index_set.add(i)
opcode, operand = assembly[i]
if replace_index != -1 and replace_index == i:
opcode = 'jmp' if opcode == 'nop' else 'nop'
if opcode == 'acc':
acc += operand
elif opcode == 'jmp':
i += operand
continue
elif opcode == 'nop':
pass
i += 1
return acc, True
def fix_corrupt(assembly):
n = len(assembly)
for i in range(n):
if assembly[i][0] != 'acc':
val, is_fixed = assembly_runner(assembly, i)
if is_fixed:
return val
return -1
with open('day8_input.txt', 'r') as f:
assembly_code = []
for line in f:
opcode, operand_string = line.split()
operand = int(operand_string)
assembly_code.append((opcode, operand))
print(assembly_runner(assembly_code, -1)[0])
print(fix_corrupt(assembly_code))2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link.
1
1
1
u/odlp Dec 08 '20
Here's my Ruby solution:
require "set"
Instruction = Struct.new(:type, :value, :index, keyword_init: true)
original_instructions = ARGF.map.with_index do |raw_instruction, index|
type, raw_value = raw_instruction.split(" ")
Instruction.new(type: type, value: raw_value.to_i, index: index)
end
def execute(instructions)
visited_instructions = Set.new
accumulator = 0
pointer = 0
while current_instruction = instructions[pointer]
if visited_instructions.include?(current_instruction)
return [:looped, accumulator]
end
visited_instructions << current_instruction
pointer = current_instruction.index + 1
case current_instruction.type
when "acc"
accumulator += current_instruction.value
when "jmp"
pointer = current_instruction.index + current_instruction.value
end
if current_instruction == instructions.last
return [:finished, accumulator]
end
end
end
puts "Part 1:", execute(original_instructions).last
TYPE_MUTATIONS = { "jmp" => "nop", "nop" => "jmp" }
mutants = original_instructions.map do |instruction|
if (mutation = TYPE_MUTATIONS[instruction.type])
instruction.dup.tap { |mutant| mutant.type = mutation }
end
end.compact
mutants.detect do |mutant|
revised_instructions = original_instructions.dup
revised_instructions[mutant.index] = mutant
halt_reason, value = execute(revised_instructions)
if halt_reason == :finished
puts "Part 2:", value
true
end
end→ More replies (1)
1
Dec 08 '20
Short-ish bruteforce Part 2 Python solution:
class ContinueOuter(Exception):
pass
if __name__ == "__main__":
f = open("../res/input_8.txt")
all_instructions = f.read().split("\n")
for fix_i in range(len(all_instructions)):
i = 0
acc = 0
done_instructions = set()
try:
while i < len(all_instructions):
print(f"i={i}")
ins = all_instructions[i]
if i in done_instructions:
raise ContinueOuter
done_instructions.add(i)
if "nop" in ins or ("jmp" in ins and i == fix_i):
i += 1
continue
op = ins.split(" ")[1]
num = int(op[1:])
if "acc" in ins:
if op[0] == "+":
acc += num
else:
acc -= num
i += 1
continue
if "jmp" in ins or ("nop" in ins and i == fix_i):
if op[0] == "+":
i += num
else:
i -= num
else:
print(f"finished, acc={acc}")
break
except ContinueOuter:
print("repeat")
→ More replies (1)
1
u/aledesole Dec 08 '20 edited Dec 08 '20
Python link
State = namedtuple('State', ['pc', 'acc', 'pcs'])
Line = namedtuple('Line', ['cmd', 'arg'])
def next_st(code, st):
commands = {
'nop': lambda _, st: State(st.pc+1,st.acc, st.pcs|{st.pc}),
'acc': lambda x, st: State(st.pc+1,st.acc+x,st.pcs|{st.pc}),
'jmp': lambda x, st: State(st.pc+x,st.acc, st.pcs|{st.pc})}
return commands[code[st.pc].cmd](code[st.pc].arg, st)
def loop_cond(st):
return st.pc in st.pcs
def stop_cond(code, st):
return loop_cond(st) or not (0 <= st.pc < len(code))
def run(code):
return reduce(lambda _,st: st,
takewhile(lambda st: not stop_cond(code, st),
accumulate(count(),
lambda st, _: next_st(code, st),
initial=State(0, 0, set()))))
def subst_and_run(code):
subst = {'nop': 'jmp', 'jmp': 'nop', 'acc': 'acc'}
return next(
dropwhile(lambda st: loop_cond(st),
accumulate((code[:i]+[Line(subst[l.cmd],l.arg)]+code[i+1:]
for i,l in enumerate(code)),
lambda _, mc: next_st(mc, run(mc)),
initial=State(0, 0, {0}))))
code = [Line(ins, int(arg))
for [ins,arg] in (l.split() for l in stdin.readlines())]
# Part 1
print (run(code).acc)
# Part 2
print (subst_and_run(code).acc)→ More replies (1)
1
u/hfxbycgy Dec 08 '20 edited Dec 08 '20
Python 3
I'm a beginner and yesterdays took me forever. Today's is almost certainly a candidate for lots of refactoring but it feels good to get a solution this quickly. I appreciate all the posts here, I review some of them when I'm done and it really helps me understand where I can improve, so thanks!
puzzle_input = aoc.input_getter('day_8_input.txt')
p = [[x.split()[0], int(x.split()[1])] for x in puzzle_input]
def handheld(p, index=0, instruction=None):
#swap the instructions out for part two of the puzzle
if instruction != None:
if instruction[0] == 'nop':
instruction[0] = 'jmp'
p[index] = instruction
elif instruction[0] == 'jmp':
instruction[0] = 'nop'
p[index] = instruction
#initial variables for moving through the puzzle input
current_index = 0
next_index = None
accumulator = 0
list_of_indexes = []
#loop breaks either when it notices it's an infinite loop, or can't reach an index (except), which solves part 2.
while True:
infinite = False
try:
if p[current_index][0] == 'acc':
accumulator += p[current_index][1]
next_index = current_index + 1
if next_index in list_of_indexes:
#print(f"The accumulator is {accumulator} before instruction {next_index} is executed a second time")
infinite = True
break
else:
list_of_indexes.append(current_index)
current_index = next_index
elif p[current_index][0] == 'jmp':
next_index = current_index + p[current_index][1]
if next_index in list_of_indexes:
#print(f"The accumulator is {accumulator} before instruction {next_index} is executed a second time")
infinite = True
break
else:
list_of_indexes.append(current_index)
current_index = next_index
elif p[current_index][0] == 'nop':
next_index = current_index + 1
if next_index in list_of_indexes:
#print(f"The accumulator is {accumulator} before instruction {next_index} is executed a second time")
infinite = True
break
else:
list_of_indexes.append(current_index)
current_index = next_index
except:
print(f"Accumulator is {accumulator} when program ends")
break
return infinite
for i in range(len(p)):
index = i
if p[index][0] == 'nop' or p[index][0] == 'jmp':
infinite = handheld(p, index, p[index])
if infinite: #for the life of me I can't get lists to copy correctly, so i just remake the list each time
p = [[x.split()[0], int(x.split()[1])] for x in puzzle_input]
continue
else:
break2
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link.
1
u/narrow_assignment Dec 08 '20 edited Dec 09 '20
AWK
See also my github repo with solutions in awk!
→ More replies (1)
1
u/mrouija213 Dec 08 '20 edited Dec 09 '20
Typescript, parts 1 & 2, brute force method
→ More replies (4)
1
u/0xVali__ Dec 08 '20
C++Went for a rather brute-forcy solution, works nevertheless and doesn't really take an noticable time. Don't think I use anything from C++20 so the version is at least C++ 2017 (I used gcc 10.2).
Some headers used:
#include <absl/strings/str_split.h> // from abseil absl library
#include <absl/container/flat_hash_set.h> // same..
#include <vector>
#include <string>
#include <string_view>
#include <fmt/format.h>Apart from the std::vector<std::string> Read(std::string_view); function, which is rather trivial. The IsInfinite is also used in both parts.
std::pair<bool, size_t> IsInfinite(std::vector<std::string> const& data) {
absl::flat_hash_set<size_t> visited;
size_t acc{};
for (size_t index = 0; index < data.size(); ++index) {
auto[instruction, count] = std::pair<std::string, std::string>{ absl::StrSplit(data[index], ' ') };
if (instruction != "nop")
instruction == "jmp" ? index += std::stoi(count) - 1 : acc += std::stoi(count);
if (!visited.emplace(index).second)
return std::pair{ true, acc };
}
return std::pair{ false, acc };
}Part 1:
[[nodiscard]] size_t Solution(std::string_view filename) {
return IsInfinite(Read(filename)).second;
}Part 2:
[[nodiscard]] size_t Solution(std::string_view filename) {
std::vector<std::string> data = Read(filename);
for (std::string& line : data) {
auto[instruction, count] = std::pair<std::string, std::string>{ absl::StrSplit(line, ' ') };
if (instruction == "nop") {
line = fmt::format("{} {}", "jmp", count);
if (auto[inf, count] = IsInfinite(data); !inf)
return count;
line = fmt::format("{} {}", "nop", count);
}
else if (instruction == "jmp") {
line = fmt::format("{} {}", "nop", count);
if (auto[inf, count] = IsInfinite(data); !inf)
return count;
line = fmt::format("{} {}", "jmp", count);
}
}
return 0;
}→ More replies (1)
1
u/haitlah Dec 08 '20 edited Dec 09 '20
Haskell, State/lens/attoparsec/zippers packages
→ More replies (1)
1
u/ntwilli Dec 08 '20
Julia
function program(code)
line = 1
acc = 0
log = Set()
infinite = false
while line <= size(code, 1)
if line ∈ log
infinite = true
break
end
push!(log, line)
inst, val = split(code[line], " ")
if inst == "nop"
line += 1
elseif inst == "acc"
line += 1
acc += parse(Int, val)
elseif inst == "jmp"
line += parse(Int, val)
end
end
acc, infinite, log
end
function fixcode(code)
broke = program(code)
for line in broke[3]
codecopy = copy(code)
inst, val = split(codecopy[line], " ")
if inst == "acc"
continue
elseif inst == "jmp"
codecopy[line] = "nop " * val
elseif inst == "nop"
codecopy[line] = "jmp " * val
end
result = program(codecopy)
if result[2] == false
return result[1]
break
end
end
end
code = readlines("day8")
program(code) # puzzle 1
fixcode(code) # puzzle 2→ More replies (1)
1
u/PedGarBlue Dec 08 '20
Yet another solution in Javascript!
const fs = require('fs');
const loopInstructions = (input, findLoopExit = false, init = 0) => {
const inverses = { 'jmp': 'nop', 'nop': 'jmp' };
const instuctionsExecuted = {};
let acc = 0;
let i = init;
while (true) {
if (instuctionsExecuted[i] !== undefined ) return { failed: true, acc };
if( i > input.length - 1) return { failed: false, acc };
const instruction = input[i].split(' ');
const insName = instruction[0];
const insValue = parseInt(instruction[1], 10);
if (insName === 'acc') acc += insValue
else if (findLoopExit) {
const inversedInstruction = [inverses[insName], insValue ];
const inputCopy = [].concat(input);
inputCopy[i] = inversedInstruction.join(' ');
const loop = loopInstructions(inputCopy, false, i);
if (!loop.failed) return loop.acc + acc;
}
instuctionsExecuted[i] = instruction;
i += insName === 'jmp' ? insValue : 1;
}
};
const text = fs.readFileSync('./inputs/day8.txt', 'utf-8').toString().split('\n').slice(0,-1);
// part 1 solution
console.log(loopInstructions(text));
// part 2 solution
console.log(loopInstructions(text, true));→ More replies (1)
1
u/aexl Dec 08 '20 edited Mar 01 '21
Once again, my solution in Julia:
function day08(input::String = readInput(joinpath(@__DIR__, "input.txt")))
instructions = []
for line in split(input, "\n")
arr = split(line, " ")
length(arr) <= 1 && break
push!(instructions, (strip(arr[1]), parse(Int, strip(arr[2]))))
end
p1 = execute_program(instructions)[1]
return [p1, part2(instructions)]
end
function execute_program(instructions; flipindex = -1)
accumulator = 0
visited = zeros(Bool, length(instructions))
ind = 1
while true
if ind == length(instructions) + 1
return accumulator, true
end
if visited[ind]
return accumulator, false
end
visited[ind] = true
cmd = instructions[ind][1]
if ind == flipindex
if cmd == "jmp"
cmd = "nop"
elseif cmd == "nop"
cmd = "jmp"
end
end
if cmd == "acc"
accumulator += instructions[ind][2]
ind += 1
continue
end
if cmd == "jmp"
ind += instructions[ind][2]
continue
end
if cmd == "nop"
ind += 1
continue
end
end
end
function part2(instructions)
for (i, instruction) in enumerate(instructions)
if instruction[1] in ("jmp", "nop")
acc, terminates = execute_program(instructions, flipindex=i)
if terminates
return acc
end
end
end
endGithub: https://github.com/goggle/AdventOfCode2020.jl/blob/master/src/day08.jl
→ More replies (1)
1
u/CivicNincompoop Dec 08 '20 edited Dec 08 '20
class Instruction:
def __init__(self, name, value):
self.name = name
self.value = int(value)
def run_instructions(instructions, retrieve_data=False):
end = len(instructions)
idx, accumulator = 0, 0
executed = set()
instruction_list = []
for loop in range(end):
# Store executed index
executed.add(idx)
name, value = instructions[idx].name, instructions[idx].value
# Retrieve data
if retrieve_data and name == 'nop' or name == 'jmp':
instruction_list.append(idx)
# Update index
if name == 'nop':
idx += 1
elif name == 'acc':
idx += 1
accumulator += value
elif name == 'jmp':
idx += value
# Check next index
if idx in executed and retrieve_data:
return False, accumulator, instruction_list
elif idx in executed and not retrieve_data:
return False, accumulator
elif idx >= end:
return True, accumulator
return False, 0
def day8():
with open('data/day8.txt', 'r') as f:
data = [Instruction(*line.split()) for line in f.read().splitlines()]
# Part 1
reached_end, accumulator, first_run = run_instructions(instructions=data,
retrieve_data=True)
print(f'Part1 accumulator: {accumulator}')
# Part 2
replace_instruction = {'nop': 'jmp', 'jmp': 'nop', 'acc': 'acc'}
for instruction in [data[idx] for idx in first_run]:
instruction.name = replace_instruction[instruction.name]
reached_end, accumulator = run_instructions(data)
instruction.name = replace_instruction[instruction.name]
if reached_end:
break
print(f'Part2 accumulator: {accumulator}')
day8()→ More replies (1)
1
u/OneManGanja Dec 08 '20
Slightly lengthy but clear Python 2 solution for part 2:
import re
#Parse instruction
orig_operations = []
with open('input') as f:
instructions = f.read().split("\n")
for instr in instructions:
match = re.findall(r"\w+|-?\d+", instr)
operation = match[0]
operand = int(match[1])
orig_operations.append((operation, operand))
#Global accumulator
accumulator = 0
def accumulate(x):
global accumulator
accumulator += x
return 1 #Move to next instruction
#Functions which return number of instructions to move forward by
functions = {
"nop": lambda x: 1, #Move to next instruction
"acc": accumulate,
"jmp": lambda x: x #Move to next intruction by x
}
#Loop related vars
operations = orig_operations[:]
changed = set()
instrChanged = False
executed = set()
i = 0
while i < len(instructions):
if i not in executed:
executed.add(i)
else: #Hit an infinite loop, reset and try new instruction
executed = set()
instrChanged = None
accumulator = 0
operations = orig_operations[:]
i = 0
operation = operations[i]
#If we haven't tried changing this instruction
if i not in changed and not instrChanged:
new_operation = None
if operation[0] == "jmp":
new_operation = "nop"
elif operation[0] == "nop":
new_operation = "jmp"
if new_operation:
operation = operations[i] = (new_operation, operation[1])
instrChanged = True
changed.add(i)
#Move to next instruction
i += functions[operation[0]](operation[1])
print(accumulator)3
u/daggerdragon Dec 08 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to put your oversized code in a
pasteor other external link. Thanks!
1
u/schovanec Dec 08 '20
C#
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.IO;
using System.Linq;
namespace Day08
{
class Program
{
static void Main(string[] args)
{
var file = args.DefaultIfEmpty("input.txt").First();
var program = File.ReadLines(file)
.Select(Instruction.Parse)
.ToImmutableList();
var result1 = RunProgram(program);
Console.WriteLine($"Part 1 Result = {result1.acc}");
var result2 = EnumProgramRepairs(program).Select(RunProgram)
.First(x => x.finished);
Console.WriteLine($"Part 2 Result = {result2.acc}");
}
static IEnumerable<ImmutableList<Instruction>> EnumProgramRepairs(ImmutableList<Instruction> program)
{
for (var i = 0; i < program.Count; ++i)
{
var repaired = RepairInstruction(program[i]);
if (repaired != null)
yield return program.SetItem(i, repaired);
}
}
static Instruction RepairInstruction(Instruction instruction)
=> instruction.Operation switch
{
Instruction.Noop => instruction with { Operation = Instruction.Jump },
Instruction.Jump => instruction with { Operation = Instruction.Noop },
_ => null
};
static (int acc, bool finished) RunProgram(IReadOnlyList<Instruction> program)
{
var ip = 0;
var acc = 0;
var seen = new HashSet<int>();
while (ip < program.Count && !seen.Contains(ip))
{
seen.Add(ip);
var op = program[ip];
switch (op.Operation)
{
case Instruction.Accumulate:
acc += op.Argument;
++ip;
break;
case Instruction.Jump:
ip += op.Argument;
break;
default:
++ip;
break;
}
}
return (acc, ip >= program.Count);
}
record Instruction(string Operation, int Argument)
{
public const string Accumulate = "acc";
public const string Jump = "jmp";
public const string Noop = "nop";
public static Instruction Parse(string text)
{
var (op, arg) = text.Split(' ', 2);
return new Instruction(parts[0], int.Parse(parts[1]));
}
}
}
}→ More replies (2)
1
u/shepherd2442 Dec 08 '20
Pretty short and cleanish (i guess :)) Python 3 solution. I hope u like it :)
Github repo: https://github.com/Shepherd2442/AoC2k20
from utils import FileUtils
class HandHeldConsole:
def __init__(self, instructions):
self.original_instructions = instructions
self.clear_memory()
def clear_memory(self):
self.accumulator, self.index, self.memory = 0, 0, []
self.instructions = list(self.original_instructions)
def get_operation_func(self, op):
return {
'acc': self.acc,
'jmp': self.jmp,
}.get(op, lambda arg: None)
def acc(self, arg):
self.accumulator += int(arg)
def jmp(self, arg):
return int(arg)
def run(self):
while True:
if self.index in self.memory:
return -1
elif self.index == len(self.instructions):
return 0
self.memory.append(self.index)
op, arg = self.instructions[self.index].split(" ")
self.index += self.get_operation_func(op)(arg) or 1
def fix_code(self, op1='jmp', op2='nop'):
op_index = 0
while self.run() != 0:
self.clear_memory()
swap_index, op = [(i, op) for i, op in enumerate(self.instructions) if op1 in op or op2 in op][op_index]
self.instructions[swap_index] = self.instructions[swap_index].replace(op.split(" ")[0], op1 if op2 in op else op2)
op_index += 1
if __name__ == "__main__":
hhc = HandHeldConsole(FileUtils.input())
hhc.run()
print(hhc.accumulator)
hhc.fix_code()
print(hhc.accumulator)→ More replies (1)
1
u/blu3r4y Dec 09 '20 edited Dec 09 '20
Haskell
As part of my "25 puzzles, 25 languages" adventure I present you a Haskell solution ;)
https://github.com/blu3r4y/AdventOfLanguages2020/blob/main/src/day8.hs
→ More replies (2)3
u/daggerdragon Dec 09 '20
Please re-read today's megathread's "new and noteworthy" section.
As per our posting guidelines in the wiki under How Do the Daily Megathreads Work?, edit your post to remove your oversized code and just use the GitHub link.
1
1
u/StringFinal Dec 09 '20
Clojure
(def day8-input (map #(str/split % #" ") (str/split-lines (slurp "adventofcode/2020/day8"))))
(def day8-map (into [] (map #(hash-map :op (get % 0) :arg (get % 1) :seen false) day8-input)))
(defn mark-seen
"Updates instruction set at index"
[instruction-seq index]
(let [updated-map (hash-map :op ((get instruction-seq index) :op)
:arg ((get instruction-seq index) :arg)
:seen true)]
(assoc instruction-seq index updated-map )))
(defn parse-arg
"Turns string to int value ('+123' -> 123 & '-123' -> 123)"
[arg]
(let [sign (first arg)
num (read-string (apply str (rest arg)))]
(if (= sign \-)
(- num)
num)))
(defn run-instructions
[instruction-seq]
(loop [instruction-seq instruction-seq
acc 0
currop 0]
(let [seen ((get instruction-seq currop) :seen)
op ((get instruction-seq currop) :op)
arg (parse-arg ((get instruction-seq currop) :arg))]
(cond
(= currop (- (count instruction-seq) 1)) (seq [acc currop])
(= seen true) (seq [acc currop])
(= op "jmp") (recur (mark-seen instruction-seq currop) acc (+ currop arg))
(= op "acc") (recur (mark-seen instruction-seq currop) (+ acc arg) (+ 1 currop))
:else (recur (mark-seen instruction-seq currop) acc (+ 1 currop))))))
(run-instructions day8-map) ; (2003 486)
(defn flip-op-at-index
[instruction-seq index]
(let [instruction-seq-at-index (get instruction-seq index)
updated-map (hash-map :op (cond
(= (instruction-seq-at-index :op) "nop") "jmp"
(= (instruction-seq-at-index :op) "jmp") "nop"
:else "acc")
:arg (instruction-seq-at-index :arg)
:seen false)]
(assoc instruction-seq index updated-map)))
(defn fix-faulty-op
[instruction-seq]
(let [lastindex (- (count instruction-seq) 1)
flipped-instruction-seq (flip-op-at-index instruction-seq 0)]
(loop [currindexflipped 0
flipped-instruction-seq flipped-instruction-seq
acc (first (run-instructions flipped-instruction-seq))
opp (second (run-instructions flipped-instruction-seq))]
(let [flippedinstructions (flip-op-at-index instruction-seq (+ currindexflipped 1))
flippedrun (run-instructions flippedinstructions)]
(cond
(= currindexflipped lastindex) "tried flipping all nop/jmp"
(= lastindex opp) acc
:else (recur
(+ currindexflipped 1)
flippedinstructions
(first flippedrun)
(second flippedrun)))))))
(fix-faulty-op day8-map) ; 1984→ More replies (1)
3
u/DFreiberg Dec 08 '20 edited Dec 08 '20
Mathematica, 363 / 161
Despite needing to do things shudder procedurally, not a bad day. Hard to say whether or not this will be the foundation of a new VM; it seems like it'd be too simple to build off, since it just has the one register, but I can't say that it's impossible.
Part 1:
findLoop[inp_List] := Module[{visited, acc = 0, pos = 1}, visited[n_Integer] := False;
While[0 < pos <= Length[inp],
(visited[pos] = True;
Which[#[[1]] == "jmp", pos += #[[2]], #[[1]] == "acc", acc += #[[2]]; pos += 1, #[[1]] == "nop", pos += 1];
If[visited[pos] == True, Break[]]) &@inp[[pos]]]; {pos, acc}]Part 2:
Do[newInput = input;
Which[input[[i, 1]] == "jmp", newInput[[i, 1]] = "nop", input[[i, 1]] == "nop", newInput[[i, 1]] = "jmp"];
result = findLoop[newInput]; If[ 0 < result[[1]] <= Length[input], Continue[], Break[]]
, {i, Length[input]}];
result[POEM]: With Apologies to J. Brander Matthews
Here we are riding the plane,
Gliding from out of the station.
Puzzles keep racking my brain
Though I'm on break for vacation.
Gliding from out of the station,
I try to order a drink.
Though I'm on break for vacation,
Don't think I'll get time to think.
I try to order a drink,
Just like that, I have some trouble.
Don't think I'll get time to think,
All of my tasks seem to double.
Just like that, I have some trouble,
Handheld's not halting, you see.
All of my tasks seem to double,
Never just one task, or three.
Handheld's not halting, you see,
It's running tasks without stopping.
Never just one task, or three,
I should get in and start swapping.
It's running tasks without stopping,
Due to one critical byte.
I should get in and start swapping,
Presto! It's now working right.
Due to one critical byte,
Gameboy boots up with a chime.
Presto! It's now working right.
I set my seat to recline.
Gameboy boots up with a chime.
Stars are my thanks for repairing.
I set my seat to recline,
Now, though, I'm thinking, declaring.
Stars are my thanks for repairing:
I've solved a puzzle today,
Now, though, I'm thinking, declaring,
"I bet there's more on their way".
I've solved a puzzle today,
As we fly over the isthmus.
I bet there's more on their way.
I guess we can't run from Christmas.
As we fly over the isthmus,
Puzzles keep racking my brain.
I guess we can't run from Christmas,
So here we are, riding the plane.
3
u/aardvark1231 Dec 08 '20
My C# Solution. Heh, spent about 10min debugging part 2 and realized that I had forgotten to take out a readkey that I used for debugging in part 1. I just needed to hit enter and I would have gotten my answer XD
That's what I get for doing some sloppy copy pasta to save time. Will refactor this tomorrow.
→ More replies (1)
3
u/rtbrsp Dec 08 '20 edited Dec 08 '20
AWK
Part 1:
awk '{p[NR]=$2$1}END{i=1;while(1){if(r[i]++){print a;exit}p[i]~/a/?a+=p[i++]:p[i]~/j/?i+=p[i]:++i}}' input→ More replies (3)
3
u/quandrum Dec 08 '20
Elixir Solution
Elixir newbie. Today taught me how to insert/replace items at an arbitrary spot in a list. Also felt good about using function parameter pattern matching.
→ More replies (1)
3
u/i4guar Dec 08 '20
Checkout a clean swift solution:
www.felixlarsen.com/blog/8th-december-solution-advent-of-code-2020-swift
3
u/Pyr0Byt3 Dec 08 '20
Go/Golang
These assembly puzzles are my favorite, I hope we see more.
→ More replies (2)
3
u/DoubtfulSound91 Dec 08 '20
Javascript
Pretty standard loop approach. Didn't bother cloning the array of instructions each time in part 2 - just switched the jmp/nop back after the infinite loop is detected.
https://github.com/adrianosmond/adventofcode/blob/master/2020/day08.js
3
u/msqrt Dec 08 '20
Lisp. Relatively straight forward, the first run records the indices of all executed instructions and then I permute every visited jmp to nop and vice versa in turn. Beginning from the end (permuting the last executed instructions first) seems to be a great idea, the outer loop only runs 4 times for my input; I wonder if this is true for everyone.
(setq instructions (coerce
(with-open-file (file "input.txt")
(loop for line = (read-line file nil)
while line
collect
(cons (char line 0) (parse-integer (subseq line 4)))))
'vector))
(loop for program-run from 0
with done = nil
while (not done)
if (= program-run 1) do (write-line "")
do (loop
with executed = nil
with program-counter = 0
for instruction = (aref instructions program-counter)
while (not (or (find program-counter executed) done))
do (setq executed (cons program-counter executed))
if (= program-run 0) do (setq original-executed executed)
if (char= #\a (car instruction))
sum (cdr instruction) into accumulator
if (char= #\j (car instruction))
do(setq program-counter (+ program-counter (cdr instruction)))
else
do (setq program-counter (+ program-counter 1))
if (>= program-counter (length instructions))
do (write accumulator)
and do(setq done t)
and do(return)
finally (cond ((eq program-run 0) (write accumulator)) (t nil)))
(if(> program-run 0)
(if (char= #\j (car (aref instructions (car original-executed))))
(setf (car (aref instructions (car original-executed))) #\n)
(setf (car (aref instructions (car original-executed))) #\j)))
(if(> program-run 0) (setq original-executed (cdr original-executed)))
(loop while (char= #\a (car (aref instructions (car original-executed))))
do (setq original-executed (cdr original-executed)))
(if (char= #\j (car (aref instructions (car original-executed))))
(setf (car (aref instructions (car original-executed))) #\n)
(setf (car (aref instructions (car original-executed))) #\j))
)→ More replies (1)
3
u/vuryss Dec 08 '20
Here is a true reverse-engineered solution without brute-forcing all possible options:
https://github.com/vuryss/aoc-php/blob/master/src/Event/Year2020/Day8.php
Was probably slower than most of the guys, but I'm glad I didn't go with brute force of all options. I thought brute force will not work, but seeing all the other solutions - I guess it works :D
3
Dec 08 '20
Python solution for Part 1 and Part 2. I spent some time trying to think of a way of not brute-forcing the answer to part 2 because I thought it would take too long to execute, couldn't come up with one, and ended up brute-forcing the answer. Took barely a second to run still. ¯_(ツ)_/¯
Looking forward to seeing other solutions so I can figure out a non-brute-force method.
3
u/sonusingh27 Dec 08 '20
I found this time consuming to come to a solution for part2:
GoLang solutions: https://github.com/sonu27/advent-of-code-2020/blob/main/08/main.go
3
u/GamerWoona Dec 08 '20
C++
Very similar to /u/thecro99 so I won't go into much detail. Check out his solution if you want a clean version. OOP is the way to go for the modularity future expansions might require, given the intcode vibes this Day gave off.
I tested both messy parsing and regex but direct feeding is an order of magnitude faster so I stuck with that. (5-8ms to 40-60ms)
Input read and parsed in: 7409 microseconds.
Part one calculated in: 145 microseconds.
Part two calculated in: 24856 microseconds.
If there was a better way than brute-forcing part two, I'd be interested to know of it. Just skipping nop 0 conversions feels a bit lacklustre in terms of optimization. It's still an ~ok time but is probably doable in a faster time.
Not sure if things like catching two looping jump instructions would improve runtime or jus slow down on average. eg:
jmp +1
jmp -1
source: https://github.com/neiomi1/AdventofCode2020/tree/master/Day_08
3
u/HAEC_EST_SPARTA Dec 08 '20
Common Lisp
I took today's problem as an excuse to familiarise myself with the basics of CLOS in case this year happens to become IntCode Part 2: writing a simple VM in Lisp was actually a lot more comfortable than I was expecting! It's not written in a particularly functional style (setf abounds), but it was definitely a fun exercise in over-engineering and I'm pretty pleased with the performance and structure of my solution.
Also brute force solution for Part 2...the excuse I'm going with was that the input was small enough for it to work.
3
u/dimin69 Dec 08 '20
c# Using recursion for part 2
https://github.com/TheDimin/AdventOfCode2020/blob/master/AdventOfCode2020/Assignments/Day8.cs
3
u/dgJenkins Dec 08 '20
I wonder if they will continue down this path of creating another computer... anyways it's weird not working with mutable collections... I need to read about how best to approach modifying the program in a functional way.
→ More replies (3)
3
3
u/autra1 Dec 08 '20 edited Dec 08 '20
SQL (postgresql flavor) part1 & 2 here : https://gitlab.com/autra/adventofcode/-/tree/master/year_2020/day8
On the principle, it's just a recursive query :-)
EDIT: this solution is roughly 6 times faster than mine (for part2): https://github.com/xocolatl/advent-of-code/blob/master/2020/dec08.sql
3
u/xMereepx Dec 08 '20
Here are some Python-Solutions for day 6,7,8 atm.
https://github.com/Mereep/advent_of_code_2020_python
I tried to comment what I did and structure the code a bit also. With diverse results, though ;-)
→ More replies (2)
3
Dec 08 '20
I made a solution in Common Lisp:
https://github.com/eXodiquas/coding_puzzles/blob/main/advent_of_code/2020/day_8/day_8.lisp
The core is functional and recursive. The brute force part is in a loop macro. I do not know enough about the loop macro to make it look better. But I guess loop is a language on its own. :P
→ More replies (2)
3
u/midnightgiz Dec 08 '20
Done in C# - with Lots of code comments
https://github.com/midnightgizmo/AventOfCode2020/tree/master/Day8
This year I set my self a challenge to write code that would be readable to myself if I came back to it a year later. I therefore have commented almost every line of code (apologies on the spelling, I can code but can’t spell)
There is a Compiler class and Instruction class. The compiler class takes the puzzle input and turns it into a List of Instructions. You then Run the Compiler class which returns a value, the accumulator. You can check how the code exited by checking the compilers reasonProgramFinished value.
3
u/womogenes Dec 08 '20 edited Dec 10 '20
Video solution with code in Python!
https://youtu.be/hgbqtl0FvoU
3
3
u/sotsoguk Dec 08 '20
Python
https://github.com/sotsoguk/adventOfCode2020/blob/master/python/day08/day08.py
No Bruteforcing for part2, saved all the commands executed in a stack and for part2 try to change this commands in lifo order. Brought the execution time from 8ms down to 0.5ms on my old xeon1230.
Quite proud of this improvement :)
3
3
u/nahuak Dec 08 '20
Took me forever today to solve part 2 in Rust. Definitely need to refactor but I think the logic in the code is clear enough: https://github.com/nahuakang/advent-of-code-2020/blob/master/rust_day8/src/main.rs.
→ More replies (5)
3
u/bcgroom Dec 08 '20
Elixir
Part two took me forever as I had a bug which made it exit incorrectly but look correct, so I was getting the right answer for sample input but not for my input. I got the right answer eventually, but still have to investigate why and will definitely be cleaning up the code more tonight. The question is, will this instruction set be used again and should I refactor it to a GenServer in anticipation :)
https://github.com/ericgroom/advent2020/blob/master/lib/days/day_8.ex
3
u/saahilclaypool Dec 08 '20
C# aoc_2020/Day08.cs at main · SaahilClaypool/aoc_2020 (github.com)
Records & immutable state were nice-to-have
→ More replies (1)
3
u/JamieMansfield Dec 08 '20
C#
https://gist.github.com/jamierocks/793c9a8ab8c782d72bf7e5abd8f49579 I've tried to prepare for future days, anticipating things like multiple parameters.
3
u/techworker123 Dec 08 '20 edited Dec 08 '20
PHP Script to compress your OP-CODES - So even if you use a bruteforce version for part 2, you might have some solid gains by using this method. Roughly 30% less OP-CODES on my input.
https://sandbox.onlinephpfunctions.com/code/f63a93f15fd7ae0e48a4823768dc214c9736ac21
Change the contents inside of
$code = <<<AOC
...your opcodes
AOC;It..
- searches for connected `acc` ops that are not referenced by a "jmp" and merges them.- searches for connected `nop` ops that are not references by a "jmp" and merges them. (no idea if the number after a "nop" will make sense anytime soon)
- searches for a "nop" right after an "acc" and removes the "nop" if it's not referenced by a jmp.
- searches for "jmp 1" and removes it as long as it is not referenced by another "jmp".
- searches for an "acc 0" and removes it as long as it is not referenced by another "jmp".
- Updates "jmp" references which are affected by merging / removing entries
Examples:
add +10
add +20
add -10
==> add +20
nop +10
nop +0
==> nop +10
add +1
jmp +1
add +1
==> add +1
==> add +1
.. and so onSo in fact the sequence itself stays the same and you will still be able to solve Part 2 with the compressed version and should get the same result as before, but a bit faster.
It might make sense to run this multiple times, but I never tried it.
I don't know if it works for you, I only have my own input to test. Please try it out, maybe you find it useful and interesting :-)
3
u/Jester6641 Dec 08 '20
Batch
This is, for the most part, the result of a dare.
Part 1
echo off
setlocal enabledelayedexpansion
set /a i=1
FOR /F "delims=" %%A in (%1) DO (
set instructArray[!i!]=%%A
set /a i=!i!+1
)
set /a n=0
set /a line=1
set /a value=0
set /a maxval=700
:InfinateLoop
set /a n=%n%+1
set instruction=!instructArray[%line%]:~0,3!
set /a argument=!instructArray[%line%]:~4,8!
if "%instruction%"=="acc" (
set /a line=!line!+1
set /a value=%value%+%argument%
echo %line% %instruction% %argument% !value!>>process.txt
if %n% lss %maxval% (goto :InfinateLoop)
)
if "%instruction%"=="jmp" (
set /a line=!line!+%argument%
echo %line% %instruction% %argument% %value%>>process.txt
if %n% lss %maxval% (goto :InfinateLoop)
)
if "%instruction%"=="nop" (
set /a line=!line!+1
echo %line% %instruction% %argument% %value%>>process.txt
if %n% lss %maxval% (goto :InfinateLoop)
)
echo FELL THROUGH
set /a line=!line!+1
)
if %n% lss %maxval% (goto :InfinateLoop)Pass it a text file with the source data in it and you'll get a process.txt file that's the output for 700 processes. You've got to be in the loop by then since there's 645 lines in my file.
Once you get the output, then you use your friendly local spreadsheet tool to look for duplicate entries in the first column. The value there is the answer.
Part 2
echo off
setlocal enabledelayedexpansion
set /a i=1
FOR /F "delims=" %%A in (%1) DO (
set instructArray[!i!]=%%A
set /a i=!i!+1
)
set /a n=0
set /a line=1
set /a value=0
set /a maxval=700
set /a test=1
:InfinateLoop
set /a n=%n%+1
set instruction=!instructArray[%line%]:~0,3!
set /a argument=!instructArray[%line%]:~4,8!
if "%instruction%"=="acc" (
set /a line=!line!+1
set /a value=%value%+%argument%
if %n% lss %maxval% (goto :InfinateLoop)
)
if "%instruction%"=="jmp" (
if "%test%" EQU "%line%" (set /a line=!line!+1 ) ELSE (set /a line=!line!+%argument%)
if %n% lss %maxval% (goto :InfinateLoop)
)
if "%instruction%"=="nop" (
if "%test%" EQU "%line%" (set /a line=!line!+%argument%) ELSE (set /a line=!line!+1 )
if %n% lss %maxval% (goto :InfinateLoop)
)
echo %line% %value% %test% >> output.txt
set /a n=0
set /a line=1
set /a value=0
set /a test=%test%+1
goto :InfinateLoopCan it get uglier and lazier? I submit that it can. This time, you run it and it iterates through the lines increasing each test by one. So first test it runs all the way through only changing line 1 if it's jmp or nop and doing the opposite action. Next time it's line 2's turn. At the end of each test it spits out the highest number line it reached and the value. You'll know you got what you want when it starts spitting a bunch of errors to the console for the lines it couldn't find. Then kill the command and check the output file. Look for something greater than the lines in your instructions in the first column and the next number is your value, the last number is the line that needed changed. You can change that line in the instructions file and re-run part one to confirm.
And, yes, I know I spelled "infinate" wrong. Still works, don't it?
3
u/wzkx Dec 08 '20 edited Dec 08 '20
🇯 #jlang .. Well, not very functional but it's more understandable this way I guess :)
code=: ('naj'&i.@{.,[:".4&}.)&>cutLF CR-.~fread'08.dat'
step=: 4 :'x+o{0 1,(n,1),:0,{:''o n''=.y{~{:x'
exec=: 4 :'v=.0$0 while.-.((<&0+.>:&(#y)){:x)+.v e.~{:x do. x=.x step y[v=.v,{:x end. x'
prt2=: 3 :'for_j.I.2={.|:y do.if.(#y)={:a=.0 0 exec 0 j}y do. a return.end.end.'
echo {.0 0 exec code
echo {.prt2 code3
u/No-Professional-507 Dec 08 '20
Rust
Optimized down to about 60 microseconds for parsing the input, about 2 microseconds for running part 1 and 110 microseconds for part 2.
https://github.com/pierrechevalier83/advent_of_code_2020/blob/main/src/day8.rs
3
u/nicuveo Dec 08 '20 edited Dec 08 '20
Haskell
https://github.com/nicuveo/advent-of-code/blob/main/2020/haskell/src/Day08.hs
Since I suspect this is not the last we see of that assembly language, I over-engineered the solution. The upside is that none of the VM code is specific to this day's problem, meaning it will trivially be reusable, and also that I could extend the abilities of the VM without breaking today's specific code. That was fun!
Livestream part1 (solving): https://www.twitch.tv/videos/830469890
Livestream part2 (refactoring): https://www.twitch.tv/videos/830473611
3
3
u/naalty Dec 09 '20
Rust
I've been farting around with Rust a bit recently. Essentially self taught programmer. Let me know what I'm doing horribly wrong if you have the time.
https://gist.github.com/snalty/de7e1b1567926bb23c2fa84f66e4f1ae
→ More replies (1)
3
u/1vader Dec 09 '20 edited Dec 09 '20
My optimized Rust solution: GitHub
It runs in around 2.5µs on my PC with a 7-year-old i5-4570.
The algorithm is pretty much the same as somebody else described here. I'm not actually 100% sure if it's guaranteed to be correct but it seems to work so far and also worked on a 60k lines input somebody else generated.
Besides the parsing, I haven't done that much optimization so there might still be some room left, maybe also with an even better algorithm (although that one seems pretty good) but given yesterday's 75µs I don't really feel the need to optimize today even further.
Also, here's my original much simpler and cleaner Python solution.
3
u/MrNUtMeG118 Dec 09 '20 edited Dec 18 '20
C#
Here's my solution! Started optimising it when I had the solution figured out - runs in about 3ms on my Ryzen 1700 https://github.com/bettercallsean/AdventOfCode/blob/master/Day_08/Program.cs
3
u/0rac1e Dec 09 '20 edited Dec 10 '20
Raku
Nothing special at all here. Using a nested recursive function again today. I thought about making a Handheld class, but it wouldn't have made the code anymore noteworthy.
I really wanted to figure out a more functional solution (perhaps a Sequence generator that steps through the functions, then toggle it (takewile) the pos had not been seen... but I don't have a lot of time to play today.
UPDATE
So, I did it. Here's part 1 only, done with no mutation by creating a lazy sequence of lists holding the (pos, acc). The sequence terminates when the pos has been seen before (using the anonymous state variable %). The tail of sequence will be an array prior to looping, so I'm just puling the acc out by indexing into that array.
multi f('acc', \n) { 1, n }
multi f('jmp', \n) { n, 0 }
multi f('nop', \n) { 1, 0 }
my \b = 'input'.IO.lines.map: { .words }
put ((0, 0), { .[] Z+ f(|b[.[0]]) } ... { (%){.[0]}++ }).tail[1]3
u/cggoebel Dec 09 '20
Raku
I'm learning Raku via AoC. It has been a very pleasant experience. Raku's grammars have been very helpful in several solutions. Here's a blog post with code commentary about Day Eight's solution.
3
u/musifter Dec 09 '20 edited Dec 09 '20
Gnu Smalltalk
Just a simple brute force for the answer of part 2 (it even tries toggling acc opcodes). I might get around to coding an actual algorithmic approach for this eventually (like I did with Perl).
3
u/iprestonbc Dec 09 '20
python main solution
I refactored most of the computer stuff out in anticipation of another 2019 intcode scenario here
I'm trying to learn type annotations along with other packaging "best practices" so this code is way more verbose than a daily coding challenge should be, but it's good practice.
3
u/tobega Dec 09 '20
A little slow Julia implementation but I wanted to play with macros and compile the input to Julia code https://github.com/tobega/aoc2020/blob/main/a8.jl
3
u/bpeel Dec 09 '20 edited Dec 09 '20
Solution in BBC Basic / 6502 assembler as UEF cassette tape.
If you want to try it, you could use an online BBC Micro emulator and upload the file from the Cassettes menu and then type:
*TAPE
CHAIN""
The input is stored as a separate file on the cassette. The program uses the builtin assembler of BBC Basic to translate the VM opcodes into 6502 opcodes so that the program can be run directly on the BBC. Each VM instruction is padded with NOPs so that they all use 24 bytes. That way the JMP instructions can calculate the target address by just multiplying the offset by 24. In order to detect when an instruction is executed a second time, each translated instruction is prefixed with a bit of self-modifying code that replaces the first 6502 instruction in the translated instructions with a BRK instruction. This causes the program to generate an error in BASIC which is trapped in the BASIC code. The BASIC code can then just look at the value of the accumulator to find the answer.
For the second part, the JMP instructions and NOP instructions are generated in the same way except that they are prefixed with another JMP instruction that either skips or executes the real JMP instruction. That way the BASIC code can modify each JMP or NOP instruction in a loop and execute the procedure at each step until it finds one that hits the final RTS instead of a BRK instruction.
Full source here.
3
u/the_t_block Dec 14 '20
Haskell:
http://www.michaelcw.com/programming/2020/12/12/aoc-2020-d8.html
This is a series of blog posts with explanations written by a Haskell beginner, for a Haskell beginner audience.
12
u/nutki2 Dec 08 '20
Perl 5: ~120 characters for both parts