Day 11 was a much smaller problem than day 10's solution.

My first consequential decision was how to represent the map of galaxies. There are two main choices: the sparse representation, where I just record the points that matter (in a Set), and the densse representation, where I record every possible point (in an Array). As there were only a few points, and I was going to be expanding the bounds of the area, I decided on the sparse representation.

In this case,  the Galaxies are the Set of Positions.

type Position = V2 Int -- r, c

type Galaxies = S.Set Position

Reading the input is a case of going through the input position-by-position and recording a point if it's the right character.

mkGalaxies :: String -> Galaxies
mkGalaxies text = S.fromList [ V2 r c | r <- [0..maxR], c <- [0..maxC]
                                      , rows !! r !! c == '#'
                             ]
  where rows = lines text
        maxR = length rows - 1
        maxC = (length $ head rows) - 1

Expansion

Luckily, expanding the rows and columns is independent. I expand the rows first, then expand the columns on the result of that. I'll show only how to do the rows: the columns is exactly the same, only acting on columns not rows.

Building from the bottom up, I can find all the points on a row. A row is empty if it has no points, and I use that to find all the empty rows.

emptyRows :: Galaxies -> [Int]
emptyRows galaxies = [ r | r <- [0..r1] , S.null $ onRow galaxies r ]
  where r1 = S.findMax $ S.map (\(V2 r _) -> r) galaxies

onRow :: Galaxies -> Int -> Galaxies
onRow galaxies r = S.filter (\(V2 r' _) -> r == r') galaxies

I expand the rows by starting from the end of the list of empty rows. For each row I expand, I add the scale factor to all points below that row. This pattern of accumulating changes is another fold, this time a foldr to work from the end.

expandRows :: Galaxies -> [Int] -> Int -> Galaxies
expandRows galaxies expansions scale = foldr (shiftRows scale) galaxies expansions

shiftRows :: Int -> Int -> Galaxies -> Galaxies
shiftRows scale n galaxies = S.union small large'
  where (small, large) = S.partition (\(V2 r _) -> r < n) galaxies
        large' = S.map (^+^ (V2 (scale - 1) 0)) large

Note that the scale is the number rows that replace each empty row, so I add scale - 1 additional rows.

(I could possibly fiddle with these functions to parameterise them over the dimension I'm using, but I think it's fine for this small example and just two dimensions.)

Distances

The distance is just the Manhattan distance, the L1 norm. I find the distances between all pairs of points with two nested folds. The outer fold uses an accumulator of the processed points and the running-total distance. As a new point is brought in, the inner fold finds the distance from the new point to all the already-seen points.

distance :: Position -> Position -> Int
distance g1 g2 = abs dr + abs dc
  where (V2 dr dc) = g1 ^-^ g2

allDistances :: Galaxies -> Int
allDistances gs = snd $ S.foldl' addGalaxy (S.empty, 0) gs
  where addGalaxy (seen, d) new = 
            (S.insert new seen, S.foldl' (addDist new) d seen)
        addDist g1 d g2 = d + distance g1 g2

Solution

And that's it!

part1, part2 :: Galaxies -> Int
part1 = allDistances . expandGalaxies 2
part2 = allDistances . expandGalaxies 10e6

But I did get caught by an off-by-one error in the scale for a few minutes. Thanks, Eric, for the good examples!

Code

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