day10.md

Day 10

all / 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

Available as an RSS Feed

Prompt / Code / Rendered

Today is another day where the "automatically build a memoized recursive map" in Haskell really shines :) It's essentially the same problem as Day 7.

For the first part, once you sort the list, you can compute the differences and then build a frequency map

-- | Build a frequency map
freqs :: Ord a => [a] -> Map a Int
freqs = M.fromListWith (+) . map (,1) . toList

diffs :: [Int] -> [Int]
diffs xs@(_:ys) = zipWith (-) ys xs

ghci> diffs [1,3,4,7]
[2,1,3]

And so part 1 can be done with:

part1 :: [Int] -> Int
part1 xs = (stepFreqs M.! 1) * (stepFreqs M.! 3)
  where
    xs' = 0 : xs ++ [maximum xs + 3]
    stepFreqs = freqs (diffs (sort xs'))

For part 2, if we get an IntSet of all of your numbers (and adding the zero, and the goal, the maximum + 3), then we can use it to build our IntMap of all the number of paths from a given number.

import           Data.IntMap (IntMap)
import           Data.IntSet (IntSet)
import qualified Data.IntMap as IM
import qualified Data.IntSet as IS

-- | A map of numbers to the count of how many paths from that number to
-- the goal
pathsToGoal :: IntSet -> IntMap Int
pathsToGoal xs = res
  where
    res = flip IM.fromSet xs $ \i ->
      if i == goal
        then 1
        else sum [ IM.findWithDefault 0 (i + j) res
                 | j <- [1,2,3]
                 ]
    goal = IS.findMax is

Our answer is res, the map of numbers to the count of how many paths exist from that number to the goal. To generate the count for a given number i, we add the number of paths from i+1, i+2, and i+3. We get that count by looking it up in res!

part2 :: [Int] -> Int
part2 xs = pathsToGoal xs IM.! 0
  where
    xs' = IS.fromList (0 : xs ++ [maximum xs + 3])

A quick note --- after some discussion on the irc, we did find a closed-form solution...I might be editing this to implement it in Haskell eventually :)

Back to all reflections for 2020

Day 10 Benchmarks

>> Day 10a
benchmarking...
time                 6.240 μs   (6.090 μs .. 6.639 μs)
                     0.985 R²   (0.964 R² .. 0.999 R²)
mean                 6.843 μs   (6.274 μs .. 7.805 μs)
std dev              2.589 μs   (1.164 μs .. 3.977 μs)
variance introduced by outliers: 99% (severely inflated)

* parsing and formatting times excluded

>> Day 10b
benchmarking...
time                 9.300 μs   (8.801 μs .. 10.10 μs)
                     0.979 R²   (0.961 R² .. 1.000 R²)
mean                 9.003 μs   (8.778 μs .. 9.453 μs)
std dev              1.001 μs   (176.6 ns .. 1.635 μs)
variance introduced by outliers: 89% (severely inflated)

* parsing and formatting times excluded