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


    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.

    Neil Smith

    Read more posts by this author.