From de640d46282134bb95db645a2bd8de687f3251b1 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Thu, 24 Dec 2020 10:55:25 +0000 Subject: [PATCH 1/1] Now with use of monad loops --- advent15/package.yaml | 9 +- advent15/src/advent15.hs | 26 +++--- advent15/src/advent15loop.hs | 75 ++++++++++++++++ advent15/src/advent15slow.hs | 1 - problems/day15.html | 165 +++++++++++++++++++++++++++++++++++ 5 files changed, 262 insertions(+), 14 deletions(-) create mode 100644 advent15/src/advent15loop.hs create mode 100644 problems/day15.html diff --git a/advent15/package.yaml b/advent15/package.yaml index cd2c591..ddc9415 100644 --- a/advent15/package.yaml +++ b/advent15/package.yaml @@ -56,7 +56,6 @@ executables: source-dirs: src dependencies: - base >= 2 && < 6 - - text - vector advent15slow: @@ -64,6 +63,12 @@ executables: source-dirs: src dependencies: - base >= 2 && < 6 - - text - containers + advent15loop: + main: advent15loop.hs + source-dirs: src + dependencies: + - base >= 2 && < 6 + - vector + - monad-loops diff --git a/advent15/src/advent15.hs b/advent15/src/advent15.hs index 87cbf3d..ac0f2b4 100644 --- a/advent15/src/advent15.hs +++ b/advent15/src/advent15.hs @@ -7,6 +7,9 @@ import Data.STRef import qualified Data.Vector.Unboxed.Mutable as V +type STInt s = STRef s Int +type VInt s = V.MVector s Int + main :: IO () main = do let seed = [20, 0, 1, 11, 6, 3] @@ -18,24 +21,25 @@ main = part1 seed = runGame seed 2020 part2 seed = runGame seed 30000000 -zeroInt :: Int -zeroInt = 0 +runGame :: [Int] -> Int -> Int +runGame seed roundsNeeded = + runST $ + do (round, word, history) <- seedGame seed roundsNeeded + gameSteps roundsNeeded round word history + readSTRef word +seedGame :: [Int] -> Int -> ST s (STInt s, STInt s, VInt s) seedGame seed historySize = do round <- newSTRef $ length seed word <- newSTRef $ last seed - history <- V.replicate historySize zeroInt + history <- V.replicate historySize 0 forM_ (zip (init seed) [1..]) $ \(t, s) -> V.write history t s return (round, word, history) -runGame seed roundsNeeded = - runST $ - do (round, word, history) <- seedGame seed roundsNeeded - gameStep roundsNeeded round word history - readSTRef word -gameStep :: Int -> STRef s Int -> STRef s Int -> V.MVector s Int -> ST s () -gameStep targetRound round word history = +-- gameSteps :: Int -> STRef s Int -> STRef s Int -> V.MVector s Int -> ST s () +gameSteps :: Int -> STInt s -> STInt s -> VInt s -> ST s () +gameSteps targetRound round word history = do roundVal <- readSTRef round if roundVal == targetRound then return () @@ -46,7 +50,7 @@ gameStep targetRound round word history = V.write history wordVal roundVal modifySTRef round (+1) writeSTRef word word' - gameStep targetRound round word history + gameSteps targetRound round word history speakWord :: Int -> Int -> Int diff --git a/advent15/src/advent15loop.hs b/advent15/src/advent15loop.hs new file mode 100644 index 0000000..7d2d258 --- /dev/null +++ b/advent15/src/advent15loop.hs @@ -0,0 +1,75 @@ +-- import Debug.Trace + +import Prelude hiding (round) +import Control.Monad +import Control.Monad.ST +import Control.Monad.Loops +import Data.STRef +import qualified Data.Vector.Unboxed.Mutable as V + + +main :: IO () +main = + do let seed = [20, 0, 1, 11, 6, 3] + -- print seed + print $ part1 seed + print $ part2 seed + + +part1 seed = runGame seed 2020 +part2 seed = runGame seed 30000000 + +runGame seed roundsNeeded = + runST $ + do (round, word, history) <- seedGame seed roundsNeeded + gameLoop roundsNeeded round word history + readSTRef word + +-- gameLoop targetRound round word history = +-- do ( gameStep round word history +-- `untilM_` (do r <- readSTRef round +-- return $ r == targetRound) +-- ) +-- return () + +-- gameLoop targetRound round word history = +-- do untilM_ (gameStep round word history ) +-- (do r <- readSTRef round +-- return $ r == targetRound ) +-- return () + +-- gameLoop targetRound round word history = +-- do whileM_ (do r <- readSTRef round +-- return $ r /= targetRound ) +-- (gameStep round word history ) +-- return () + +gameLoop targetRound round word history = + do whileM_ (do r <- readSTRef round + return $ r /= targetRound ) + $ gameStep round word history + return () + +seedGame seed historySize = + do round <- newSTRef $ length seed + word <- newSTRef $ last seed + history <- V.replicate historySize 0 + forM_ (zip (init seed) [1..]) $ \(t, s) -> V.write history t s + return (round, word, history) + +gameStep :: STRef s Int -> STRef s Int -> V.MVector s Int -> ST s () +gameStep round word history = + do roundVal <- readSTRef round + wordVal <- readSTRef word + wordH <- V.read history wordVal + let word' = speakWord wordH roundVal + V.write history wordVal roundVal + modifySTRef round (+1) + writeSTRef word word' + return () + +speakWord :: Int -> Int -> Int +speakWord 0 _ = 0 +speakWord prev now = now - prev + + diff --git a/advent15/src/advent15slow.hs b/advent15/src/advent15slow.hs index 508fedd..4c6ff07 100644 --- a/advent15/src/advent15slow.hs +++ b/advent15/src/advent15slow.hs @@ -3,7 +3,6 @@ import Prelude hiding (round) import qualified Data.IntMap.Strict as M - data Game = Game { round :: Int , word :: Int , history :: M.IntMap Int diff --git a/problems/day15.html b/problems/day15.html new file mode 100644 index 0000000..cc9a773 --- /dev/null +++ b/problems/day15.html @@ -0,0 +1,165 @@ + + + + +Day 15 - Advent of Code 2020 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 30*

   int y=2020;

+ + + +
+ +

--- Day 15: Rambunctious Recitation ---

You catch the airport shuttle and try to book a new flight to your vacation island. Due to the storm, all direct flights have been cancelled, but a route is available to get around the storm. You take it.

+

While you wait for your flight, you decide to check in with the Elves back at the North Pole. They're playing a memory game and are ever so excited to explain the rules!

+

In this game, the players take turns saying numbers. They begin by taking turns reading from a list of starting numbers (your puzzle input). Then, each turn consists of considering the most recently spoken number:

+
    +
  • If that was the first time the number has been spoken, the current player says 0.
    • +
  • Otherwise, the number had been spoken before; the current player announces how many turns apart the number is from when it was previously spoken.
    • +
+

So, after the starting numbers, each turn results in that player speaking aloud either 0 (if the last number is new) or an age (if the last number is a repeat).

+

For example, suppose the starting numbers are 0,3,6:

+
    +
  • Turn 1: The 1st number spoken is a starting number, 0.
    • +
  • Turn 2: The 2nd number spoken is a starting number, 3.
    • +
  • Turn 3: The 3rd number spoken is a starting number, 6.
    • +
  • Turn 4: Now, consider the last number spoken, 6. Since that was the first time the number had been spoken, the 4th number spoken is 0.
    • +
  • Turn 5: Next, again consider the last number spoken, 0. Since it had been spoken before, the next number to speak is the difference between the turn number when it was last spoken (the previous turn, 4) and the turn number of the time it was most recently spoken before then (turn 1). Thus, the 5th number spoken is 4 - 1, 3.
    • +
  • Turn 6: The last number spoken, 3 had also been spoken before, most recently on turns 5 and 2. So, the 6th number spoken is 5 - 2, 3.
    • +
  • Turn 7: Since 3 was just spoken twice in a row, and the last two turns are 1 turn apart, the 7th number spoken is 1.
    • +
  • Turn 8: Since 1 is new, the 8th number spoken is 0.
    • +
  • Turn 9: 0 was last spoken on turns 8 and 4, so the 9th number spoken is the difference between them, 4.
    • +
  • Turn 10: 4 is new, so the 10th number spoken is 0.
    • +
+

(The game ends when the Elves get sick of playing or dinner is ready, whichever comes first.)

+

Their question for you is: what will be the 2020th number spoken? In the example above, the 2020th number spoken will be 436.

+

Here are a few more examples:

+
    +
  • Given the starting numbers 1,3,2, the 2020th number spoken is 1.
    • +
  • Given the starting numbers 2,1,3, the 2020th number spoken is 10.
    • +
  • Given the starting numbers 1,2,3, the 2020th number spoken is 27.
    • +
  • Given the starting numbers 2,3,1, the 2020th number spoken is 78.
    • +
  • Given the starting numbers 3,2,1, the 2020th number spoken is 438.
    • +
  • Given the starting numbers 3,1,2, the 2020th number spoken is 1836.
    • +
+

Given your starting numbers, what will be the 2020th number spoken?

+
+

Your puzzle answer was 421.

--- Part Two ---

Impressed, the Elves issue you a challenge: determine the 30000000th number spoken. For example, given the same starting numbers as above:

+
    +
  • Given 0,3,6, the 30000000th number spoken is 175594.
    • +
  • Given 1,3,2, the 30000000th number spoken is 2578.
    • +
  • Given 2,1,3, the 30000000th number spoken is 3544142.
    • +
  • Given 1,2,3, the 30000000th number spoken is 261214.
    • +
  • Given 2,3,1, the 30000000th number spoken is 6895259.
    • +
  • Given 3,2,1, the 30000000th number spoken is 18.
    • +
  • Given 3,1,2, the 30000000th number spoken is 362.
    • +
+

Given your starting numbers, what will be the 30000000th number spoken?

+
+

Your puzzle answer was 436.

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.

+

Your puzzle input was 20,0,1,11,6,3.

+

You can also this puzzle.

+
+ + + + + + \ No newline at end of file -- 2.34.1