January 04, 2020
in
#advent of code
#haskell

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.

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
```

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
```

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!

The complete code is available here, and on Github.