Amplification Circuit

Advent of Code 2019 Day 7

Try the simulator for Part 1 using your input!

Task: Solve for X where...

X = the highest signal that can be sent to the thrusters

Example input

3,15,3,16,1002,16,10,16,1,16,15,15,4,15,99,0,0

It represents

• An Intcode program similar to ones seen in Days 2 and 5

Part 1

1. Here we go again
2. Sub-puzzle: Find all permutations
3. Recalling Intcode program iterations
4. Updating the Intcode program for two inputs and one transferrable output
5. Writing the new core loop of a new Intcode computer
6. Building the next iteration of my Intcode computer simulator

Here we go again

• Another puzzle that makes use of the Intcode program I've been building
• Fortunately, it seems there are no new opcodes to add
• But I will have to account for two inputs, one output, and the need to run the same program in its original state several times in a row

Sub-puzzle: Find all permutations

• Five amplifiers must run the same starting Intcode program, one after another
• Each amplifiers must use two inputs: a unique integer between 0 and 4 inclusive, and the output of the previous amplifier's program - or 0 for the first amplifier
• I must test all permutations of the order of integers

I could attempt to hand-craft the list of 120 (5-factorial or 5!) 5-element arrays, some of which would look like these:

[0,1,2,3,4]
[3,2,4,1,0]
[4,1,3,0,2]

But I presume this puzzle expects me to write an algorithm to generate that comprehensive list of permutations of integers 0,1,2,3,4.

After some thought, I couldn't think of how I would write this algorithm.

I'm also more interested in updating my Intcode program to accommodate any of these permutations.

So, I did some Googling and found a detailed walkthrough of how to write this exact algorithm and a more concise, eloquent, functional variant.

I appreciate the first article's attempt to hold the reader's hand and step through the recursive algorithm using [1,2,3] as input.

I also appreciate the alternative algorithm for its terseness.

The core mechanics of both algorithms seems to be:

For each item in the list
  Remove that item from the list
  Repeat until the list contains two items
  Stamp out two lists - one where the items are in their original spots and one where they are swapped
  Return both lists to the calling function
  Merge both lists with the removed item
  Return those larger lists to the calling function

By the time the originally-called function for each item in the original list is completed, a comprehensive list of all permutations will have been generated and merged back with that item

Recalling Intcode program iterations

For Day 2

• There were no inputs, and the output was the value that remained in location 0
• Instead, I had to change two values in the Intcode program prior to running so it would store some expected number in location 0

For Day 5

• There was one input, and either several or one output
• That single input was fed to the first instruction opcode
• The program only ran once, so I didn't need to store the output...just log it

For Day 7

• There are two inputs, and the output must become one of two inputs
• I can't pre-plan for where the second input will go
• And I must now store the output for use in subsequent program runs

Updating the Intcode program for two inputs and one transferrable output

1. My method for handling opcode 3's instructions needed a small update
2. As did the one for handling opcode 4's instructions

opcode 3

Before:

Assign to the appropriate memory address in the Intcode program some one-time input
Update the address pointer

After:

Outside of the instruction, initialize a tracker to 0
First time encountered: Assign to the appropriate memory address in the Intcode program the value at the location specified by tracker in a 2-element input array
Increment tracker: it's now 1
Second time encountered: Assign to the appropriate memory address in the Intcode program the value at the location specified by tracker in a 2-element input array
Update the address pointer

opcode 4

Before:

Add the value at the appropriate memory address in the Intcode program to a list of output integers
Update the address pointer

After:

Outside of the instruction, initialize an output to null
Set as output the value at the appropriate memory address in the Intcode program

Writing the new core loop of a new Intcode computer

Initialize four placeholders:
1. Address pointer
2. Input
3. Tracker
4. Output

For each 5-element array in the list of 120 phase permutations
  Update the 5-element array to a single integer that results from the following operations:
    For each integer in the ordered list of numbers 0-4
      Accumulate a number - starting at 0 - based on the following operations:
        Split the puzzle input at each comma character to generate a list of strings, then coerce each string to a number
        Set the four placeholders as follows:
          1. Address pointer = 0
          2. Input = 2-item list: [current integer 0-4, accumulated number from prior iteration]
          3. Tracker = 0
          4. Output = null
        Do as long as Pointer is less than the length of the Intcode program, and the value at Pointer is not 99, and Output is null
          Parse the current opcode, parameter mode, and perform the instruction - optionally updating the address pointer and output
        By now, Output should not be null, and instead should be an integer
        Return the integer

Return the largest number among the updated list of integers

Building the next iteration of my Intcode computer simulator

• I built a simulator for Days 2 and 5...so I had to make one for today
• The difficult part for this simulator was all the DOM manipulation for each of the bits of data: phase, output, program, and highest number
• The result is a fairly interesting peek into how certain integers inside the Intcode program update for each of the phases

Try the simulator using your input!

Part 2

1. Trying to fully comprehend the instructions
2. Updating my Intcode computer with less-than-full understanding
3. Over-complicating things as a last-ditch effort
4. I can't believe that worked!

Trying to fully comprehend the instructions

New example input

3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26,
27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5

New rules...that I feel I fully understand

• The phase integers are not 5,6,7,8,9 - not 0,1,2,3,4
• The process doesn't stop after Amplifier E runs the first time. Instead, the process loops back to Amplifier A using E's output.
• Each amplifier still uses it's own copy of the puzzle input Intcode program
• More still, each amplifier uses the mutated copy of its program during each subsequent iteration in its part of the feedback loop
• The first signal sent to Amplifier A is still 0
• It is safe to check for five halted programs as a way to test whether the feedback loop has ended

New rules...that I felt unsure of

These bits of instructions left me with uncomfortable ambiguity, even after several re-reads:

Provide each amplifier its phase setting at its first input instruction; all further input/output instructions are for signals.

• For all iterations after the first one through each Amplifier, am I expected to provide two inputs still (the phase and the signal)...or just the signal from the previously-running Amplifier?

Don't restart the Amplifier Controller Software on any amplifier during this process.

• I recognize that each copy should maintain its program's mutated Intcodes from each most recent iteration. But I wasn't sure whether the address pointer should always reset to 0 and run the program from start...or if I should pick-up right where the pointer had jumped to after running the most recent output instruction?

Updating my Intcode computer with less-than-full understanding

My goal was to run it on the first new example input and see if any of the output signals from Amplifier E was the max thruster signal referenced in the instructions for the given phase settings.

At this point, I chose to reset each pointer to 0 for each amplifier and not explicitly track whether each amplifier's last instruction was to halt.

Modifications:

• A new array with five independent - but identical - Intcode programs
• Updated instructions for opcode 3
• Expanded parameters for my instruction parser and each of my opcode instructions
• Tweaked all references to address pointers and Intcode program arrays to accommodate my new five-element array

Result:

• Since I wasn't sure how to set up the while loop, I started with a for loop that ran 30 times
• By way of logging each amplifier's output in each iteration, I saw the expected thruster signal among the list of outputs
• It wasn't the last output, though, which was concerning
• I still didn't know how to make the loop stop at the correct output signal

Over-complicating things as a last-ditch effort

I re-factored my code to account for several new global variables:

• Five address pointers
• Five outputs
• Five trackers for whether each Amplifier's code had halted

I added a check in my opcode parser for opcode 99.

I refactored my opcode 3 instruction to account for iterations 1-5 and 5+ (assuming amplifiers would receive two inputs initially, then one input every time thereafter).

Result:

• Success with new example input 1/2!
• Success with new example input 2/2!
• Success with my puzzle input!!!!!!!

I can't believe that worked!

• I was prepared to move on from this puzzle recognizing that I didn't fully understand the instructions
• I was prepared to only troubleshoot my Frankenstein algorithm enough to see outputs that never ended
• I was prepared to be disappointed

I did it!!

• I solved both parts!
• That means I actually solved Part 2!
• I built another Intcode computer simulator that at least runs Part 1
• Thus far, in total, I've solved all Intcode puzzles
• That means I still have a chance at solving Day 25

I'm exhausted from today's puzzle.

I'd love a break from these Intcode puzzles.

Sadly, I recall Day 9 being another one.

Here's to hoping Day 8 is either a softball or such a curveball that I can just accept the strike.