From 7f33f392172a57f78d4de4a94af76a2f08428b66 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Tue, 22 Dec 2020 09:30:13 +0000 Subject: [PATCH] Done day 13 --- advent12/package.yaml | 2 -- advent12/src/advent12.hs | 20 ++++++------ advent13/package.yaml | 62 +++++++++++++++++++++++++++++++++++++ advent13/src/advent13.hs | 66 ++++++++++++++++++++++++++++++++++++++++ data/advent13.txt | 2 ++ stack.yaml | 1 + 6 files changed, 140 insertions(+), 13 deletions(-) create mode 100644 advent13/package.yaml create mode 100644 advent13/src/advent13.hs create mode 100644 data/advent13.txt diff --git a/advent12/package.yaml b/advent12/package.yaml index 5dbbf31..39a7c8b 100644 --- a/advent12/package.yaml +++ b/advent12/package.yaml @@ -58,6 +58,4 @@ executables: - base >= 2 && < 6 - text - attoparsec - - containers - - vector \ No newline at end of file diff --git a/advent12/src/advent12.hs b/advent12/src/advent12.hs index fb75491..c109c18 100644 --- a/advent12/src/advent12.hs +++ b/advent12/src/advent12.hs @@ -46,15 +46,15 @@ part2 actions = manhattan (positionW ship1) start ship0 = ShipW {positionW = start, waypoint = (10, 1)} ship1 = foldl actW ship0 actions -apAc actions = ship1 - where start = (0, 0) - ship0 = Ship {position = start, direction = East } - ship1 = foldl act ship0 actions +-- apAc actions = ship1 +-- where start = (0, 0) +-- ship0 = Ship {position = start, direction = East } +-- ship1 = foldl act ship0 actions -apAcW actions = ship1 - where start = (0, 0) - ship0 = ShipW {positionW = start, waypoint = (10, 1) } - ship1 = foldl actW ship0 actions +-- apAcW actions = ship1 +-- where start = (0, 0) +-- ship0 = ShipW {positionW = start, waypoint = (10, 1) } +-- ship1 = foldl actW ship0 actions act Ship{..} (N d) = Ship { position = dDelta d North position, ..} act Ship{..} (S d) = Ship { position = dDelta d South position, ..} @@ -63,9 +63,7 @@ act Ship{..} (E d) = Ship { position = dDelta d East position, ..} act Ship{..} (L a) = Ship { direction = d, ..} where d = (iterate predW direction) !! (a `div` 90) act Ship{..} (R a) = Ship { direction = d, ..} where d = (iterate succW direction) !! (a `div` 90) act Ship{..} (F d) = Ship { position = dDelta d direction position, ..} - -- where (x, y) = position - -- (dx, dy) = (delta direction) - -- p' = (x + (d * dx), y + (d * dy)) + actW ShipW{..} (N d) = ShipW { waypoint = dDelta d North waypoint, ..} actW ShipW{..} (S d) = ShipW { waypoint = dDelta d South waypoint, ..} diff --git a/advent13/package.yaml b/advent13/package.yaml new file mode 100644 index 0000000..fde2277 --- /dev/null +++ b/advent13/package.yaml @@ -0,0 +1,62 @@ +# This YAML file describes your package. Stack will automatically generate a +# Cabal file when you run `stack build`. See the hpack website for help with +# this file: . + +name: advent13 +synopsis: Advent of Code +version: '0.0.1' + +default-extensions: +- AllowAmbiguousTypes +- ApplicativeDo +- BangPatterns +- BlockArguments +- DataKinds +- DeriveFoldable +- DeriveFunctor +- DeriveGeneric +- DeriveTraversable +- EmptyCase +- FlexibleContexts +- FlexibleInstances +- FunctionalDependencies +- GADTs +- GeneralizedNewtypeDeriving +- ImplicitParams +- KindSignatures +- LambdaCase +- MonadComprehensions +- MonoLocalBinds +- MultiParamTypeClasses +- MultiWayIf +- NamedFieldPuns +- NegativeLiterals +- NumDecimals +# - OverloadedLists +- OverloadedStrings +- PartialTypeSignatures +- PatternGuards +- PatternSynonyms +- PolyKinds +- RankNTypes +- RecordWildCards +- ScopedTypeVariables +- TemplateHaskell +- TransformListComp +- TupleSections +- TypeApplications +- TypeFamilies +- TypeInType +- TypeOperators +- ViewPatterns + +executables: + advent13: + main: advent13.hs + source-dirs: src + dependencies: + - base >= 2 && < 6 + - text + - attoparsec + - arithmoi + \ No newline at end of file diff --git a/advent13/src/advent13.hs b/advent13/src/advent13.hs new file mode 100644 index 0000000..bb4117e --- /dev/null +++ b/advent13/src/advent13.hs @@ -0,0 +1,66 @@ +-- import Debug.Trace + +import Data.Text (Text) +-- import qualified Data.Text as T +import qualified Data.Text.IO as TIO + +import Data.Attoparsec.Text +-- import Data.Attoparsec.Combinator +import Control.Applicative +import Data.Maybe +import Data.List +import Math.NumberTheory.Moduli.Chinese + + + +main :: IO () +main = + do text <- TIO.readFile "data/advent13.txt" + let (timestamp, busses) = successfulParse text + print timestamp + print busses + print $ part1 timestamp busses + print $ part2 busses + +part1 timestamp maybeBusses = eBus * eTime + where busses = catMaybes maybeBusses + busDepartures = map (busAndTime timestamp) busses + (eBus, eTime) = head $ sortOn snd busDepartures + +part2 maybeBusses = b - a + where (a, b) = earliestGroup $ periodOffsets maybeBusses + + +busAndTime timestamp period = (period, earliestDeparture timestamp period) + +earliestDeparture timestamp period = period - (timestamp `mod` period) + +periodOffsets :: [Maybe Integer] -> [(Integer, Integer)] +periodOffsets maybeBusses = offsetBusses + where offsetMaybeBusses = zip [0..] maybeBusses + offsetJustBusses = filter (isJust . snd) offsetMaybeBusses + offsetBusses = map (\(o, b) -> (o, fromJust b)) offsetJustBusses + + +earliestGroup :: [(Integer, Integer)] -> (Integer, Integer) +earliestGroup offsetBusses = foldl1 chineseStep offsetBusses + + +chineseStep (n1, m1) (n2, m2) = (n, m1 * m2) + where n = fromJust $ chinese (n1, m1) (n2, m2) + + +-- Parse the input file + +timeBusP = (,) <$> decimal <* endOfLine <*> busPeriodsP + +busPeriodsP = busPeriodP `sepBy` (string ",") + +busPeriodP = (Just <$> decimal) <|> ("x" *> pure Nothing) + + +successfulParse :: Text -> (Integer, [Maybe Integer]) +successfulParse input = + case parseOnly timeBusP input of + Left _err -> (0, []) -- TIO.putStr $ T.pack $ parseErrorPretty err + Right timeBus -> timeBus diff --git a/data/advent13.txt b/data/advent13.txt new file mode 100644 index 0000000..f569282 --- /dev/null +++ b/data/advent13.txt @@ -0,0 +1,2 @@ +1000104 +41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,659,x,x,x,x,x,x,x,23,x,x,x,x,13,x,x,x,x,x,19,x,x,x,x,x,x,x,x,x,29,x,937,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,17 \ No newline at end of file diff --git a/stack.yaml b/stack.yaml index 33cb0a8..24a447e 100644 --- a/stack.yaml +++ b/stack.yaml @@ -47,6 +47,7 @@ packages: - advent10 - advent11 - advent12 +- advent13 # Dependency packages to be pulled from upstream that are not in the resolver. # These entries can reference officially published versions as well as -- 2.34.1