Advent of Code: 2020 Day 08
Tags: adventofcode, python
Published: 2020-12-08 07:30:48


⚠️ **SPOILER ALERT** ⚠️
This is a post with my solutions and learning from the puzzle. Don't continue reading if you haven't tried the puzzle on your own yet.

If you want to do the puzzle, visit [adventofcode.com/2020/day/8](https://adventofcode.com/2020/day/8).

My programming language of choice is `python` and all examples below are in python.

## Key learning <a name="key-learning"></a>

* Simple compiler

This puzzle is a really simple compiler where we execute one of three instructions and only keep track of one value in memory. For those beginning to learn programmingmthis is valuable lesson to start understanding compilers and some of the core concepts of code.

## Puzzle <a name="puzzle"></a>

The puzzle about is to executing a set of instructions according to a specification. We have three operators `jmp`, `acc`, `nop`. Each instuction is one operator followed
by a value.

Quoted from advent of code:
- acc increases or decreases a single global value called the accumulator by the value given in the argument. For example, acc +7 would increase the accumulator by 7. The accumulator starts at 0. After an acc instruction, the instruction immediately below it is executed next.
- jmp jumps to a new instruction relative to itself. The next instruction to execute is found using the argument as an offset from the jmp instruction; for example, jmp +2 would skip the next instruction, jmp +1 would continue to the instruction immediately below it, and jmp -20 would cause the instruction 20 lines above to be executed next.
- nop stands for No OPeration - it does nothing. The instruction immediately below it is executed next.

**Example input:**
```
nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6
```

## Part 1 <a name="part-1"></a>

The instructions we receive as input creates a program with an infinite loop. The puzzle is to figure out what the `accumulator` is at the end of first loop.

I'm using a `set` for keeping track of where the instruciton-cursor has been. With that we know when the first loop is complete.

### Parsing input

```python
# Read in instructions from file
lines = [x.strip() for x in open('08.input', 'r').readlines() if x != '']

# Create tuples (x,y) where x is instruction and y is value
lines = [tuple(x.split()) for x in lines]
```

### Solution: Quick

Just by reading part 1 one might write some code like this. A `while`-loop with some if statements containing operations to execute.

It might look like this:

```python
def part1():
    lines_executed = set()
    cursor, accumulator = 0, 0

    while cursor not in lines_executed:
        instruction = lines[cursor][0]
        lines_executed.add(cursor)
        if instruction == 'jmp':
            cursor += int(lines[cursor][1])
        elif instruction == 'nop':
            cursor += 1
        elif instruction == 'acc':
            accumulator += int(lines[cursor][1])
            cursor += 1
        else:
            raise Exception('Unexpected instruction', instruction)
    return accumulator
print part1()
```

### Solution: Extendable

Those that competed in AoC 2019 might have some flashbacks of the [intcode](https://adventofcode.com/2019/day/2) that has it similarities. A simple compiler with a few instructions. That puzzle came back multiple times and we had to built upon our compiler with new operations and features. Investing in good structure at the beginning might be beneficial for coming puzzles.

Therefore I suggest finding a structure that you find more extendable.

Here is a suggestion:

```python
def execute_program(lines):
    lines_executed = set()
    cursor = 0
    accumulator = 0

    def acc(lines, cursor, accumulator):
        return (cursor + 1, accumulator + int(lines[cursor][1]))

    def jmp(lines, cursor, accumulator):
        return (cursor + int(lines[cursor][1]), accumulator )

    def nop(lines, cursor, accumulator):
        return (cursor + 1, accumulator)

    while cursor not in lines_executed:
        instruction = lines[cursor][0]
        lines_executed.add(cursor)
        operations = {
            'jmp': jmp,
            'acc': acc,
            'nop': nop,
        }
        operation = operations[instruction]
        cursor, accumulator = operation(lines, cursor, accumulator)
    return accumulator

print "Solution part 1: %d" % execute_program(lines)
```

Do you find it more readable? Do you have other solutions or tips on making the compiler more extendable?

## Part 2 <a name="part-2"></a>

We find out that one `jmp` or `nop` should be the other for executing the program without infinite loop.

Our execute program needs minimal change. Just a variable (`terminated`) to keep track if we reached the last instruction.

Then we just have to iterate through all `jmp` and `nop`, switch them, execute the program, and see if it was terminated or not.

### Solution

```python
def execute_program(lines):
    lines_executed = set()
    cursor = 0
    accumulator = 0

    def acc(lines, cursor, accumulator):
        return (cursor + 1, accumulator + int(lines[cursor][1]))

    def jmp(lines, cursor, accumulator):
        return (cursor + int(lines[cursor][1]), accumulator )

    def nop(lines, cursor, accumulator):
        return (cursor + 1, accumulator)

    terminated = False
    while not terminated and cursor not in lines_executed:
        instruction = lines[cursor][0]
        lines_executed.add(cursor)

        operations = {
            'jmp': jmp,
            'acc': acc,
            'nop': nop,
        }
        operation = operations[instruction]
        cursor, accumulator = operation(lines, cursor, accumulator)

        # Terminate if end at program
        terminated = cursor == len(lines)

    return terminated, accumulator


def part2(lines):
    for i in range(len(lines)):
        # Copy lines so that changes don't persist.
        local_lines = [x for x in lines]

        # Switch statement jmp/nop
        if 'jmp' in local_lines[i][0]:
            local_lines[i] = ('nop', local_lines[i][1])
        elif 'nop' in local_lines[i][0]:
            local_lines[i] = ('jmp', local_lines[i][1])

        terminated, result = execute_program(local_lines)

        if terminated:
            break
    return result
print "Solution part 2: %d" % part2(lines)
```

## Thanks for reading!

I hope these solutions were insightful for you.

Complete code can be found at: [github.com/cNille/AdventOfCode/blob/master/2020/08.py](https://github.com/cNille/AdventOfCode/blob/master/2020/08.py)