From a7dff77048ed6fb039a3c9c852759a79d47891b7 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Tue, 24 Dec 2024 13:36:11 +0000 Subject: [PATCH] Done day 22 --- advent22/Main.hs | 66 ++++++++++++++++++++++++++++++++++++++ advent22/MainBruteForce.hs | 64 ++++++++++++++++++++++++++++++++++++ adventofcode24.cabal | 9 ++++++ 3 files changed, 139 insertions(+) create mode 100644 advent22/Main.hs create mode 100644 advent22/MainBruteForce.hs diff --git a/advent22/Main.hs b/advent22/Main.hs new file mode 100644 index 0000000..39657a1 --- /dev/null +++ b/advent22/Main.hs @@ -0,0 +1,66 @@ +-- Writeup at https://work.njae.me.uk/2024/12/24/advent-of-code-2024-day-21/ +import AoC + +import Data.Bits +import Data.List +import Data.List.Split +import qualified Data.IntMap.Strict as M + +type Prices = M.IntMap Int + +main :: IO () +main = + do dataFileName <- getDataFileName + text <- readFile dataFileName + let codes = fmap read $ lines text + -- print codes + -- print $ fmap (followingSecret 2000) codes + print $ part1 codes + print $ part2 codes + +part1 :: [Int] -> Int +part1 codes = sum $ fmap (followingSecret 2000) codes + +part2 codes = maximum $ M.elems mergedPriceValues + where allPrices = fmap salePrices codes + allPriceValues = fmap windowsAndPrices allPrices + mergedPriceValues = M.unionsWith (+) allPriceValues + +nextSecret, step1, step2, step3, prune :: Int -> Int +nextSecret = step3 . step2 . step1 +step1 n = prune $ (n * 64) `mix` n +step2 n = prune $ (n `div` 32) `mix` n +step3 n = prune $ (n * 2048) `mix` n +prune n = n `mod` 16777216 + +mix :: Int -> Int -> Int +mix s n = s `xor` n + +followingSecret :: Int -> Int -> Int +followingSecret n s = (!! n) $ iterate nextSecret s + +salePrices :: Int -> [Int] +salePrices s = take 2001 $ fmap (`mod` 10) $ iterate nextSecret s + +priceChanges :: [Int] -> [Int] +priceChanges ps = zipWith (-) (tail ps) ps + +windows :: [Int] -> [Int] +windows = fmap encode . divvy 4 1 + +encode :: [Int] -> Int +encode xs = foldl' (\a n -> a * 20 + n) 0 xs + +windowsAndPrices :: [Int] -> Prices +windowsAndPrices ps = foldl' (\m (w, p) -> M.insertWith (flip const) w p m) M.empty wPs + where cs = priceChanges ps + wPs = zip (windows cs) (drop 4 ps) + + +possibleWindows :: [[Int]] +possibleWindows = [ [a, b, c, d] + | a <- [-9..9] + , b <- [-9..9] + , c <- [-9..9] + , d <- [-9..9] + ] diff --git a/advent22/MainBruteForce.hs b/advent22/MainBruteForce.hs new file mode 100644 index 0000000..53156da --- /dev/null +++ b/advent22/MainBruteForce.hs @@ -0,0 +1,64 @@ +-- Writeup at https://work.njae.me.uk/2024/12/24/advent-of-code-2024-day-21/ +import AoC + +import Data.Bits +import Data.List.Split + +main :: IO () +main = + do dataFileName <- getDataFileName + text <- readFile dataFileName + let codes = fmap read $ lines text + -- print codes + -- print $ fmap (followingSecret 2000) codes + print $ part1 codes + print $ part2 codes + +part1 :: [Int] -> Int +part1 codes = sum $ fmap (followingSecret 2000) codes + +part2 codes = maximum $ fmap valueOfWindow allWindows + where allPrices = fmap salePrices codes + allWindows = possibleWindows + valueOfWindow w = sum $ fmap (valueGivenWindow w) allPrices + +nextSecret, step1, step2, step3, prune :: Int -> Int +nextSecret = step3 . step2 . step1 +step1 n = prune $ (n * 64) `mix` n +step2 n = prune $ (n `div` 32) `mix` n +step3 n = prune $ (n * 2048) `mix` n +prune n = n `mod` 16777216 + +mix :: Int -> Int -> Int +mix s n = s `xor` n + +followingSecret :: Int -> Int -> Int +followingSecret n s = (!! n) $ iterate nextSecret s + +salePrices :: Int -> [Int] +salePrices s = take 2001 $ fmap (`mod` 10) $ iterate nextSecret s + +priceChanges :: [Int] -> [Int] +priceChanges ps = zipWith (-) (tail ps) ps + +windows :: [Int] -> [[Int]] +windows = divvy 4 1 + +pricesAndWindows :: [Int] -> [(Int, [Int])] +pricesAndWindows ps = zip (drop 4 ps) $ windows cs + where cs = priceChanges ps + +valueGivenWindow :: [Int] -> [Int] -> Int +valueGivenWindow window ps + | null foundPrices = 0 + | otherwise = fst $ head foundPrices + where vCs = pricesAndWindows ps + foundPrices = dropWhile (\(p, w) -> w /= window) vCs + +possibleWindows :: [[Int]] +possibleWindows = [ [a, b, c, d] + | a <- [-9..9] + , b <- [-9..9] + , c <- [-9..9] + , d <- [-9..9] + ] diff --git a/adventofcode24.cabal b/adventofcode24.cabal index 57ca291..35c9ac6 100644 --- a/adventofcode24.cabal +++ b/adventofcode24.cabal @@ -204,3 +204,12 @@ executable advent21 import: warnings, common-extensions, build-directives, common-modules main-is: advent21/Main.hs build-depends: linear, containers + +executable advent22 + import: warnings, common-extensions, build-directives, common-modules + main-is: advent22/Main.hs + build-depends: split, containers +executable advent22bf + import: warnings, common-extensions, build-directives, common-modules + main-is: advent22/MainBruteForce.hs + build-depends: split \ No newline at end of file -- 2.34.1