-
Notifications
You must be signed in to change notification settings - Fork 3
/
Day09.hs
83 lines (71 loc) · 2.55 KB
/
Day09.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
{-|
Module : Main
Description : Day 9 solution
Copyright : (c) Eric Mertens, 2018
License : ISC
Maintainer : emertens@gmail.com
<https://adventofcode.com/2018/day/9>
This solution takes advantage of "Data.Sequence" providing efficient
access to both ends of a sequence. This gives us a amortized constant
time rotation operation and allows the solution to run quickly even at
the part 2 input size.
-}
{-# Language OverloadedStrings #-}
module Main (main) where
import Advent (Parser, getParsedLines, number)
import qualified Data.IntMap.Strict as IntMap
import Data.Sequence (Seq)
import qualified Data.Sequence as Seq
-- | Print the answers to day 9
main :: IO ()
main =
do [(players, marbles)] <- getParsedLines 9 parseInput
print (game players marbles)
print (game players (100*marbles))
-- | Extract the number of players and number of marbles from the input string.
parseInput :: Parser (Int, Int) -- ^ (players, marbles)
parseInput = (,) <$> number <* " players; last marble is worth " <*> number <* " points"
-- | Player the marble game, find maximum score
--
-- >>> game 10 1618
-- 8317
-- >>> game 13 7999
-- 146373
-- >>> game 17 1104
-- 2764
-- >>> game 21 6111
-- 54718
-- >>> game 30 5807
-- 37305
game :: Int {- ^ players -} -> Int {- ^ max marble -} -> Int {- ^ max score -}
game players marbles = go IntMap.empty (Seq.singleton 0) 1
where
go scores circle i
-- game over, find winning score
| i > marbles = maximum scores
-- scoring marble, update current elf's score
| isScoreMarble i =
case rotate (-7) circle of
Seq.Empty -> error "game: empty circle"
picked Seq.:<| circle' -> go scores' circle' (i+1)
where
scores' = IntMap.insertWith (+) (i `rem` players) (i + picked) scores
-- normal turn, just add the marble
| otherwise = go scores (i Seq.<| rotate 2 circle) (i+1)
-- | Rotate the elements of a sequence. Positive numbers index from the front.
-- Negative numbers index from the back. Indexes wrap around.
--
-- >>> rotate (-2) (Seq.fromList [0..10])
-- fromList [9,10,0,1,2,3,4,5,6,7,8]
-- >>> rotate 2 (Seq.fromList [0..10])
-- fromList [2,3,4,5,6,7,8,9,10,0,1]
-- >>> rotate 10 (Seq.fromList [0..2])
-- fromList [1,2,0]
rotate :: Int -> Seq a -> Seq a
rotate n xs
| Seq.null xs = xs
| otherwise = case Seq.splitAt (n `mod` Seq.length xs) xs of
(l, r) -> r <> l
-- | Predicate for marbles that trigger a score event
isScoreMarble :: Int -> Bool
isScoreMarble i = i `rem` 23 == 0