Tractor Beam
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-05-19 23:36:11

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

## Task: Solve for X where...
### Part 1
```
X = the number of points affected by the tractor beam in the 50x50 area closest to the emitter
```
### Part 2
```
X = the sum of (the product of a point's X coordinate and 10000) and (a point's Y coordinate) where that point is the top-left-most point among a 100x100 area of points closest to the emitter where all points are affected by the tractor beam
```

## No example input given
Instead, as in recent Intcode puzzles, example output is offered:
```
       X
  0->      9
 0#.........
 |.#........
 v..##......
  ...###....
  ....###...
Y .....####.
  ......####
  ......####
  .......###
 9........##
```
It represents:
- The visualization of a tractor beam's pull along a 2D area, as determined by a drone
- `#`s mean there's pull
- `.`s mean there's no pull

## Part 1
1. Generating the list of coordinates
2. Assuming the program will run once on all coordinates
3. Being wrong: the program runs on a single coordinate
4. Generating a picture of the tractor beam's pull
5. Counting the points

### Generating the list of coordinates
- I need the robot to visit X from 0-49 and Y from 0-49

In other words:
```
[0,0]
[0,1]
...
[0,49]
[1,0]
...
[1,49]
...
[49,49]
```

I used two loops to generate such a list:
```
Create coords, an empty list
For row from 0 to 49
  For col from 0 to 49
    Add to coords [row, col]
```

### Assuming the program will run once on all coordinates
- Because that's how the last Intcode program ran
- I had to keep track of two numbers: 1) the nested list, and 2) the location within that list
- Any time the location reached a value equivalent to the length of the list, I had to increment the location of the nested list tracker and reset the other value to 0 so it would begin again at the start of the next list

I got it working, only to discover...

### Being wrong: the program runs on a single coordinate
- This Intcode program only uses two inputs and only generates one output before halting
- Therefore, the state management code I wrote is meaningless
- Instead, I need to run the program for each set of coordinates

```
For each set of coordinates in coords
  Parse the input string of comma-separated integers into a list of numbers
  Do as long as the value in the list at the current memory address is not 99
    Parse the opcode and parameter mode and perform the instruction
      When the opcode is 3, update input to reflect the correct coordinate
      When the opcode is 4, add to output the new value
```

### Generating a picture of the tractor beam's pull
- I confirmed the output contained `1`s and `0`s
- Next, I need to generate a 2D array where the values are either `#`s or `.`s
- Thankfully, several prior puzzles have made me highly practiced in completing this task

```
Create an array with 50 nested arrays, each with 50 items initialized to the space character

For each set of coordinates (and their location) in coords
  Update the value corresponding to the nested array and item in that array as signified by the coordinate's values at locations 2 and 1 (Y,X or Row,Col) based on the following condition:
    If the value at the same location of the coordinate array in coords as in output is 1
      Set the value to #
    Else, if the value in output at the same location is 0
      Set the value to .

Print the grid's values as a square area by concatenating each character in the nested arrays, then joining each string with a newline character
```

The result is this depiction of the tractor beam
![The tractor beam visualized](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3r8l01lomvro56vf8mqj.png)

### Counting the points
- I added a variable `points` initialized to 0
- I incremented it by the value in output at the same location in coords: 0 or 1
- Lastly, I had my program return points

Thankfully, it was the correct answer!

## Part 2
1. How long will it take to double the area?
2. Noticing the pattern of the beam
3. Trying my hardest to deduce the answer
4. Returning to the challenge five 'days' later
5. Describing my new strategy

### How long will it take to double the area?
- I changed `50` and `100` and ran my program again
- I waited about 10 seconds before I saw the tractor beam rendered
- The highest number of contiguous points affected by the beam was about 10
- Clearly, I would have to render an area closer to 1000x1000 to reach the first contiguous points totaling 100 along a single axis
- That seems unfeasible, so there must be another way

### Noticing the pattern of the beam
- Next, I studied the affected points of the beam
![Patterns among the tractor beam affected points](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ff9s3mf83t5azm7t0ukc.gif)

### Trying my hardest to deduce the answer
I was excited, until I saw that last beam length: 9.

It skipped 8!

And it seems like that's the only number it skipped. Why?

#### What is the top-left-most coordinate of areas NxN where N is from 2 to 8?
- 2x2 is [14,20]
- 3x3 is [26,37]
- 4x4 is [37,53]
- 5x5 is [49,70]
- 6x6 is [60,86]
- 7x7 is [72,103]
- 8x8 is [83,119]
```
2 [14,20] 
3 [26,37]   +12,+17
4 [37,53]  +11,+16
5 [49,70]   +12,+17
6 [60,86]  +11,+16
7 [72,103]  +12,+17
8 [83,119] +11,+16
```

I found a pattern!

Now, to play out the arithmetic.

```
Start points at [14,20]
For i from 3 thru 100
  Update the values in points such that
    If i is odd, increment each value by 12, 17
    Else, if if i is even, increment each value by 11, 16
```

When the loop finishes, `points` contains:
```
[ 1141, 1637 ]
```

The puzzle requires that I multiply the first value by 10000 and add the second, which coincidentally just concatenates both together to form:
```
11411637
```

Sadly, that answer is too high.

In good news, the answer using `points` after 99 iterations is too low.

I am close.

I may be off by one.

Or 10,000.

But I don't want to waste any more attempts.

### Returning to the challenge five 'days' later
- For Day 24, I solved Part 1 but threw in the towel for Part 2
- I harbored some shame for not discovering the correct answer to Part 2 of today's puzzle
- I had a strategy in mind, it was just a matter of trial-and-error to write it and run it
- I knew I had to give this one more try

### Describing my new strategy
- Several Reddit solvers mentioned needing to `follow the left-most edge of the tractor beam`
- What would that algorithm look like?

Well, the beam from Y coordinates 40-50 looks like this using my puzzle input:
```
..........................####....................
...........................####...................
...........................#####..................
............................####..................
.............................####.................
.............................#####................
..............................#####...............
...............................####...............
...............................#####..............
................................#####.............
.................................#####............
```

The left edge appears to always increase by one Y coordinate and increase by either zero or one X coordinate.

Where would I start? Well, (33,50) is the lowest left-most edge. How about there?
```
.................................*    ............
```

I then run my Intcode program on three coordinates:
```
.................................*    ............
.................................123..............
```

I'm certain that at least one will result in an output of 1.

The question is, which of these will it be?
```
[0,0,1]
....#####....
......#####..

[0,1,1]
....#####....
.....#####...

[1,1,1]
....#####....
....######...
```

Whichever one it is, I need the coordinate the spawned the first 1 among the group, because that is the next coordinate along the left-most edge.

I use a short loop - running 50-100 times - to continue walking along the left edge until the Y coordinates are greater than 100.

From that point, I can perform the more important check:
- Are the values at coordinates that form a 100x100 square -  with the left-most edge representing the bottom-left edge of that square - all within the boundary of the tractor beam?

Said another way, I am looking for the coordinate labeled X in the diagram below:
```
................###############.........
................#################.......
.................########OOOOOOOOOO.....
..................#######OOOOOOOOOO#....
...................######OOOOOOOOOO###..
....................#####OOOOOOOOOO#####
.....................####OOOOOOOOOO#####
.....................####OOOOOOOOOO#####
......................###OOOOOOOOOO#####
.......................##OOOOOOOOOO#####
........................#OOOOOOOOOO#####
.........................XOOOOOOOOO#####
```

So, each time I identify the next left-most coordinate, I run the program for three other coordinates: each of the other three 'edges' of the 100x100 square.

I know I've found it when my output is:
```
[1,1,1]
```

Since I start my search from Y coordinate 100, I see this for a while:
```
[0,0,0]
```

Eventually, I see this exclusively:
```
[1,0,1]
```

Continuing in batches of 100, I keep my eyes peeled on my console's output for the first:
```
[1,1,1]
```

At last, I spot it!
![The moment I believe I found the correct answer](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rpgtyo89zyehv7bx73t0.png)

The coordinate is:
```
1135,1724
```

Remember, that represents the bottom-left of the square:
```
OOO
OOO
XOO
```

I want the coordinate of the top-left of the square:
```
XOO
OOO
OOO
```

That should be at:
```
1135, (1724 - 99)

1135, 1625
```

Which makes the possible correct answer:
```
11351625
```

- I type it in, press [Submit], and Viola!
- Correct answer!
- Two gold stars!

## Celebrating my accomplishments
- UPDATED: I solved both parts!
- I solved Part 1!
- I've now solved 9/10 Intcode computer puzzles!
- I made a GIF in attempts to identify a pattern to solve Part 2
- I feel like I discovered an applicable pattern for Part 2 through careful analysis of the tractor beam up to a 200x200 area

Bummer:
- I didn't build a simulator. It would have been impossible to do for Part 2, and it didn't seem worth it to make one for Part 1 since I made the GIF.

As intriguing and creative as these Intcode programs are, I'm ready to be done with them.

I know there's at least one more on Day 25.

There's been one every odd day since Day 5.

So, I can only presume there will be at least two more before Day 25.

Let's see what Day 20 has in store.