Haskell, part 2

I broke down the outline into a set of boxes by scanning over them.

type Box = (C, C) -- inclusive coordinates
makeBoxes :: [C] -> [Box]
makeBoxes cs =
    let cs' = sort cs -- left-to-right first, top-to-bottom second
        scanLines = cs' & groupOn fst
     in scanOver 0 [] scanLines
  where
    scanOver lastX currentYs [] = []
    scanOver lastX currentYs (new : rest) =
        let newX = new & head & fst
            closedBoxes = do
                [y1, y2] <- currentYs & chunksOf 2
                pure ((lastX, y1), (newX, y2))
            newYs =
                -- Take the new column and remove anything that
                -- corresponds to a y value that appears in both
                merge currentYs (map snd new)
         in -- Close the current boxes
            closedBoxes ++ scanOver newX newYs rest
    merge [] ns = ns
    merge ms [] = ms
    merge (m : ms) (n : ns)
        | m < n = m : merge ms (n : ns)
        | m > n = n : merge (m : ms) ns
        | otherwise = merge ms ns

The fiddly bit was handling all the cases for shape subtraction. I don’t give it here because it’s just a slog, but the gist is this:

type Shape = [Box]
subtractBox :: Box -> Box -> Shape -- returns whatever's left

subtractShape :: Shape -> Shape -> Shape -- this is just a fold.

The idea: take a bounding box that’s just large enough to cover all coordinates. From that, subtract the set of boxes above. You get a set of boxes that are in the “outside”, ie, illegal region. [I did it this way because managing shape subtraction from the set of “inside” boxes is just more work.]

Then for each candidate rectangle, if it overlaps with any of the “out-of-bounds” boxes, it’s not a solution.