Module day19 

Tractor Beam

The intcode program computes a linear inequality: returning true if an integer point lies on or between two lines through the origin, often with irrational slope. The intcode program was designed so that the two lines are close enough that there are no integer solutions when y=1, so there are intentionally one or two discontinuities between the origin and the bulk of the beam. This solution finds the approximate boundary of the upper and lower edges of the beam expressed as an integer ratio for slope. We then skip the relatively expensive intcode test if the x and y coordinates lie outside. Once we identify an edge past the initial discontinuities, scaling along the lines buys more accuracy and thus fewer later intcode runs.

For part 2, we can further speed up the process by using geometry to hone in on a viable target to start searching at. Our target point (x,y) is related to our two slopes as:

  scale*y = upper*(x+99)
  scale*x = lower*(y+99)

Those two equations can be represented in matrix form:

  [upper-scale][x] = [-99*upper]
  [scale-lower][y] = [ 99*lower]

where inverting the matrix gives a solution:

  determinant = scale * scale - lower * upper
  x = 99 * (lower * upper + lower * scale) / determinant
  y = 99 * (lower * upper + upper * scale) / determinant

Structs

Input

Functions

inside 🔒

Skip the relatively expensive intcode test if the point lies outside the beam’s slopes. The slope check has some false positives but no false negatives.

parse

part1

part2

test 🔒

Definitive but slower check.