Space Police
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-05-06 20:13:33

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

## [Try the simulator with your puzzle input!](https://aocspacepolice.rmion.repl.co/)
![Simulator of painting robot](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1ll113xyxh8mfboyieqw.gif)

## 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 `0`s and `1`s are output

Starting with `1` as input and never updating it:
- About 500 `0`s and `1`s 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
![Visualization of Part 1's algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bq99lfxqabvq1yqv25oe.gif)

## 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!](https://aocspacepolice.rmion.repl.co/)
![Simulator of painting robot](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1ll113xyxh8mfboyieqw.gif)

## 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)