{-# Language NumericUnderscores, ImportQualifiedPost #-}
{-|
Module      : Main
Description : Day 11 solution
Copyright   : (c) Eric Mertens, 2023
License     : ISC
Maintainer  : emertens@gmail.com

<https://adventofcode.com/2023/day/11>

We're given a map of galaxies and need to find the
sum of all distances between the pairs of galaxies.
The twist is that empty rows and columns are expanded.

We can simplify this problem by solving the X and Y
axes separately. We can collapse the input down to
a count of how many galaxies exist at each location
on a single axis.

>>> :{
:main +
"...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....
"
:}
374
82000210

-}
module Main (main) where

import Advent (getInputLines, counts)
import Advent.Coord (Coord(C), coordLines)
import Data.List (tails)
import Data.Map qualified as Map

-- | Parse the input map and print out the answers to both parts.
--
-- >>> :main
-- 9965032
-- 550358864332
main :: IO ()
IO ()
main =
 do input <- Int -> Int -> IO [String]
getInputLines Int
2023 Int
11
    let (rows, cols) = unzip [(y, x) | (C y x, '#') <- coordLines input]
        (r1, rWide) = solve1 rows
        (c1, cWide) = solve1 cols
        solve Int
n = Int
r1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
c1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ (Int
rWide Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
cWide) Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
n
    print (solve         2)
    print (solve 1_000_000)

-- | Solve the travel problem along a single axis.
-- The result is how many normal steps and how many
-- expanded steps were taken.
solve1 ::
  [Int]     {- ^ galaxy positions               -} ->
  (Int,Int) {- ^ regular and expanded distances -}
solve1 :: [Int] -> (Int, Int)
solve1 [Int]
galaxies = ([Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [Int]
crossings, [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum ((Int -> Int -> Int) -> [Int] -> [Int] -> [Int]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Int -> Int -> Int
forall a. Num a => a -> a -> a
(*) [Int]
crossings [Int]
gaps))
  where
    counted :: Map Int Int
counted = [Int] -> Map Int Int
forall (f :: * -> *) a. (Foldable f, Ord a) => f a -> Map a Int
counts [Int]
galaxies
    total :: Int
total   = Map Int Int -> Int
forall a. Num a => Map Int a -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum Map Int Int
counted

    -- empty space between locations containing galaxies
    gaps :: [Int]
gaps = [Int
x2 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
x1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 | Int
x1 : Int
x2 : [Int]
_ <- [Int] -> [[Int]]
forall a. [a] -> [[a]]
tails (Map Int Int -> [Int]
forall k a. Map k a -> [k]
Map.keys Map Int Int
counted)]

    -- number of unique pairs of galaxies on left and right side of a gap
    crossings :: [Int]
crossings = [Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
* (Int
total Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
n) | Int
n <- (Int -> Int -> Int) -> [Int] -> [Int]
forall a. (a -> a -> a) -> [a] -> [a]
scanl1 Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) (Map Int Int -> [Int]
forall k a. Map k a -> [a]
Map.elems Map Int Int
counted)]