AoC 2019 D19: Tractor Beam
| Problem statement | Source code | Tags: IntcodeGeometry
← Previous Back to AoC Index Next →
This problem is essentially a "oracle" problem, where the program tells us whether a given coordinate has a beam.
Part 1
We just enumerate over the 50x50 grid, running the Intcode program for each coordinate (x, y), and counting the coordinates for which the program outputs 1 .
Part 2
The beam looks like this:
Roughly speaking, there's a lower edge and an upper edge, both linear. The first step is to find the equations of these edges. This is a very imprecise process; I took all samples in the x=10..50 range, and found the max/min slopes from the origin to these points (as y / x). To account for errors, I round up/down to 3 decimal places for the max/min slopes. The resulting slopes are approximately 0.481 (lower edge) and 0.578 (upper edge).
A square can be contained in this triangular region at a position if and only if the square's northwest and southeast corners are both contained the beam edges (flip the diagram above along the x axis so the y axis points upwards). So the optimal placement is to have the corners touch the edges. If the square has side length s, and its southwest corner is at (x, y), then the two corners are at (x + s, y) and (x, y + s). Thus we have the system of equations:
This gives , (the real answer is , which isn't too far). If we blindly brute force our way there, we would have checked 1.2 million coordinates, which is too much. Instead, equipped with the knowledge of how to estimate the intersection points, we only need the oracle to fine-adjust the coordinates. Since the square's northwest-southeast diagonal lies on the line x + y = c, we enumerate over c values. For each c, we can compute the intersection of the line x + y = c with the lower and upper beam edges. If we floor the smaller x coordinate and ceil the larger one, we get a range to search for the actual intersection points. We then just run the oracle on each point (x, c - x) in this range starting from x_min and x_max respectively, until we find the first points that are inside the beam. The real answers should be fairly close to the estimates since we only allow errors up to rounding. If the distance between these two points is 100, we have found a valid placement for the square, and this is the smallest c that works, hence the closest to the origin.