# Advent of Code day 8

[Today's problem](https://adventofcode.com/2020/day/8) is a straightforward assembly language type problem. We see something like this every year in Advent of Code.  

The possible instructions are 'acc', 'jmp', and 'nop'.  In more detail:

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

For Part 1 we are told that the instructions cause an infinite loop.  Our mission is to build a wrapper code that goes through the instructions line by line and determines when we hit the same instruction twice.  This part is pretty straightforward -- comment if you have questions. 

For part 2 we need to change one ‘nop’ to ‘jmp' or one ‘jmp’ to ‘nop’ to stop the program from getting caught get into the infinite loop. Our mission is to find out which instruction needs the swap. My first thought is to just go through the instructions line-by-line and try each possibility until the program runs, but that is pretty inefficient.  Let’s think a bit.  

How can we make this faster? Instead of 1) starting from index 0, then index 1, etc and trying to change nop/jmp at each line, we could 2) go through the instructions we actually take as we follow the logic of  the code -- in the example there are instructions that are never visited, so if that were true for the real input that would save some time.  We could also 3) start from the end of the instructions instead of the beginning with the thought that the problem is near the end. These seem like incremental improvements rather than a new way of looking at the problem, but maybe they will help.  

I implement this solution (option 2) and it works fine -- it didn’t take much time, so maybe my worry about efficiency was not necessary.  I guarantee that efficiency will be important in the coming days, though.  

My full solution is over at [Github](https://github.com/alyshareinard/Advent-of-Code-2020)