# 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.