# 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 12 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.