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)] [sy..(sy + d)] ]
            topRight = [V2 x y | (x, y) <- zip [(sx + d), (sx + d - 1)] [sy..(sy + d)] ]
            bottomLeft = [V2 x y | (x, y) <- zip [(sx - d)] [sy, (sy - 1)..(sy - d)] ]
            bottomRight = [V2 x y | (x, y) <- zip [(sx + d), (sx + d - 1)] [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.


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

    Neil Smith

    Read more posts by this author.