Space Police

Advent of Code 2019 Day 11

Try the simulator with your puzzle input!

Task: Solve for X where...

Part 1

X = the number of panels painted at least once by the emergency hull painting robot

Part 2

X = the eight-letter registration identifier revealed by all white-colored panels after the robot finishes painting

Example input

• No example Intcode program is offered
• An example path is depicted with simulated movement directions as indicated by some imagined Intcode program's output

.....   .....   .....   .....   .....
.....   .....   .....   .....   ..<#.
..^..   .<#..   ..#..   ..^..   ...#.
.....   .....   .v...   .##..   .##..
.....   .....   .....   .....   .....

It represents:

• The path followed by an emergency hull painting robot
• The arrow shows which way the robot faces
• .s indicate black panels
• #s indicate white panels

Part 1

1. Intcode computer: Round 5!
2. Running the program to see some of the outputs
3. Updating my Intcode computer to manage all this new state
4. Running the program to confirm expected key-value pairs
5. Running the program to display the correct answer
6. A visual depiction of my algorithm

Intcode computer: Round 5!

• Good news: as stated Round 4 (a.k.a. Day 9), there are no new features to add!
• Fun news: it seems this - and possibly future puzzles - will leverage the output of a program running on my Intcode computer to generate a correct answer

In this puzzle

The program uses input instructions to access the robot's camera

• 0 and 1 will be the only inputs

There will be two outputs every so often:

1. The color to paint the panel that the robot is on
2. The direction the robot must rotate: clockwise or counter-clockwise

Other important notes:

• After the robot turns, it should always move forward exactly one panel
• The robot starts facing up

Running the program to see some of the outputs

Starting with 0 as input and never updating it:

• Over 19,000 0s and 1s are output

Starting with 1 as input and never updating it:

• About 500 0s and 1s are output

Fascinating!

Updating my Intcode computer to manage all this new state

I need to keep track of:

• The current direction the robot faces
• The current location of the robot at any given time
• The current length of the list of integers output thus far
• The number of panels that have been painted at least once
• The integer stored as input
• The new color of the current panel

The current direction the robot faces

It starts at up.

So the first move is to relative coordinate -1,0.

What about the other directions?

Up:    -1,0
Right: 0, 1
Down:  1, 0
Left:  0,-1

When saved as a list:

[[-1,0],[0,1],[1,0],[0,-1]]

When the robot is instructed to turn left:

• Move the last item to the front of the list

When the robot is instructed to turn right:

• Move the first item to the end of the list

Always refer to the first item as the direction the robot currently faces.

The current location of the robot at any given time

It starts at 0,0.

After rotating, move the robot one step in the current direction:

X,Y as current coordinates

New coordinates can be determined:
X + first value in first item
Y + second value in first item

The current length of the list of integers output thus far

• Every opcode 4 adds the appropriate value to a list of output values, starting as empty
• Every odd output value indicates the color to paint the panel the robot is over
• Every even output value indicates the direction the robot should turn
• I'll continually need to check the length of the list to know whether it contains an odd or even number of values
• And I'll continually need to reference the one or two most recently added values

The number of panels that have been painted at least once

• I'll use a dictionary/hash/object
• Where the keys are stringified coordinates of the robot's visited locations relative to an origin location of 0,0
• And the values are either 0 or 1 signifying the current color of the panel at that relative coordinate

The integer stored as input

• It starts as 0
• It must reflect the color of the panel that the robot has moved to after rotating.
• To determine this, I'll check whether my dictionary of visited coordinates contains the coordinate of the panel that the robot just moved to
• If it has been visited, I'll set input to its value
• It it is a newly visited panel, I'll set input to 0 because all panels start as black

The new color of the current panel

• In my opcode 4 instruction
• If the newest value in output is odd
• I need to either create a key and set it's value...or update the value associated with the existing key representing the current relative coordinate...to the output value

And if the newest value in output is even, I need to perform the directional update, the forward movement, and the input update.

Running the program to confirm expected key-value pairs

With all the work above complete, I was ready to run my Intcode program again.

I saw output like this:

'-31|4': 0
'-68|24': 1
...

Success! I was recording painted panels correctly!

Running the program to display the correct answer

Thankfully, this was a simple, one-line addition:

Return the count of all keys in the painted panels dictionary

A visual depiction of my algorithm

Part 2

1. Drawing the board to reveal the registration identifier
2. Building a robot painting simulator

Drawing the board to reveal the registration identifier

Since 0,0 is not likely to be in the top-left corner, I have to calculate what the size of the board is:

Extract the keys from the painted panels dictionary
  Split each key at the pipe character to generate a 2-element array of strings
    Coerce each string to a number

Calculate the largest/smallest X/Y values

Generate a grid where:
  The height is the difference between max and min Y values
  The width is the difference between max and min X values
  Fill each cell with an empty space character

For each item containing three values (X, Y, panel color) in the painted panels dictionary
  Update the corresponding grid cell with either a # or a space character, depending on the panel color

Display the grid by concatenating each character in each row, then joining each row with a newline character

Write down the revealed registration identifier

I had the axes mixed up the first time I ran this algorithm.

After swapping X and Y, I saw my eight-letter identifier.

And it was the correct answer!

Building a robot painting simulator

• I wanted to render each pixel of the identifier as the robot painted it white
• This required running the program twice: once to calculate the size of the grid, and again to actually paint each panel
• The code got very messy - with lots of copy-pasting and global variables - but I got it to work as expected for my puzzle input

Try the simulator with your puzzle input!

I did it!!

• I solved both parts!
• I made a GIF to visualize my algorithm for Part 1
• I made another simulator, this time of the painting robot
• I've now solved five Intcode puzzles - this one being an unexpected one that wasn't in my original list of dependencies (probably because it required no additional features of the Intcode computer)