Advent of Code 2022 day 15

Day 15 was some clever tricks with representing data by functions, and then representing those functions as data.

Regions as functions

The field of possible locations is far too large to represent explicitly. But all I need to do is determine whether a beacon could be hidden in a particular location. That's a function of Position -> Bool. Therefore, I decided to represent all the regions as functions, with the newtype Region.

newtype Region = Region { getRegion :: Position -> Bool }

A Region contains the function I need: a Region defines the area where there cannot be a beacon. getRegion allows be to extract that function from the Region so I can use it.

A bit of preamble, to set up positions and find the distances between points.

type Position = V2 Int

manhattan :: Position -> Position -> Int
manhattan p1 p2 = (abs dx) + (abs dy)
  where V2 dx dy = p1 ^-^ p2

The nearby function creates a Region for a Sensor. The Region contains a function that determines if a point is within the "forbidden zone" of a sensor.

nearby :: Sensor -> Region
nearby (Sensor s b) = Region (\p -> manhattan s p <= dist)
  where dist = manhattan s b

But now, to find how sensors and their regions overlap.

Combining regions

Haskell has some standard machinery for combining things: semigroups and monoids. The semigroup defines how to combine two (or more) things, and the monoid shows what happens with no thing.

I want to combine regions, so I define instances for semigroup and monoid. When regions r1 and r2 overlap, a point is forbidden if it's in r1 or r2. If there are no regions, points are never forbidden.

instance Semigroup Region where
  r1 <> r2 = Region (\p -> getRegion r1 p || getRegion r2 p)

instance Monoid Region where
  mempty = Region (\p -> False)

mconcat combines a list of things in a monoid. I use that to find the entire forbidden region, the coverage of the sensors:

coverage = mconcat $ fmap nearby sensors

A point is forbidden if it is within the coverage. I can ask about a particular point with the function call getRegion coverage point, and the result shows me if that point is in the overall forbidden zone.

Part 1

In part 1, I need to count the number of forbidden points on a particular row. First, I need to find the range of possible points to consider, which ranges from the leftmost forbidden x value to the rightmost forbidden x value.

minX, maxX :: Sensor -> Int
minX (Sensor s@(V2 sx _) b) = sx - (manhattan s b)
maxX (Sensor s@(V2 sx _) b) = sx + (manhattan s b)

globalMinX, globalMaxX :: [Sensor] -> Int
globalMinX = minimum . fmap minX
globalMaxX = maximum . fmap maxX

From that, I can use the range function from Data.Ix to identify all the possibly-forbidden points on the row of interest, remembering to remove the points that are occupied by sensors and beacons!

thisY :: Int
-- thisY = 10
thisY = 2000000

part1 sensors = length $ filter (\p -> p `notElem` occupied) $ filter (getRegion coverage) rowCoords
  where coverage = mconcat $ fmap nearby sensors
        rowCoords = range ((V2 (globalMinX sensors) thisY), (V2 (globalMaxX sensors) thisY))
        occupied = concatMap (\(Sensor s b) -> [s, b]) sensors

Part 2

The direct way to do this is to something similar to part 1, but rather than working on a particular row I should test every point in the search range.

But there are 4,000,000 × 4,000,000 points, and checking 16 × 10 ¹² points takes a long time. On the other hand, the nature of the problem indicates that there only one such non-forbidden point, so it must lie just outside the boundary of at least one sensor.

That means I need to find the points that are just outside the forbidden zone of one sensor, which involves a bit of faffing with Enum ranges to get the points.

justOutside :: Sensor -> S.Set Position
justOutside (Sensor s@(V2 sx sy) b) = S.fromList (topLeft ++ topRight ++ bottomLeft ++ bottomRight)
  where d = 1 + manhattan s b
        topLeft = [V2 x y | (x, y) <- zip [(sx - d)..sx] [sy..(sy + d)] ]
        topRight = [V2 x y | (x, y) <- zip [(sx + d), (sx + d - 1)..sx] [sy..(sy + d)] ]
        bottomLeft = [V2 x y | (x, y) <- zip [(sx - d)..sx] [sy, (sy - 1)..(sy - d)] ]
        bottomRight = [V2 x y | (x, y) <- zip [(sx + d), (sx + d - 1)..sx] [sy, (sy - 1)..(sy - d)] ]

Combining these for all the sensors, and filtering to be within the given zone, gives about 4.9 million points to search, about one-four-millionth of the size of the entire search region.

searchRange :: (Position, Position)
-- searchRange = ((V2 0 0), (V2 20 20))
searchRange = ((V2 0 0), (V2 4000000 4000000))

part2 sensors = x * 4000000 + y
  where coverage = mconcat $ fmap nearby sensors
        boundaries = S.filter (inRange searchRange) $ S.unions $ fmap justOutside sensors
        V2 x y = S.findMin $ S.filter (\p -> not $ getRegion coverage p) boundaries

It still takes about three minutes on my machine, but it doesn't seem to use multiple cores. But anyway, there's no real optimisation here.

Code

You can get the code from my locally-hosted Git repo, or from Gitlab.