Advent of Code 2019 day 19

There are only two hard things in computer science: cache invalidations, naming things, and off-by-one errors.

After the challenge that was day 18, the day 19 task was a bit of light relief.

Part 1

I thought that Part 2 might require me to keep track of the beam's extents, so I decided to store the beam information as I went. I also assumed that the beam was the same rough shape as the examples: an expanding triangle of cells, with no gaps within it, and with the upper and lower margin y co-ordinates both non-decreasing as x increased.

To keep the maths easy, I decided to track, in each column, the y co-ordinate of the topmost point affected by the beam, and the y co-ordinate of the topmost point beneath the beam that wasn't affected. The number of affected points in that column was just the difference between these two. I could find the total number of points affected by finding the beam limits in all columns. Because the beam limits were always non-decreasing, I could start the search in each column at the same rows as the previous column. That implied I should do the search as a fold, and I could store the results in a Map.

I did start thinking about limiting the search area to just the top 50 rows, but guessed that part 2 would require exploring a larger area, and dealing with boundaries now would just complicate things too much.

My initial solution almost worked, but I didn't realise that the first couple of columns had no points affected, so that put off my previous-column tracking idea.

The tractorBeamAt function is a predicate that says if the beam is active at a point. beamInColumn sweeps down a column, looking for any cell where the beam is active. If it is active, it returns the first active row.

traceBeam then does a bit of fiddling around with previous values to find where to start scanning for the beam in this column.

type Bounds = (Integer, Integer) -- upper, lower
type Beam = M.Map Integer Bounds

traceBeam :: Machine -> Beam -> Integer -> Beam
traceBeam machine beam x = M.insert x (u', l') beam
    where (prevU, _prevL) = M.findWithDefault (0, 0) (x - 1) beam
          (bic, _foundU) = beamInColumn machine x
          u = head $ dropWhile (\y -> not $ tractorBeamAt machine x y) [prevU..]
          l = head $ dropWhile (\y -> tractorBeamAt machine x y) [u..]
          (u', l') = if prevU == 0 && bic == False
                       then (0, 0)
                       else (u, l)

tractorBeamAt :: Machine -> Integer -> Integer -> Bool
tractorBeamAt machine x y = (head output) == 1
    where (_, _, output) = runMachine [x, y] machine

beamInColumn :: Machine -> Integer -> (Bool, Integer)
beamInColumn machine x
    | null fromTop = (False, 0)
    | otherwise = (True, head fromTop)
    where fromTop = dropWhile (\y -> not $ tractorBeamAt machine x y) [0..maxY]

The overall solution is found by filtering the cells in the correct rows, and adding up how many there are.

part1 machine = sum $ map cellsInRange $ M.elems beamPresence
    where beamPresence = foldl' (traceBeam machine) M.empty xRange

cellsInRange :: Bounds -> Integer
cellsInRange (u, l) = l' - u'
    where u' = min u maxY
          l' = min l maxY

Part 2

This was about fitting a box in the beam. That meant I had to find the (x, y) co-ordinates of both the bottom-left and top-right of the box; call them \((x_b, y_b)\) and \((x_t, y_t)\) respectively. Therefore, I need to generate a stream of the x and y co-ordinates of the top and bottom of the beam.

This kind of "generate a stream of repeated applications" is a scan; it's like a fold but returns all the intermediate results. In this case, it's a scan over an infinite list of x values. (I could use iterate but I need explicit x values for the tractorBeamAt calls.)

Tracing the lower edge is done with traceLower (it finds the first unaffected cell below the beam, and returns that y - 1):

traceLower :: Machine -> (Integer, Integer) -> Integer -> (Integer, Integer)
traceLower machine (_, prev) x = (x, l')
    where (bic, foundU) = beamInColumn machine x
          startL = if prev == 0 then foundU else prev
          l = head $ dropWhile (\y -> tractorBeamAt machine x y) [startL..]
          l' = if prev == 0 && bic == False
               then 0
               else l - 1

and the stream of all \((x_b, y_b)\) values created with the scan:

lowers = scanl' (traceLower machine) (0, 0) xs

I know that \(x_t = x_b + 100\), so I don't need to thread the \(x_t\) value through the computation of the upper corner. I can instead generate the stream of upper y values and drop the first 99 of them. I can combine the \(y_t\) and \((x_b, y_b)\) values into the stream of corners then test if the y values are sufficiently different to accommodate the box.

part2 machine = score $ head $ dropWhile (not . containsBox) corners
    where uppers = scanl' (traceUpper machine) 0 xs
          lowers = scanl' (traceLower machine) (0, 0) xs
          corners = zip (drop ((fromIntegral boxSize) - 1) uppers) lowers
          xs = [0..] :: [Integer]

traceUpper :: Machine -> Integer -> Integer -> Integer
traceUpper machine prev x = u'
    where (bic, _foundU) = beamInColumn machine x
          u = head $ dropWhile (\y -> not $ tractorBeamAt machine x y) [prev..]
          u' = if prev == 0 && bic == False
               then 0
               else u

All that's left is the definition of containsBox and score:

containsBox (yt, (_xb, yb)) = yt + boxSize - 1 <= yb

score (yt, (xb, _yb)) = xb * 10000 + yt

Thanks

One thing I found very useful was the Intcode example-generator program written by /u/bjnord, which generated the patterns in the puzzle examples. That really helped me find all the off-by-one errors in my code!

Code

The complete code is available here, and on Github.