From 01011870c422fadc2cf36d8b01f79d6ee25a18ba Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Thu, 9 Jan 2020 11:20:50 +0000 Subject: [PATCH] Done day 22 --- advent22/package.yaml | 61 ++++++++++ advent22/src/advent22.hs | 104 ++++++++++++++++ data/advent22.txt | 100 +++++++++++++++ data/advent22c.txt | 10 ++ problems/day22.html | 256 +++++++++++++++++++++++++++++++++++++++ stack.yaml | 1 + 6 files changed, 532 insertions(+) create mode 100644 advent22/package.yaml create mode 100644 advent22/src/advent22.hs create mode 100644 data/advent22.txt create mode 100644 data/advent22c.txt create mode 100644 problems/day22.html diff --git a/advent22/package.yaml b/advent22/package.yaml new file mode 100644 index 0000000..e56e7ad --- /dev/null +++ b/advent22/package.yaml @@ -0,0 +1,61 @@ +# 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: advent22 +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 +- NegativeLiterals +- NumDecimals +# - OverloadedLists +- OverloadedStrings +- PartialTypeSignatures +- PatternGuards +- PatternSynonyms +- PolyKinds +- RankNTypes +- RecordWildCards +- ScopedTypeVariables +- TemplateHaskell +- TransformListComp +- TupleSections +- TypeApplications +- TypeInType +- TypeOperators +- ViewPatterns + + +executables: + advent22: + main: advent22.hs + source-dirs: src + dependencies: + - base >= 2 && < 6 + - text + - megaparsec + - finite-typelits + - groups diff --git a/advent22/src/advent22.hs b/advent22/src/advent22.hs new file mode 100644 index 0000000..d0d616a --- /dev/null +++ b/advent22/src/advent22.hs @@ -0,0 +1,104 @@ +-- import Debug.Trace + +import Data.Text (Text) +import qualified Data.Text.IO as TIO + +import Data.Void (Void) + +import Text.Megaparsec hiding (State) +import Text.Megaparsec.Char +import qualified Text.Megaparsec.Char.Lexer as L +import qualified Control.Applicative as CA + + +import Data.Finite (Finite, modulo, getFinite) +import Data.Group (Group(..), pow) +import GHC.TypeNats (KnownNat) + +import Data.Foldable (fold) + + +data ShuffleOp = Cut Integer + | Increment Integer + | Stack + deriving (Eq, Ord, Show) + +type Shuffle = [ShuffleOp] + +data Affine n = Affine { affA :: !(Finite n) + , affB :: !(Finite n) + } deriving (Eq, Ord, Show) + + +instance KnownNat n => Semigroup (Affine n) where + Affine a2 b2 <> Affine a1 b1 = Affine (a2 * a1) (a2 * b1 + b2) + +instance KnownNat n => Monoid (Affine n) where + mempty = Affine 1 0 + +instance KnownNat n => Group (Affine n) where + invert (Affine a b) = Affine a' b' + where + a' = a ^ (maxBound @(Finite n) - 1) + b' = negate (a' * b) + + +main :: IO () +main = do + text <- TIO.readFile "data/advent22.txt" + let shuffle = successfulParse text + print $ part1 shuffle + print $ part2 shuffle + + +part1 shuffle = getFinite $ trans @$ 2019 + where trans = mergeOps $ map affOfOp shuffle :: Affine 10007 + +part2 shuffle = getFinite $ invert bigTrans @$ 2020 + where trans = mergeOps $ map affOfOp shuffle :: Affine 119315717514047 + bigTrans = trans `pow` 101741582076661 + + + +affOfOp :: KnownNat n => ShuffleOp -> Affine n +affOfOp (Cut c) = Affine 1 (negate (modulo c)) +affOfOp (Increment i) = Affine (modulo i) 0 +affOfOp Stack = Affine (modulo -1) (modulo -1) + +mergeOps :: KnownNat n => [Affine n] -> Affine n +mergeOps = fold . reverse + +-- given a transformation, where does the item at x end up? +(@$) :: KnownNat n => Affine n -> Finite n -> Finite n +Affine a b @$ x = a * x + b + + +-- Parse the input file +type Parser = Parsec Void Text + +sc :: Parser () +sc = L.space (skipSome spaceChar) CA.empty CA.empty +-- sc = L.space (skipSome (char ' ')) CA.empty CA.empty + +lexeme = L.lexeme sc +integer = lexeme L.decimal +signedInteger = L.signed sc integer +symb = L.symbol sc +cutSP = symb "cut" +dealIncrementP = symb "deal with increment" +dealIntoP = symb "deal into new stack" + +cutP = Cut <$> (cutSP *> signedInteger) +incrementP = Increment <$> (dealIncrementP *> signedInteger) +stackP = Stack <$ dealIntoP + +shuffleOpP = cutP <|> incrementP <|> stackP + +shuffleP = many shuffleOpP + +-- successfulParse :: Text -> [Vec] +successfulParse :: Text -> Shuffle +successfulParse input = + case parse shuffleP "input" input of + Left _err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err + Right shuffle -> shuffle diff --git a/data/advent22.txt b/data/advent22.txt new file mode 100644 index 0000000..97760b6 --- /dev/null +++ b/data/advent22.txt @@ -0,0 +1,100 @@ +cut -45 +deal with increment 28 +cut -9687 +deal with increment 47 +cut 7237 +deal with increment 12 +cut -9336 +deal with increment 72 +cut -9471 +deal into new stack +cut -3034 +deal with increment 5 +cut -5333 +deal with increment 69 +cut -3998 +deal with increment 20 +cut 1217 +deal with increment 40 +cut -421 +deal into new stack +cut 6883 +deal with increment 7 +cut 1897 +deal with increment 57 +cut -3069 +deal with increment 10 +cut -5522 +deal with increment 64 +cut 1422 +deal with increment 55 +cut 973 +deal with increment 57 +cut 1061 +deal with increment 60 +cut -5652 +deal with increment 9 +cut 2037 +deal with increment 73 +deal into new stack +cut -8727 +deal with increment 59 +cut -2227 +deal into new stack +cut 467 +deal with increment 39 +deal into new stack +deal with increment 67 +cut -3708 +deal into new stack +cut 1394 +deal with increment 42 +cut -6618 +deal with increment 21 +deal into new stack +cut 9107 +deal with increment 33 +cut 892 +deal with increment 32 +deal into new stack +cut -7566 +deal with increment 45 +cut 5149 +deal with increment 53 +deal into new stack +deal with increment 71 +cut -1564 +deal with increment 68 +cut 6372 +deal with increment 2 +cut -3799 +deal with increment 39 +cut -2830 +deal with increment 63 +cut -4758 +deal with increment 38 +cut -6179 +deal with increment 16 +cut -1023 +deal into new stack +deal with increment 34 +cut -8829 +deal with increment 70 +cut 9112 +deal with increment 72 +cut -4044 +deal with increment 29 +cut 3010 +deal with increment 48 +cut -9025 +deal with increment 72 +cut -8418 +deal with increment 45 +cut -4991 +deal with increment 19 +cut -6999 +deal with increment 11 +cut 1852 +deal with increment 56 +deal into new stack +deal with increment 39 diff --git a/data/advent22c.txt b/data/advent22c.txt new file mode 100644 index 0000000..480cbce --- /dev/null +++ b/data/advent22c.txt @@ -0,0 +1,10 @@ +deal into new stack +cut -2 +deal with increment 7 +cut 8 +cut -4 +deal with increment 7 +cut 3 +deal with increment 9 +deal with increment 3 +cut -1 diff --git a/problems/day22.html b/problems/day22.html new file mode 100644 index 0000000..403b6ad --- /dev/null +++ b/problems/day22.html @@ -0,0 +1,256 @@ + + + + +Day 22 - Advent of Code 2019 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 44*

   <y>2019</y>

+ + + +
+ +

--- Day 22: Slam Shuffle ---

There isn't much to do while you wait for the droids to repair your ship. At least you're drifting in the right direction. You decide to practice a new card shuffle you've been working on.

+

Digging through the ship's storage, you find a deck of space cards! Just like any deck of space cards, there are 10007 cards in the deck numbered 0 through 10006. The deck must be new - they're still in factory order, with 0 on the top, then 1, then 2, and so on, all the way through to 10006 on the bottom.

+

You've been practicing three different techniques that you use while shuffling. Suppose you have a deck of only 10 cards (numbered 0 through 9):

+

To deal into new stack, create a new stack of cards by dealing the top card of the deck onto the top of the new stack repeatedly until you run out of cards:

+
Top          Bottom
+0 1 2 3 4 5 6 7 8 9   Your deck
+                      New stack
+
+  1 2 3 4 5 6 7 8 9   Your deck
+                  0   New stack
+
+    2 3 4 5 6 7 8 9   Your deck
+                1 0   New stack
+
+      3 4 5 6 7 8 9   Your deck
+              2 1 0   New stack
+
+Several steps later...
+
+                  9   Your deck
+  8 7 6 5 4 3 2 1 0   New stack
+
+                      Your deck
+9 8 7 6 5 4 3 2 1 0   New stack
+
+

Finally, pick up the new stack you've just created and use it as the deck for the next technique.

+

To cut N cards, take the top N cards off the top of the deck and move them as a single unit to the bottom of the deck, retaining their order. For example, to cut 3:

+
Top          Bottom
+0 1 2 3 4 5 6 7 8 9   Your deck
+
+      3 4 5 6 7 8 9   Your deck
+0 1 2                 Cut cards
+
+3 4 5 6 7 8 9         Your deck
+              0 1 2   Cut cards
+
+3 4 5 6 7 8 9 0 1 2   Your deck
+
+

You've also been getting pretty good at a version of this technique where N is negative! In that case, cut (the absolute value of) N cards from the bottom of the deck onto the top. For example, to cut -4:

+
Top          Bottom
+0 1 2 3 4 5 6 7 8 9   Your deck
+
+0 1 2 3 4 5           Your deck
+            6 7 8 9   Cut cards
+
+        0 1 2 3 4 5   Your deck
+6 7 8 9               Cut cards
+
+6 7 8 9 0 1 2 3 4 5   Your deck
+
+

To deal with increment N, start by clearing enough space on your table to lay out all of the cards individually in a long line. Deal the top card into the leftmost position. Then, move N positions to the right and deal the next card there. If you would move into a position past the end of the space on your table, wrap around and keep counting from the leftmost card again. Continue this process until you run out of cards.

+

For example, to deal with increment 3:

+

+0 1 2 3 4 5 6 7 8 9   Your deck
+. . . . . . . . . .   Space on table
+^                     Current position
+
+Deal the top card to the current position:
+
+  1 2 3 4 5 6 7 8 9   Your deck
+0 . . . . . . . . .   Space on table
+^                     Current position
+
+Move the current position right 3:
+
+  1 2 3 4 5 6 7 8 9   Your deck
+0 . . . . . . . . .   Space on table
+      ^               Current position
+
+Deal the top card:
+
+    2 3 4 5 6 7 8 9   Your deck
+0 . . 1 . . . . . .   Space on table
+      ^               Current position
+
+Move right 3 and deal:
+
+      3 4 5 6 7 8 9   Your deck
+0 . . 1 . . 2 . . .   Space on table
+            ^         Current position
+
+Move right 3 and deal:
+
+        4 5 6 7 8 9   Your deck
+0 . . 1 . . 2 . . 3   Space on table
+                  ^   Current position
+
+Move right 3, wrapping around, and deal:
+
+          5 6 7 8 9   Your deck
+0 . 4 1 . . 2 . . 3   Space on table
+    ^                 Current position
+
+And so on:
+
+0 7 4 1 8 5 2 9 6 3   Space on table
+
+

Positions on the table which already contain cards are still counted; they're not skipped. Of course, this technique is carefully designed so it will never put two cards in the same position or leave a position empty.

+

Finally, collect the cards on the table so that the leftmost card ends up at the top of your deck, the card to its right ends up just below the top card, and so on, until the rightmost card ends up at the bottom of the deck.

+

The complete shuffle process (your puzzle input) consists of applying many of these techniques. Here are some examples that combine techniques; they all start with a factory order deck of 10 cards:

+
deal with increment 7
+deal into new stack
+deal into new stack
+Result: 0 3 6 9 2 5 8 1 4 7
+
+
cut 6
+deal with increment 7
+deal into new stack
+Result: 3 0 7 4 1 8 5 2 9 6
+
+
deal with increment 7
+deal with increment 9
+cut -2
+Result: 6 3 0 7 4 1 8 5 2 9
+
+
deal into new stack
+cut -2
+deal with increment 7
+cut 8
+cut -4
+deal with increment 7
+cut 3
+deal with increment 9
+deal with increment 3
+cut -1
+Result: 9 2 5 8 1 4 7 0 3 6
+
+

Positions within the deck count from 0 at the top, then 1 for the card immediately below the top card, and so on to the bottom. (That is, cards start in the position matching their number.)

+

After shuffling your factory order deck of 10007 cards, what is the position of card 2019?

+
+

Your puzzle answer was 2480.

--- Part Two ---

After a while, you realize your shuffling skill won't improve much more with merely a single deck of cards. You ask every 3D printer on the ship to make you some more cards while you check on the ship repairs. While reviewing the work the droids have finished so far, you think you see Halley's Comet fly past!

+

When you get back, you discover that the 3D printers have combined their power to create for you a single, giant, brand new, factory order deck of 119315717514047 space cards.

+

Finally, a deck of cards worthy of shuffling!

+

You decide to apply your complete shuffle process (your puzzle input) to the deck 101741582076661 times in a row.

+

You'll need to be careful, though - one wrong move with this many cards and you might overflow your entire ship!

+

After shuffling your new, giant, factory order deck that many times, what number is on the card that ends up in position 2020?

+
+

Your puzzle answer was 62416301438548.

Both parts of this puzzle are complete! They provide two gold stars: **

+

At this point, you should return to your Advent calendar and try another puzzle.

+

If you still want to see it, you can get your puzzle input.

+

You can also this puzzle.

+
+ + + + + + \ No newline at end of file diff --git a/stack.yaml b/stack.yaml index a73acc6..fb6add8 100644 --- a/stack.yaml +++ b/stack.yaml @@ -59,6 +59,7 @@ packages: - advent19 - advent20 - advent21 +- advent22 # Dependency packages to be pulled from upstream that are not in the resolver. -- 2.34.1