Day 9 was the first day that took both significant effort to develop a solution, and significant time for it to run.

Part 1

We're given a set of co-ordinates (as x, y pairs) of red tiles in a theatre, like this:

7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3

That produces a grid that looks like this:

..............
.......#...#..
..............
..#....#......
..............
..#......#....
..............
.........#.#..
..............

(with the origin at the top left of the diagram, x increasing to the right, y increasing down).

The challenge is to pick two tiles, call them the diagonally opposite corners of a rectangle, and find the area (number of tiles) enclosed.

That was almost trivial to find. I find all the rectangles with a list comprehension, and there's a simple function to find the area of a rectangle.

part1 :: [Position] -> Int
part1 tiles = maximum $ fmap rectangleArea $ allRectangles tiles

allRectangles :: [Position] -> [(Position, Position)]
allRectangles tiles = rectangles
  where rectangles = [(a, b) | a <- tiles, b <- tiles
                             , a < b
                             ]
 
rectangleArea :: (Position, Position) -> Int
rectangleArea (a, b) = ((abs dr) + 1) * ((abs dc) + 1)
  where V2 dr dc = a ^-^ b

Part 2

The challenge comes in part 2. Now, the given red tiles are connected by lines of green tiles, forming a loop. (And the interior of the loop is green, but I don't use that fact.)

..............
.......#XXX#..
.......X...X..
..#XXXX#...X..
..X........X..
..#XXXXXX#.X..
.........X.X..
.........#X#..
..............

I still need to find the largest rectangle, but the rectangle is only valid if all tiles within it are within the enclosed area.

That took a while to think about how to solve. The obvious solution is to have a collection of all the tiles that could be used (e.g. a Set of tiles), and check that all tiles within a candidate rectangle are filled. However, the coordinates go up to about 10⁵, so there will be about 1o¹⁰ usable tiles. That's too large.

Instead, I made a couple of assumptions. The first is that the path is non-intersecting. The second is that the best rectangle will have some height and width, so I don't have to deal with the degenerate case of the "rectangle" being a line of tiles.

However, I was fairly certain the shape would be concave, so I had to deal with that.

Given that the overall perimeter of the valid tiles is non-intersecting, a rectangle will be invalid if one the boundary edges penetrates the wall of the rectangle. For instance, the rectangle formed from O characters in the diagram below is invalid, because the boundary wall penetrates the rectangle's left and bottom edges.

..............
.......#XXX#..
.......X...X..
..#XXXX#OOOO..
..X....O...O..
..#XXXXOX#.O..
.......O.X.O..
.......OOOO#..
..............

A simplification of this test is to see if any of the boundary tiles are within the rectangle.

The other test is that an arbitrary point in the rectangle is inside the boundary. That allows me to rule out rectangles like the one below, where no walls penetrate the rectangle, but it's outside the boundary.

..............
..OOOOO#XXX#..
..O....O...X..
..#OOOO#...X..
..X........X..
..#XXXXXX#.X..
.........X.X..
.........#X#..
..............

That means I need to store the boundary tiles somewhere. Luckily, there are only about 600,000 of them, so that's feasible to store in a Map going from Position to Colour of the tile.

data Colour = Red | Green deriving (Show, Eq)

type Theatre = M.Map Position Colour
mkTheatre :: [Position] -> Theatre
mkTheatre redTiles = theatre1
  where theatre0 = M.fromList $ zip redTiles $ repeat Red
        edges = zip redTiles ((tail redTiles) ++ redTiles)
        theatre1 = foldl' fillEdge theatre0 edges

fillEdge :: Theatre -> (Position, Position) -> Theatre
fillEdge theatre ends = M.union theatre $ findEdge ends

findEdge :: (Position, Position) -> Theatre
findEdge (V2 x1 y1, V2 x2 y2)
  | x1 == x2 = M.fromList [(V2 x1 y, Green) | y <- [ yMin .. yMax ] ]
  | y1 == y2 = M.fromList [(V2 x y1, Green) | x <- [ xMin .. xMax ] ]
  | otherwise = M.empty
  where yMin = min y1 y2
        yMax = max y1 y2
        xMin = min x1 x2
        xMax = max x1 x2

I can now test if a given rectangle is valid. There are three conditions: it's fat (i.e. not a single line of tiles), it's empty within, and a point in the rectangle is inside the perimeter.

validRectangle :: Theatre -> Position -> Position -> Bool
validRectangle theatre (V2 x1 y1) (V2 x2 y2) = isFat && isEmptyWithin && isInside
  where isFat = x1 /= x2 && y1 /= y2
        topLeft = V2 (min x1 x2) (min y1 y2)
        bottomRight = V2 (max x1 x2) (max y1 y2)
        bounds = (topLeft ^+^ DR, bottomRight ^+^ UL)
        greenWithin = M.filterWithKey (\p _ -> inRange bounds p) theatre
        isEmptyWithin = M.null greenWithin
        testPoint = bottomRight ^+^ UL
        isInside = pointInside theatre testPoint

The bounds for the emptiness check are just inside the corners, to account for the existing boundary tiles that are adjacent to the red tiles chosen.

Testing if a point is inside is something I had to look up. The ray-casting algorithm is good enough for this. I always start at the bottom right of the rectangle and project it to the right. A point is inside if it crosses the boundary an odd number of times on its way off the right edge of the theatre.

The logic in rayTraceStep is a bit complex to deal with cases of meeting and following a horizontal boundary. The basic idea is to track the current position and the the number of crossings. If the current position is not in the theatre, move to the next position. If it is, and is a green tile, that means we're crossing a vertical wall, so increment the number of crossings.

The complexity comes if we meet a red tile. That means the next little bit will be the green tiles of the boundary section for this tile. Meeting those doesn't necessarily mean crossing a boundary. If the vertical green boundaries are either both above or both below, I've not crossed a boundary; they they're one above or one below, I have. That means I need to track the last-seen tile colour, and the last-seen vertical boundary direction.

    .........    ......X..
    .........    ......X..
--> ..#XXX#..    ..#XXX#..
    ..X...X..    ..X......
    ..X...X..    ..X......

That gives the full implementation below.

pointInside :: Theatre -> Position -> Bool
pointInside theatre here = (rayTrace theatre testPoint) `mod` 2 == 1
  where testPoint0 = here ^+^ UL
        testPoint = head $ dropWhile (\p -> M.member p theatre) $ iterate (^+^ UL) here

rayTrace :: Theatre -> Position -> Int
rayTrace theatre here = n
  where maxX = maximum $ fmap xOf $ M.keys theatre 
        xOf (V2 x _) = x
        (_, _, _, n) = head $ dropWhile (\(h, _, _, _) -> xOf h <= maxX) $ iterate (rayTraceStep theatre) (here, Green, WallBelow, 0)

rayTraceStep :: Theatre -> (Position, Colour, WallDirection, Int) -> (Position, Colour, WallDirection, Int)
rayTraceStep theatre (here, colour, wallDirection, crossings) 
  | tile == (Just Green) && colour == Green = (there, Green, wallDirection, crossings + 1) -- crossing a vertical green wall
  | tile == (Just Red) && colour == Green = (there, Red, newWallDirection, crossings + 1) -- encountering a horizontal wall
  | tile == (Just Green) && colour == Red = (there, Red, wallDirection, crossings)  -- continuing along a horizontal wall
  | tile == (Just Red) && colour == Red = (there, Green, WallBelow, crossings + delta)  -- leaving a horizontal wall
  | tile == Nothing = (there, colour, wallDirection, crossings)
  where tile = M.lookup here theatre
        there = here ^+^ R
        tileAbove = M.member (here ^+^ U) theatre
        tileBelow = M.member (here ^+^ D) theatre
        newWallDirection = if tileAbove then WallAbove else WallBelow
        delta = if wallDirection == newWallDirection then 1 else 0

The good news is, this gave the correct answer at the first attempt!

The bad news is, this took just over 20 minutes to run. That means there's plenty of scope for optimisation, but that's something to come back to.

Future optimisation

As a note for self, there are two things I could look at for optimising this. One is coordinate compression, where I don't have the full range of the theatre, but instead keep track of the ranked coordinates. That would give a theatre of about 250-tiles-square.

The other is to consider the Sutherland-Hodgman algorithm for detecting if boundary tiles are within the rectangle I'm testing.

Addendum

I've done the optimisation, using coordinate compression. It dropped the runtime down to 1.6 seconds, about a 750-fold speedup.

Code

You can get the code from Codeberg.