TheLazy.Dev
Portfolio GitHub

Blog

adventofcode |algorithms |computerscience |programming

Tractor Beam

rmion

Robert Mion

Posted on May 19, 2022

Tractor Beam

Advent of Code 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

No example input given

Instead, as in recent Intcode puzzles, example output is offered:

       X
  0->      9
 0#.........
 |.#........
 v..##......
  ...###....
  ....###...
Y .....####.
  ......####
  ......####
  .......###
 9........##
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Generating a picture of the tractor beam's pull

  • I confirmed the output contained 1s and 0s
  • 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
Enter fullscreen mode Exit fullscreen mode

The result is this depiction of the tractor beam
The tractor beam visualized

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

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

When the loop finishes, points contains:

[ 1141, 1637 ]
Enter fullscreen mode Exit fullscreen mode

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

11411637
Enter fullscreen mode Exit fullscreen mode

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:

..........................####....................
...........................####...................
...........................#####..................
............................####..................
.............................####.................
.............................#####................
..............................#####...............
...............................####...............
...............................#####..............
................................#####.............
.................................#####............
Enter fullscreen mode Exit fullscreen mode

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?

.................................*    ............
Enter fullscreen mode Exit fullscreen mode

I then run my Intcode program on three coordinates:

.................................*    ............
.................................123..............
Enter fullscreen mode Exit fullscreen mode

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]
....#####....
....######...
Enter fullscreen mode Exit fullscreen mode

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#####
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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

[0,0,0]
Enter fullscreen mode Exit fullscreen mode

Eventually, I see this exclusively:

[1,0,1]
Enter fullscreen mode Exit fullscreen mode

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

[1,1,1]
Enter fullscreen mode Exit fullscreen mode

At last, I spot it!
The moment I believe I found the correct answer

The coordinate is:

1135,1724
Enter fullscreen mode Exit fullscreen mode

Remember, that represents the bottom-left of the square:

OOO
OOO
XOO
Enter fullscreen mode Exit fullscreen mode

I want the coordinate of the top-left of the square:

XOO
OOO
OOO
Enter fullscreen mode Exit fullscreen mode

That should be at:

1135, (1724 - 99)

1135, 1625
Enter fullscreen mode Exit fullscreen mode

Which makes the possible correct answer:

11351625
Enter fullscreen mode Exit fullscreen mode
  • 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.

💖 💪 🙅 🚩
rmion
Robert Mion

Posted on May 19, 2022

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Grid Computing
adventofcode Grid Computing

August 15, 2022

Timing is Everything
adventofcode Timing is Everything

August 22, 2022

Two Steps Forward
adventofcode Two Steps Forward

August 21, 2022

Radioisotope Thermoelectric Generators
adventofcode Radioisotope Thermoelectric Generators

August 11, 2022

Stream Processing
adventofcode Stream Processing

August 3, 2022