Day 19: Tractor Beam
by Simon Berger
Links:
Today the puzzles were a little more relaxed. For the first part I just ran the intcode program for every possible position in the 50 by 50 area and counted the ones that are part of the beam. This was so easy that I wanted to solve it in a more interesting way. What I wanted was to model the beam as two linear equations (one for the upper and one for the lower bound) and then calculate the solutions for part 1 and 2 from that. I wrote a whole bunch of code like for a data structure representing fractions which is used by the other important structure, the linear equation, to represent its slope. The linear equation structure also had methods for calculating the area under it and all that good stuff. I spent more than 30 minutes perfecting these data structures only to find out that I couldn’t determine the slope such that the resulting equation fits all points of the beam.
I wish I could tell you where exactly I went wrong and what I should’ve done to fix it, but I couldn’t come up with a solution on the spot and I was pressed for time so I decided not to bother any longer and instead reverted back to the “simple” approach.
For the second part I then made the assumption that the beam is strictly non-contracting (i.e. it always expands or stays the same). Using this assumption I could then write an algorithm that efficiently follows the beam.
I used the following approach to determine whether the ship’s rectangle would fit in the beam at a given x position start_x
:
First, determine the x value end_x = start_x + width - 1
where width is the width of the ship’s rectangle (100). end_x
is the x value of the last “column” that’s part of the ship.
To find out whether the ship’s height is contained in the beam we have the determine the y positions of the start and end of the beam at both x values.
These values are called start_y_start
, start_y_end
for the first x value and end_y_start
, end_y_end
for the second.
We only really care about end_y_start
and start_y_end
though.
Here are the relevant values marked on an illustration:
start_x end_x
/ /
| |
v v end_y_start
#############....... /
#####OOOOOOOOOX.....<--
#####OOOOOOOOOO#....
#####OOOOOOOOOO###..
#####OOOOOOOOOO#####
.####OOOOOOOOOO#####
.####OOOOOOOOOO#####
..###OOOOOOOOOO#####
...##OOOOOOOOOO##### start_y_end
....#OOOOOOOOOO##### /
.....YOOOOOOOOO#####<--
......##############
As you can see these values describe the points X
(end_x
, end_y_start
) and Y
(start_x
, start_y_end
) which are the two corner points of the rectangle touching the edge of the beam.
The width of this rectangle is |end_x - start_x| + 1
and the height is |start_y_end - end_y_start| + 1
.
Our width is defined as 100 so we only have to check whether the height is at least 100.
If the height is less than 100 we move to the next x position.
I started by simply checking every x position in increasing order until one is found where the ship fits in the beam. Originally, I wanted to switch to a binary search to make it faster, but it turned out that just moving one step to the right is fast enough. Usually I would switch to the more efficient method if only for my consciousness, but because I wasted a lot of time on the linear equation approach I didn’t bother today.
tags: intcodeOverview
Previous day Next day