4 January 2020 Tagged in: advent of code | haskell

Advent of Code 2019 day 19

There are only two hard things in computer science...

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.