Thanks for sharing. Your input parser tells me I should consider learning TemplateHaskell one of these days – currently I write ad hoc parsers for each day.
Quite happy with the symmetric structure I ended up with.
north, south, east, west, cycle1 :: [String] -> [String]
north = transpose . map f . transpose
west = map f
south = transpose . map reverse . map f . map reverse . transpose
east = map reverse . map f . map reverse
f :: String -> String
f [] = []
f s = let (a, b) = span (/= '#') s
(c, d) = break (/= '#') b
in reverse (sort a) ++ c ++ f d
cycle1 = east . south . west . north
Runs okay-ish too, 0.6s, though I think that’s more to do with me not hashing solutions when detecting cycles for part 2.
That little parser DSL is my favorite thing in my solution library. I’ve done Advent of Code every year since it started in 2015, but it didn’t occur to me to build that until only a few years ago. I then went back and incorporated it into my past solution files.
Day 17 - 62 lines, 0.5 seconds
This was a lot of fun. I went through many iterations. After getting the correct
solution, I was still unhappy at the runtime - it took ~15 seconds when
optimized. I don’t use any library dependencies in my AOC solutions, so I
thought I’ll have to give in and implement a heap for storing the Dijkstra
priority queue.
I looked around for how to go about doing a heap in a purely functional manner, and came across this thing of beauty (still amortized O (log n)), by the venerable Tarjan himself apparently:
data Heap a = Empty | Heap a (Heap a) (Heap a)
union :: Ord a => Heap a -> Heap a -> Heap a
union h Empty = h
union Empty h = h
union hl@(Heap l ll lr) hr@(Heap r _ _)
| l <= r = Heap l (union lr hr) ll
| otherwise = union hr hl
extractMin :: Ord a => Heap a -> Maybe (a, Heap a)
extractMin Empty = Nothing
extractMin (Heap x l r) = Just (x, union l r)
(Runnable Haskell demoing this heap).This, and some other approaches, are described in a great article by Louis Wassermann in MonadReader Issue 16.
Also, I realized that the standard library Set already provides a O (log n)
minView. Anyways, all this tinkering with heaps etc, I was able to make things
faster, but not by much.
Finally, after reading through the other soultions, I figured out the trick was
not to use a fancier Dijkstra alternative like A* or optimize the heap
implementation, the trick was to reduce the search space.
From
((x, y), L|R|U|D, Int)
I was able to get to a much smaller
((x, y), Bool)
And now the search runs in a jiffy. I also did the solution in Swift, it is a bit more verbose at 109 lines, but runs in about the same time as the Haskell solution.
1 Like