Day 3 and 4 kinda kicked my butt (plus I had work stuff both nights) but I finally finished day 4. It asks us to solve a scheduling problem, and the example even shows us a nice matrix we could use.
I was sort of leery about trying another matrix based on my adventures on day 3. (I made what I thought was a reasonable-sized matrix and blew through all my memory, probably due to lazy execution or something.) So instead I went with a horribly compute-inefficient design.
Input looks like this:
[1518-03-11 00:45] wakes up
[1518-07-13 00:13] falls asleep
[1518-11-02 23:56] Guard #3463 begins shift
[1518-11-13 00:59] wakes up
[1518-06-15 23:59] Guard #829 begins shift
[1518-08-16 00:03] Guard #1399 begins shift
[1518-09-18 00:19] wakes up
[1518-08-30 00:56] wakes up
[1518-04-22 00:32] falls asleep
[1518-10-07 00:41] wakes up
[1518-08-21 00:28] falls asleep
...
Parsing into a data structure isn't too bad, I haven't had to learn and break out a parser combinator yet. We can easily sort the timeline using standard alphanumeric ordering:
type Time = Int
type GuardId = Int
type GuardTotals = Map.Map GuardId Time
type GuardSched = Array Int Int
data Event =
ShiftBegin Time GuardId |
Sleep Time |
Wake Time
deriving Show
timeToOffset :: String -> String -> Time
-- timeToOffset h m = 60 * (read h) + (read m)
-- oops, only minute matters
timeToOffset h m = (read m)
parseEvent :: String -> Event
parseEvent s =
case splitOneOf "[:] #" s of
(_:_:h:m:_:kw:_) | kw == "wakes" -> Wake (timeToOffset h m)
(_:_:h:m:_:kw:_) | kw == "falls" -> Sleep (timeToOffset h m)
(_:_:h:m:_:kw:_:n:_) | kw == "Guard" -> ShiftBegin (timeToOffset h m) (read n )
_ -> undefined
chronology = map parseEvent (sort (splitOn "\n" input) )
Part one asks for which guard spent the most time sleeping, overall. (Not averaged!) I decided to do this as a fold, as that seems the right way in Haskell to "do something to every element of the list, maintaining some state." So I built a state machine as a function that I can call foldl on.
data GuardState =
InitialState |
Awake GuardId |
Asleep GuardId Time
deriving Show
addOrInsert :: Int -> Maybe Int -> Maybe Int
addOrInsert x (Just y) = Just (x+y)
addOrInsert x Nothing = Just x
updateSleep :: (GuardState,GuardTotals) -> Event -> (GuardState,GuardTotals)
updateSleep (InitialState,m) (ShiftBegin time id) = ((Awake id),m)
updateSleep (InitialState,m) _ = error "No shift begin"
updateSleep (Awake id, m) (ShiftBegin time newId) = (Awake newId, m)
updateSleep (Awake id, m) (Wake _) = error "Guard woke up when already awake."
updateSleep (Awake id, m) (Sleep time) = (Asleep id time,m)
updateSleep (Asleep _ _, _) (ShiftBegin _ _) = error "New shift started when guard asleep."
updateSleep (Asleep _ _, _) (Sleep _) = error "Guard slept when already asleep."
updateSleep (Asleep id start, m) (Wake end) =
let minutes = end - start in
(Awake id,
Map.alter (addOrInsert minutes) id m)
The only surprising part was figuring out that most of the functions to modify a Map actually took a function rather than a new value, but OK. (I'm using Data.Map.Strict from containers-0.6.0.1.) Totaling up all the guard's sleep times thus becomes:
guardTotals = foldl' updateSleep (InitialState,Map.empty) chronology
Next we needed which minute that guard slept the most. I really did not think making my state machine drag along an array as well as a map was a great idea, but that would be most efficient. Part of the problem is that I don't know how to decompose this in a way that makes it easy to see what's being done on each state transition. There's probably some Haskell pattern to do this.
So in the absence of something smart to do, I just copy/pasted a second version for computing the histogram of sleep per minute:
updateSched :: GuardId -> (GuardState,GuardSched) -> Event -> (GuardState,GuardSched)
updateSched g (InitialState,m) (ShiftBegin time id) = ((Awake id),m)
updateSched g (InitialState,m) _ = error "No shift begin"
updateSched g (Awake id, m) (ShiftBegin time newId) = (Awake newId, m)
updateSched g (Awake id, m) (Wake _) = error "Guard woke up when already awake."
updateSched g (Awake id, m) (Sleep time) = (Asleep id time,m)
updateSched g (Asleep _ _, _) (ShiftBegin _ _) = error "New shift started when guard asleep."
updateSched g (Asleep _ _, _) (Sleep _) = error "Guard slept when already asleep."
updateSched g (Asleep id start, a) (Wake end)
| g == id = (Awake id,
accum (+) a [(t,1) | t <- [start..(end-1)] ])
| g /= id = (Awake id, a )
emptySched = array (0,59) [ (i,0) | i <- [0..59] ]
We can get that array for a particular guard
schedule g = snd (foldl' (updateSched g) (InitialState,emptySched) chronology)
and after that it's just putting the pieces together. But this solution kinda sucks because it goes over the input N+1 times, where N is the number of guards.
guards = Map.keys (snd guardTotals)
max2nd (g1,s1) (g2,s2)
| s1 > s2 = (g1,s1)
| s1 <= s2 = (g2,s2)
sleepiestGuard = foldl1 max2nd (Map.assocs (snd guardTotals))
sleepiestMinute g = foldl1 max2nd (assocs (schedule g))
reorder guard (minute,count) = ((guard,minute),count)
consistentSleeper = foldl1 max2nd [ reorder g (sleepiestMinute g) |
g <- guards ]
main :: IO ()
main = putStrLn (show (take 5 chronology)) >>
putStrLn (show guardTotals) >>
putStrLn ("Guard who slept the most: " ++
(show (fst sleepiestGuard))) >>
putStrLn ("His schedule: " ++
(show (schedule (fst sleepiestGuard)))) >>
putStrLn ("His sleepiest minute: " ++
show (fst (sleepiestMinute (fst sleepiestGuard)))) >>
putStrLn ("Most consistent sleeper/minute: " ++
show (consistentSleeper))
A better version would do one pass over the input and compute a list of schedules, each schedule a row of 0's and 1's for whether the guard is sleeping. Then we can add the rows for each guard, and from that we can compute both part 1 (sum the row and take the max over guards) and part 2 (max the rows and take the max over guards).
Full version checked in here: https://github.com/mgritter/aoc2018/blob/master/day4/day4.hs