2016 / 2017 / 2018 / 2019 / 2020 / 2021 / 2022 / 2023
Prompt / Code / Rendered / Standalone Reflection Page
This year's day 1 was definitely a little spicier than most! But Haskell's stream processing works well for us, again.
First let's get a nice utility function to make a number the first and last seen digit:
firstAndLast :: [Int] -> Int
firstAndLast xs = head xs * 10 + last xsAnd now we have to figure out how to extract the digits from each part. For
part 1, we need only to extract all of the isDigit characters:
extract1 :: String -> [Int]
extract1 = map digitToInt . filter isDigitFor part 2, it's a little bit trickier: we can look at each position and see if it is a new number string:
extract2 :: String -> [Int]
extract2 = mapMaybe isNumberString . tails
where
isNumberString :: String -> Maybe Int
isNumberString str = listToMaybe
[ d
| (numStr, d) <-
[ ("one",1), ("two",2), ("three",3)
, ("four",4), ("five",5), ("six",6)
, ("seven",7), ("eight",8), ("nine",9)
]
| numStr `isPrefixOf` str
]Note that tails is a function that takes "abc" and returns
["abc","bc","c"], allowing us to look at each position in order.
And that gives us the solutions:
day01 :: (String -> [Int]) -> String -> Int
day01 extractor = sum . map (sum . extractor) . lines
day01a = day01 extract1
day01b = day01 extract2>> Day 01a
benchmarking...
time 644.4 μs (634.7 μs .. 654.0 μs)
0.992 R² (0.985 R² .. 0.997 R²)
mean 636.6 μs (615.0 μs .. 658.1 μs)
std dev 72.70 μs (60.51 μs .. 86.91 μs)
variance introduced by outliers: 80% (severely inflated)
* parsing and formatting times excluded
>> Day 01b
benchmarking...
time 3.106 ms (3.086 ms .. 3.145 ms)
1.000 R² (0.999 R² .. 1.000 R²)
mean 3.094 ms (3.090 ms .. 3.105 ms)
std dev 22.59 μs (8.206 μs .. 41.38 μs)
* parsing and formatting times excluded
Prompt / Code / Rendered / Standalone Reflection Page
This one was definitely a bit too heavy on the parsing side heh. But maybe the
more interesting Haskell insight would be that we can use a nice data type --
V3 from the linear library (data V3 a = V3 a a a) to make the actual
solving logic very simple. I've always held that V2 and V3 are pretty much
some of the most useful non-standard data types for advent of code, and they
were pretty helpful today. They have the most convenient Num, Functor,
Applicative, Foldable, and Traversable instances!
If we encode each "set" as V3 <red> <green> <blue>, then the filters and
checksums become very simple.
For part 1, we need to see if all V3 Ints in a line are legal. We can
implement that as all isLegal:
isLegal :: V3 Int -> Bool
isLegal colorVec = and do
allowed <- V3 12 13 14
amount <- colorVec
pure (amount <= allowed)
It reads a little silly, but you just have to remember that and just checks
if every item is true, and here the do notation semantics are to compare each
allowed and amount point-wise, first the red-by-red, then the
green-by-green, and then the blue-by-blue.
Part 2 is a little simpler, we just need to aggregate the max per-color, and then find the product:
calcPower = product . foldr (liftA2 max) 0where liftA2 max (V3 x y z) (V3 a b c) = V3 (max x a) (max y b) (max z c),
and 0 for V3 is V3 0 0 0. And product works like how you'd think.
Going back to parsing, one neat way we can leverage V3 is with its Functor
instance:
-- [("red", 1), ("blue", 2), ("green", 6)] => V3 1 6 2
pairUp :: [(String, Int)] -> V3 Int
pairUp pairs = do
color <- V3 "red" "green" "blue"
pure $ fromMaybe 0 (lookup color pairs)
This performs an action per-color and fills in the spot with the result of
lookup, with 0 if the lookup fails.
>> Day 02a
benchmarking...
time 1.376 μs (1.373 μs .. 1.380 μs)
0.999 R² (0.998 R² .. 1.000 R²)
mean 1.388 μs (1.376 μs .. 1.435 μs)
std dev 75.81 ns (6.071 ns .. 160.5 ns)
variance introduced by outliers: 69% (severely inflated)
* parsing and formatting times excluded
>> Day 02b
benchmarking...
time 3.878 μs (3.678 μs .. 4.054 μs)
0.992 R² (0.988 R² .. 0.997 R²)
mean 3.808 μs (3.761 μs .. 3.861 μs)
std dev 173.2 ns (112.0 ns .. 256.3 ns)
variance introduced by outliers: 58% (severely inflated)
* parsing and formatting times excluded
Prompt / Code / Rendered / Standalone Reflection Page
Reflection not yet written -- please check back later!
>> Day 03a
benchmarking...
time 10.59 ms (10.40 ms .. 10.83 ms)
0.996 R² (0.991 R² .. 1.000 R²)
mean 10.49 ms (10.43 ms .. 10.73 ms)
std dev 291.4 μs (112.4 μs .. 559.0 μs)
* parsing and formatting times excluded
>> Day 03b
benchmarking...
time 7.405 ms (7.385 ms .. 7.423 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 7.420 ms (7.412 ms .. 7.432 ms)
std dev 26.68 μs (18.95 μs .. 40.49 μs)
* parsing and formatting times excluded
Prompt / Code / Rendered / Standalone Reflection Page
Reflection not yet written -- please check back later!
>> Day 04a
benchmarking...
time 170.3 μs (169.9 μs .. 170.6 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 169.8 μs (169.7 μs .. 170.0 μs)
std dev 485.7 ns (334.9 ns .. 807.0 ns)
* parsing and formatting times excluded
>> Day 04b
benchmarking...
time 315.3 μs (314.7 μs .. 316.1 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 314.8 μs (314.4 μs .. 315.2 μs)
std dev 1.252 μs (781.1 ns .. 1.957 μs)
* parsing and formatting times excluded
Prompt / Code / Rendered / Standalone Reflection Page
Another year and another puzzle where I feel like using Haskell's
data-interval is cheating :) It lets us work with ranged intervals and
gives us types like IntervalSet (a set of intervals) and IntervalMap
(mapping intervals to values), but with the correct implementations of map
intersection, set intersection, etc. that is aware of how intervals work. We
can generate a single Interval:
import Data.Interval (Interval)
import qualified Data.Interval as IV
fromRange :: Int -> Int -> Interval Int
fromRange x len = IV.Finite x IV.<=..< IV.Finite (x + len)The main type we will be using here is the IntervalMap type. We will use it
to map intervals to deltas: if you fall inside the interval, your value will
update by + delta.
import Data.IntervalMap.Strict (IntervalMap)
import qualified Data.IntervalMap.Strict as IVM
-- | Takes in the (a, b, c) triples that the problem gives map chunks
buildMap :: [(Int, Int, Int)] -> IntervalMap Int Int
buildMap = IVM.fromList
. map (\(dest, src, len) -> fromRange src len, dest - src)Now we can run it on a single point:
convertSingle :: Int -> IntervalMap Int Int -> Int
convertSingle x mp = case IVM.lookup x mp of
Nothing -> x -- the value is not in any known interval
Just delta -> x + delta -- that interval has the given deltaSo part 1 is simply finding the minimum after iterating convertSingle across
every range:
day05a :: [IntervalMap Int Int] -> [Int] -> Int
day05a imaps = minimum . map (\s0 -> foldl' convertSingle s0 imaps)Part 2 is where it gets interesting. We actually want to keep track of an
IntervalSet -- the set of all intervals that we have seeds at. We need to
write a function convertMany that takes an IntervalSet and runs that
interval set through an IntervalMap appropriately.
To do this, we find all of the "misses" (the intervals in the IntervalSet
that aren't mapped) and the "hits" (the intervals in the IntervalSet that do
exist in the map, shifted by the delta) and then recombine it:
import Data.IntervalSet (IntervalSet)
import qualified Data.IntervalSet as IVS
convertMany :: IntervalMap Int Int -> IntervalSet Int -> IntervalSet Int
convertMany mp xs = misses <> hits
where
-- dummy map corresponding to putting `()` at every interval in our
-- `IntervalSet`, needed because interval map functions require maps
tempMap :: IntervalMap Int ()
tempMap = IVM.fromList . map (,()) . IVS.toList $ xs
misses = IVM.keysSet $ tempMap `IVM.difference` mp
hits =
IVS.fromList
. map (\(iv, delta) -> IV.mapMonotonic (+ delta) iv)
. IVM.toList
$ IVM.intersectionWith const mp tempMapAnd run it all together with:
day05b :: IntervalSet Int -> [IntervalMap Int Int] -> IntervalSet Int
day05b = foldl' convertMany>> Day 05a
benchmarking...
time 17.13 μs (16.83 μs .. 17.86 μs)
0.997 R² (0.994 R² .. 1.000 R²)
mean 16.87 μs (16.80 μs .. 17.13 μs)
std dev 421.7 ns (78.33 ns .. 880.9 ns)
variance introduced by outliers: 26% (moderately inflated)
* parsing and formatting times excluded
>> Day 05b
benchmarking...
time 450.8 μs (450.1 μs .. 451.6 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 450.3 μs (450.0 μs .. 450.6 μs)
std dev 946.6 ns (694.4 ns .. 1.270 μs)
* parsing and formatting times excluded