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.