Robert Mion

Posted on

Handheld Halting

Advent of Code 2020 Day 8

``````X = the value of accumulator at some N time
``````
1. N = Prior to the first time any step is repeated
2. N = After the last instruction is read - given one change to make the program successfully terminate

Example input

``````nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
``````

It represents:

• Boot code
• One instruction per line
• Each line contains an operation and an argument
• The operation could be: 1. do nothing, 2. accumulate some changing value, 3. jump to another instruction line

Part 1

1. Identifying the items to keep track of
2. Writing an algorithm I think will work
3. Smiling because it worked

Identifying the items to keep track of

1. An accumulator, which starts at 0
2. A unique list of indices visited
3. The current instruction line being read
4. The next instruction line index

Writing an algorithm I think will work

``````Split the input at each new line character into an array of strings
Split each string at the space character into a 2-element array of strings
Convert the second string into a positive or negative number

Set an accumulator at 0
Set a unique list of indices as empty
Set the next instruction line index as 0

Do as long as the next instruction line index is not in the unique list of indices
Look-up the 2-item array at the next index
If the first item is 'nop'
Add the index to the unique list
Increment the value stored in next instruction line
Else, if the first item is 'acc'
Add to accumulator the value stored in the second item
Add the index to the unique list
Increment the value stored in next instruction line
Else, if the first item is 'jmp'
Add the index to the unique list
Update the value stored in next instruction line to the sum of this item's index and the value of the second element

The above loop should finish as soon as the next instruction line's index is the first to already be in the unique set, meaning it has been visited

Return accumulator
``````

Hooray!

Part 2

1. My brute-force working algorithm
2. Considering my algorithm's performance

My brute-force working algorithm

``````Set a correct accumulator that will eventually reflect the fully accumulated value from the program that runs to termination

Identify each instruction line with either a `nop` or `jmp` operation

For each of those lines
Create a clone of the full list of instructions
Change the operation at the current line to swap 'nop' for 'jmp' or vice versa
Run the single-line modified program, tracking the unique set of indices visited, the next index expected, and an accumulator...until the next index exists in the unique set of indices visited

As soon as the next index expected is equivalent to the length of the list of instructions - indicating that the program finally terminated:
Update the correct accumulator to equal the currently tracked local accumulator
Break out of the outer loop

Return the newly-set value in the correct accumulator
``````

Here's a visualization of my brute-force algorithm:

Considering my algorithm's performance

For my puzzle input, the worst-case scenario was that this loop ran nearly 250 times, generating nearly 250 clones of the instruction list, which contains just over 650 instructions.

So, not optimal in space or time complexity.

But...it generated a correct answer in what felt like under 1 second.

So, mission accomplished!