Marketing Pitch and Impressions#

Why Haskell?

  • A new paradigm
  • Composition and predictability
  • Declarative
  • Performance
  • Abstraction
  • Excellent tooling

— haskell.org (abridged)

I started with Swift, but I couldn’t resist rewriting the solution in Haskell. This problem is practically tailor-made to showcase the benefits of non-strict evaluation.

Visual Studio Code support for Haskell is excellent.

The Code#

We define a map memo, populated with all possible nodes and flag values. The values in memo are unevaluated calls to count. count is then defined to look up the values it needs in memo.

Assuming we don’t have any cycles in the graph, this will eventually terminate.

The lazy evaluation in Haskell means that while this looks a bit like top-down dynamic programming, it is a bottom up strategy as the entire (unevaluated) solution space is constructed up front, and then just the relevant parts evaluated for the solutions we need.

Both part 1 and part 2 are evaluated using the same code, just modifying the start node and flags to suit.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import Data.Bits ((.|.))
import Data.Map (Map, findWithDefault, fromList, keys, (!))

solve :: Map String [String] -> String -> Int -> Int
solve gr startNode startFlags = result
  where
    memo = fromList [((n, f), count n f) | n <- "out" : keys gr, f <- [0 .. 3]]
    count "out" f = f `div` 3
    count node f =
      let dacFlag = fromEnum (node == "dac")
          fftFlag = fromEnum (node == "fft") * 2
          nextFlags = f .|. dacFlag .|. fftFlag
          neighbors = findWithDefault [] node gr
       in sum [memo ! (neighbor, nextFlags) | neighbor <- neighbors]
    result = memo ! (startNode, startFlags)

main :: IO ()
main = do
  content <- readFile "y25d11.txt"
  let graph = fromList [
                (k, words $ drop 1 v)
                | line <- lines content, let (k, v) = break (== ':') line
              ]
  putStrLn $ "Result1: " ++ show (solve graph "you" 3)
  putStrLn $ "Result2: " ++ show (solve graph "svr" 0)

Install GHC and run#

The recommended way to install Haskell is via GHCup, but your package manager probably has installable packages.

# I installed from Homebrew
brew install ghc

# haskell.org recommends using GHCup
curl --proto '=https' --tlsv1.2 -sSf https://get-ghcup.haskell.org | sh

# Execute the code
runhaskell d11.hs