-
Notifications
You must be signed in to change notification settings - Fork 0
/
07.hs
executable file
·420 lines (365 loc) · 15.3 KB
/
07.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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
#!/usr/bin/env stack
{- stack --resolver=nightly-2018-11-14 script --compile
--package "here megaparsec pretty-show safe split"
-}
-- relude
-- {-# Language NoImplicitPrelude #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE QuasiQuotes #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE TupleSections #-}
-- import Relude
import Control.Monad.State
import Data.Char
import Data.Either
import Data.Function
import Data.List
import Data.List.Split
import Data.Maybe
import Data.String.Here
import Debug.Trace
import Safe
import Text.Printf
import Text.Show.Pretty
import qualified Text.Megaparsec as M
import qualified Text.Megaparsec.Char as M
pp :: Show a => a -> IO ()
pp = putStrLn . ppShow
ltrace :: Show a => String -> a -> a
ltrace msg x =
trace (msg++": "++show x)
x
{-
You find yourself standing on a snow-covered coastline; apparently,
you landed a little off course. The region is too hilly to see the
North Pole from here, but you do spot some Elves that seem to be
trying to unpack something that washed ashore. It's quite cold out, so
you decide to risk creating a paradox by asking them for directions.
"Oh, are you the search party?" Somehow, you can understand whatever
Elves from the year 1018 speak; you assume it's Ancient Nordic
Elvish. Could the device on your wrist also be a translator? "Those
clothes don't look very warm; take this." They hand you a heavy coat.
"We do need to find our way back to the North Pole, but we have higher
priorities at the moment. You see, believe it or not, this box
contains something that will solve all of Santa's transportation
problems - at least, that's what it looks like from the pictures in
the instructions." It doesn't seem like they can read whatever
language it's in, but you can: "Sleigh kit. Some assembly required."
"'Sleigh'? What a wonderful name! You must help us assemble this
'sleigh' at once!" They start excitedly pulling more parts out of the
box.
The instructions specify a series of steps and requirements about
which steps must be finished before others can begin (your puzzle
input). Each step is designated by a single letter. For example,
suppose you have the following instructions:
Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.
Visually, these requirements look like this:
-->A--->B--
/ \ \
C -->D----->E
\ /
---->F-----
Your first goal is to determine the order in which the steps should be
completed. If more than one step is ready, choose the step which is
first alphabetically. In this example, the steps would be completed as
follows:
Only C is available, and so it is done first.
Next, both A and F are available. A is first alphabetically, so it
is done next.
Then, even though F was available earlier, steps B and D are now
also available, and B is the first alphabetically of the three.
After that, only D and F are available. E is not available because
only some of its prerequisites are complete. Therefore, D is completed
next.
F is the only choice, so it is done next.
Finally, E is completed.
So, in this example, the correct order is CABDFE.
In what order should the steps in your instructions be completed?
-}
test = parselines [here|
Step C must be finished before step A can begin.
Step C must be finished before step F can begin.
Step A must be finished before step B can begin.
Step A must be finished before step D can begin.
Step B must be finished before step E can begin.
Step D must be finished before step E can begin.
Step F must be finished before step E can begin.
|]
type Step = Char
type Rule = (Step,Step) -- step a is a prerequisite of step b
parselines :: String -> [Rule]
parselines = fromRight [] . M.parse p ""
where
p :: M.Parsec String String [(Char,Char)]
p = do
xs <- M.many $ do
M.string "Step "
a <- M.letterChar
M.string " must be finished before step "
b <- M.letterChar
M.string " can begin."
M.optional M.eol
return (a,b)
M.eof
return xs
-- All the steps mentioned in a list of rules.
steps :: [Rule] -> [Step]
steps rules = nub $ sort $ map fst rules ++ map snd rules
-- The steps which have prerequisites.
depsteps rules = nub $ sort $ map snd rules
-- List the steps which have no prequisites.
freesteps rules = steps rules \\ depsteps rules
-- Pick the likely first step from a list of rules, ie the step that
-- has no prerequisites and appears first in the list.
firststep rules = head $ freesteps rules
-- The steps required before this step, if any.
stepdeps :: [Rule] -> Step -> [Step]
stepdeps rules s = map fst $ filter ((==s).snd) rules
-- Given lists of step dependency rules and completed steps,
-- which steps could be done next ?
availablesteps rules done =
[s | s <- steps rules \\ done, -- uncompleted steps
all (`elem` done) $ stepdeps rules s -- whose prequisites have all been completed
]
-- Choose the next step (first available one).
donextstep :: [Rule] -> [Step] -> [Step]
donextstep rules done
| null available = done
| otherwise = done++[next]
where
cur = last done
available = availablesteps rules done
next = head $ sort $ available
-- Find a complete legal step sequence, hopefully.
findsteps rules =
last $ take (length $ steps rules) $
iterate (donextstep rules) [firststep rules]
a = findsteps input
type Time = Int -- time in seconds since simulation start
type Worker = Maybe (Step, Time) -- a worker's current assigned step and predicted completion time
data World = W {
wrules :: [Rule] -- step dependency rules
,wtime :: Time -- elapsed seconds since simulation start
,wtodo :: [Step] -- steps remaining to do
,wdone :: [Step] -- steps done
,wworkers :: [Worker] -- all workers' states
} deriving (Show)
-- initialise a simulation with given step dependency rules and number of workers
initWorld :: [Rule] -> Int -> World
initWorld rs numworkers =
W {wrules = rs
,wtime = 0
,wdone = []
,wworkers = replicate numworkers Nothing
,wtodo = steps rs
}
-- assign as many tasks as possible to available workers
assignSteps :: World -> World
assignSteps w = w{wworkers=wworkers', wtodo=wtodo'}
where
wipsteps = map fst $ catMaybes $ wworkers w
readysteps = -- ltrace ("ready at "++show (wtime w)) $
availablesteps (wrules w) (wdone w) \\ wipsteps
numfreeworkers = length $ filter isNothing $ wworkers w
assignsteps = -- ltrace "assigning" $
take numfreeworkers readysteps
wtodo' = wtodo w \\ assignsteps
wworkers' = foldl' assignone (wworkers w) assignsteps
where
assignone :: [Worker] -> Step -> [Worker]
assignone ws s = as ++ [Just (s, finishtime)] ++ drop 1 rest
where
(as,rest) = break isNothing ws
finishtime = wtime w + steptime s
steptime s =
60 +
1 + (ord s - ord 'A')
-- advance the clock to the next task completion(s), record the done task(s),
-- and free up the worker(s).
completeAStep w =
-- trace ("finished at "++show wtime'++": "++intersperse ' ' finishedsteps)
w{wtime=wtime',wdone=wdone',wworkers=wworkers'}
where
wtime' = minimum $ map snd $ catMaybes $ wworkers w
isdone (Just (_,finishtime)) | finishtime == wtime' = True
isdone _ = False
finishedsteps = map fst $ catMaybes $ filter isdone $ wworkers w
wdone' = wdone w ++ finishedsteps
wworkers' = map free $ wworkers w
where
free mw | isdone mw = -- trace ("freeing: "++[fst$fromJust$mw])
Nothing
| otherwise = mw
-- print a one-line summary of current simulation state
traceState w@W{..} = flip trace w $ intercalate " " [
printf "%4d" wtime
,intersperse ' ' $ map (maybe '.' fst) wworkers
,wdone
]
-- run a simulation until all tasks are completed
runWorld :: World -> World
runWorld w@W{wtodo=[]} = w
runWorld w = w
& assignSteps
& traceState
& completeAStep
& traceState
& runWorld
-- simulate completing all tasks with the given dependencies and number of workers,
-- returning the final state
runRules :: [Rule] -> Int -> World
runRules rs numworkers = runWorld $ initWorld rs numworkers
b rs n = wtime (runRules rs n)
-- 1115
{-
As you're about to begin construction, four of the Elves offer to
help. "The sun will set soon; it'll go faster if we work together."
Now, you need to account for multiple people working on steps
simultaneously. If multiple steps are available, workers should still
begin them in alphabetical order.
Each step takes 60 seconds plus an amount corresponding to its letter:
A=1, B=2, C=3, and so on. So, step A takes 60+1=61 seconds, while step
Z takes 60+26=86 seconds. No time is required between steps.
To simplify things for the example, however, suppose you only have
help from one Elf (a total of two workers) and that each step takes 60
fewer seconds (so that step A takes 1 second and step Z takes 26
seconds). Then, using the same instructions as above, this is how each
second would be spent:
Second Worker 1 Worker 2 Done
0 C .
1 C .
2 C .
3 A F C
4 B F CA
5 B F CA
6 D F CAB
7 D F CAB
8 D F CAB
9 D . CABF
10 E . CABFD
11 E . CABFD
12 E . CABFD
13 E . CABFD
14 E . CABFD
15 . . CABFDE
Each row represents one second of time. The Second column identifies
how many seconds have passed as of the beginning of that second. Each
worker column shows the step that worker is currently doing (or . if
they are idle). The Done column shows completed steps.
Note that the order of the steps has changed; this is because steps
now take time to finish and multiple workers can begin multiple steps
simultaneously.
In this example, it would take 15 seconds for two workers to complete
these steps.
With 5 workers and the 60+ second step durations described above, how
long will it take to complete all of the steps?
-}
input = parselines [here|
Step G must be finished before step S can begin.
Step T must be finished before step Q can begin.
Step A must be finished before step B can begin.
Step H must be finished before step X can begin.
Step V must be finished before step O can begin.
Step Z must be finished before step P can begin.
Step R must be finished before step J can begin.
Step L must be finished before step Y can begin.
Step Y must be finished before step E can begin.
Step W must be finished before step X can begin.
Step X must be finished before step B can begin.
Step K must be finished before step E can begin.
Step Q must be finished before step P can begin.
Step U must be finished before step B can begin.
Step M must be finished before step O can begin.
Step P must be finished before step N can begin.
Step I must be finished before step J can begin.
Step B must be finished before step C can begin.
Step C must be finished before step O can begin.
Step J must be finished before step F can begin.
Step F must be finished before step O can begin.
Step E must be finished before step D can begin.
Step D must be finished before step N can begin.
Step N must be finished before step S can begin.
Step S must be finished before step O can begin.
Step W must be finished before step O can begin.
Step L must be finished before step P can begin.
Step N must be finished before step O can begin.
Step T must be finished before step D can begin.
Step G must be finished before step I can begin.
Step V must be finished before step X can begin.
Step B must be finished before step N can begin.
Step R must be finished before step N can begin.
Step H must be finished before step J can begin.
Step B must be finished before step S can begin.
Step P must be finished before step I can begin.
Step A must be finished before step J can begin.
Step A must be finished before step U can begin.
Step B must be finished before step D can begin.
Step T must be finished before step A can begin.
Step U must be finished before step D can begin.
Step T must be finished before step L can begin.
Step I must be finished before step E can begin.
Step R must be finished before step U can begin.
Step H must be finished before step S can begin.
Step P must be finished before step F can begin.
Step Q must be finished before step C can begin.
Step A must be finished before step P can begin.
Step X must be finished before step E can begin.
Step Q must be finished before step N can begin.
Step E must be finished before step N can begin.
Step Q must be finished before step O can begin.
Step J must be finished before step S can begin.
Step X must be finished before step P can begin.
Step K must be finished before step U can begin.
Step F must be finished before step E can begin.
Step C must be finished before step E can begin.
Step H must be finished before step K can begin.
Step W must be finished before step B can begin.
Step G must be finished before step O can begin.
Step F must be finished before step N can begin.
Step I must be finished before step D can begin.
Step G must be finished before step V can begin.
Step E must be finished before step S can begin.
Step Y must be finished before step P can begin.
Step G must be finished before step E can begin.
Step P must be finished before step J can begin.
Step U must be finished before step N can begin.
Step U must be finished before step F can begin.
Step X must be finished before step U can begin.
Step X must be finished before step C can begin.
Step R must be finished before step Q can begin.
Step Q must be finished before step E can begin.
Step Z must be finished before step E can begin.
Step X must be finished before step F can begin.
Step J must be finished before step D can begin.
Step X must be finished before step M can begin.
Step Y must be finished before step D can begin.
Step K must be finished before step J can begin.
Step Z must be finished before step J can begin.
Step M must be finished before step P can begin.
Step T must be finished before step M can begin.
Step F must be finished before step S can begin.
Step P must be finished before step S can begin.
Step X must be finished before step I can begin.
Step U must be finished before step J can begin.
Step M must be finished before step B can begin.
Step Q must be finished before step D can begin.
Step Z must be finished before step I can begin.
Step D must be finished before step S can begin.
Step J must be finished before step N can begin.
Step D must be finished before step O can begin.
Step T must be finished before step H can begin.
Step P must be finished before step D can begin.
Step M must be finished before step F can begin.
Step Y must be finished before step S can begin.
Step H must be finished before step I can begin.
Step Y must be finished before step W can begin.
Step X must be finished before step J can begin.
Step L must be finished before step W can begin.
Step G must be finished before step N can begin.
|]