1202 Program Alarm
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-04-19 15:07:02

## [Advent of Code 2019 Day 2](https://adventofcode.com/2019/day/2)

## [Try the simulator!](https://aoc1202programalarm.rmion.repl.co/)
![Simulator showing Part 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/53vfal4gqfmtwy19iqjl.gif)

## Task: Solve for X where...
Part 1
```
X = the value left at position 0 after the modified program terminates
```
Part 2
```
X = the result of an equation combining the noun and verb inputs that modify the program such that it terminates with value 19690720 at position 0
```

### Example input
```
1,9,10,3,2,3,11,0,99,30,40,50
```
It represents:
- A list of comma-separated integers
- Where some integers represent opcodes - 1, 2 or 99
- And other integers represent instructions for which locations to look-up and whether to add or multiply their values

## Part 1
1. Visualizing the nested look-up process
2. Writing a working algorithm
3. A visual depiction of the algorithm

### Visualizing the nested look-up process
As the instructions indicate:
```
1,9,10,3,2,3,11,0,99,30,40,50

1 = Consider the next three locations
  9 10 3
  1  2 3

Look-up the values in locations 1 and 2
                      9 10
                     30 40

1 = Add them together
                     30+40=70

Store the result in the location referenced by the value in location 3
       3
       3

Resulting in:
       70

Updating the program to:
1,9,10,70,2,3,11,0,99,30,40,50
```

### Writing a working algorithm
```
Split the input at each comma to create a list of strings
  Coerce each string to a number
  Change the value of the number at location 1 (the second value) to 12
  Change the value of the number at location 2 (the third value) to 2

Set a starting address at 0

Do as long as address is not equal to or greater than the length of the list of intcodes AND the value at the current address is not 99
  If the value at the current address is a 1
    Update the value at the location specified by the value at the location equal to the current address plus 3 by the sum of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
  Else, if the value at the current address is a 2
    Update the value at the location specified by the value at the location equal to the current address plus 3 by the product of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
  Increment address by 4

Return the new value stored at the first location in the list of intcodes
```

### A visual depiction of the algorithm
![Simulator or Part 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r5eno0wevxzkdtgpepwo.gif)

## Part 2
1. Writing a brute-force working algorithm
2. Using the simulator to spot a pattern
3. Writing a more performant working algorithm

### Writing a brute-force working algorithm
- In Part 1, the `noun` and `verb` were prescribed
- In Part 2, the correct `noun` and `verb` must be identified, given the same integer boundaries: `0-99`

Let's say the correct `noun` and `verb` are 99 and 99.

An algorithm that checked every possible combination, starting with 0 and 0, would have to run a modified program 10,000 times.

That's not terrible, and will probably finish in a second.

What's that algorithm look like?
```
Create variables for noun and verb
For n as 0 through 99
  For v as 0 through 99
    Split the input at each comma to create a list of strings
      Coerce each string to a number
      Change the value of the number at location 1 (the second value) to n
      Change the value of the number at location 2 (the third value) to v

    Set a starting address at 0

    Do as long as address is not equal to or greater than the length of the list of intcodes AND the value at the current address is not 99
      If the value at the current address is a 1
        Update the value at the location specified by the value at the location equal to the current address plus 3 by the sum of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
      Else, if the value at the current address is a 2
        Update the value at the location specified by the value at the location equal to the current address plus 3 by the product of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
      Increment address by 4

If the new value stored at the first location in the list of intcodes is 19690720
  Set the values of noun and verb respectively to n and v
  Break out of the loop

Return the sum of verb and the product of 100 and noun
```

### Using the simulator to spot a pattern
After building a simulator for Part 2, the effect of each integer 0-99 for noun and verb becomes apparent:
- The integer for verb modifies the last two digits
- The integer for noun modifies all earlier digits (4-5)

### Writing a more performant working algorithm
- I don't have to check each integer verb for each integer noun
- Instead, I can separately check each noun and verb for when each becomes equal to the corresponding sub-integer of the larger output number
- As long as the two are not equal, I can increment the correct one(s) separately

```
Sub-routine: Run
- Accept two parameters, noun and verb
Split the input at each comma to create a list of strings
  Coerce each string to a number
  Change the value of the number at location 1 (the second value) to noun
  Change the value of the number at location 2 (the third value) to verb
Set a starting address at 0
Do as long as address is not equal to or greater than the length of the list of intcodes AND the value at the current address is not 99
  If the value at the current address is a 1
    Update the value at the location specified by the value at the location equal to the current address plus 3 by the sum of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
  Else, if the value at the current address is a 2
    Update the value at the location specified by the value at the location equal to the current address plus 3 by the product of value at the location specified by the value at the location equal to the current address plus 1 and the value at the location specified by the value at the location equal to the current address plus 2
  Increment address by 4
Return the value stored at location 1

Main loop:
Set noun and verb each to 0
Call Run once, passing in noun and verb
  Store the result as a variable, output
Do as long as output does not store the value 19690720
  Create an integer from all but the last two digits of the value stored in output
  Create an integer from the last two digits of the value stored in output
  If the first integer is not equal to 196907
    Increment noun by 1
  If the second integer is not equal to 20
    Increment verb by 1
  Call Run again, passing in noun and verb
    Store the result in output

Return the sum of verb and the product of 100 and noun
```

As you can see in this animation of the simulator, my puzzle input only requires 72 iterations...instead of the 5,121 using the earlier brute-force algorithm
(https://aoc1202programalarm.rmion.repl.co/)
![Simulator showing Part 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/53vfal4gqfmtwy19iqjl.gif)

I wanted to make the algorithm even more performant by using Binary Search to find the correct noun and verb for my input.

That likely could bring down the number of iterations to a number between 10-15.

Oh well. I'm still proud that:
- I solved both parts
- And that I solved Part 2 with a more performant algorithm than brute-force
- Especially after using my simulator to spot the hidden pattern!