Advent of Code 2019 Day 2
Try the simulator!
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
- Visualizing the nested look-up process
- Writing a working algorithm
- 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
Part 2
- Writing a brute-force working algorithm
- Using the simulator to spot a pattern
- Writing a more performant working algorithm
Writing a brute-force working algorithm
- In Part 1, the
nounandverbwere prescribed - In Part 2, the correct
nounandverbmust 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/)
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!
Top comments (0)