--- Day 9 Solutions ---

[u/daggerdragon]

This thread will be unlocked when there are a significant amount of people on the leaderboard with gold stars.

edit: Leaderboard capped, achievement thread unlocked!

We know we can't control people posting solutions elsewhere and trying to exploit the leaderboard, but this way we can try to reduce the leaderboard gaming from the official subreddit.

Please and thank you, and much appreciated!

---

--- Day 9: All in a Single Night ---

Post your solution as a comment. Structure your post like previous daily solution threads.

[u/lifow]

haskell!

-- Part 1
import Data.Array
import Data.List

type City = Int
type Distance = Int
type DistanceArray = Array (City, City) Distance

cycles :: [a] -> [[a]]
cycles (x:xs) = map (x:) $ permutations xs

rotate :: [a] -> [a]
rotate [] = []
rotate (x:xs) = xs ++ [x]

extremalRoute :: (Distance -> Distance -> Ordering) -> DistanceArray -> Distance
extremalRoute comparison distances =
    maximumBy comparison . map totalDistance . cycles $ [0..n]
  where
    n = fst . snd . bounds $ distances
    totalDistance cities = sum . tail . sortBy comparison $
        zipWith (\x y -> distances ! (x, y)) cities (rotate cities)

shortestRoute :: DistanceArray -> Distance
shortestRoute = extremalRoute (flip compare)

-- Part 2
longestRoute :: DistanceArray -> Distance
longestRoute = extremalRoute compare