Creating, using, and merging branches
There are only two hard things in computer science: cache invalidations, naming things, and off-by-one errors.
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
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.
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
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
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 (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!