advent-of-code/2018-12-07.lisp -rw-r--r-- 7.5 KiB View raw
                                                                                
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
(defpackage "AOC/7" (:use "CL"))
(in-package "AOC/7")

(defvar *input* "Step O must be finished before step W can begin.
Step S must be finished before step V can begin.
Step Z must be finished before step B can begin.
Step F must be finished before step R can begin.
Step I must be finished before step D can begin.
Step W must be finished before step P can begin.
Step J must be finished before step E can begin.
Step P must be finished before step N can begin.
Step Q must be finished before step V can begin.
Step D must be finished before step K can begin.
Step X must be finished before step N can begin.
Step E must be finished before step B can begin.
Step L must be finished before step H can begin.
Step A must be finished before step T can begin.
Step U must be finished before step R can begin.
Step M must be finished before step T can begin.
Step V must be finished before step R can begin.
Step N must be finished before step C can begin.
Step T must be finished before step C can begin.
Step Y must be finished before step B can begin.
Step H must be finished before step B can begin.
Step B must be finished before step C can begin.
Step C must be finished before step K can begin.
Step R must be finished before step K can begin.
Step G must be finished before step K can begin.
Step Q must be finished before step K can begin.
Step U must be finished before step Y can begin.
Step L must be finished before step G can begin.
Step S must be finished before step D can begin.
Step E must be finished before step R can begin.
Step Z must be finished before step M can begin.
Step U must be finished before step K can begin.
Step Q must be finished before step H can begin.
Step T must be finished before step B can begin.
Step J must be finished before step Q can begin.
Step X must be finished before step V can begin.
Step Q must be finished before step U can begin.
Step T must be finished before step K can begin.
Step S must be finished before step B can begin.
Step L must be finished before step C can begin.
Step Q must be finished before step D can begin.
Step E must be finished before step K can begin.
Step N must be finished before step G can begin.
Step L must be finished before step T can begin.
Step E must be finished before step L can begin.
Step A must be finished before step N can begin.
Step V must be finished before step C can begin.
Step D must be finished before step L can begin.
Step O must be finished before step S can begin.
Step V must be finished before step Y can begin.
Step N must be finished before step T can begin.
Step I must be finished before step H can begin.
Step U must be finished before step N can begin.
Step O must be finished before step Y can begin.
Step J must be finished before step C can begin.
Step Y must be finished before step C can begin.
Step W must be finished before step A can begin.
Step M must be finished before step C can begin.
Step X must be finished before step E can begin.
Step S must be finished before step J can begin.
Step U must be finished before step C can begin.
Step H must be finished before step K can begin.
Step Q must be finished before step B can begin.
Step E must be finished before step G can begin.
Step N must be finished before step H can begin.
Step I must be finished before step J can begin.
Step P must be finished before step B can begin.
Step Z must be finished before step T can begin.
Step J must be finished before step M can begin.
Step C must be finished before step G can begin.
Step I must be finished before step B can begin.
Step D must be finished before step G can begin.
Step X must be finished before step T can begin.
Step O must be finished before step F can begin.
Step A must be finished before step Y can begin.
Step S must be finished before step G can begin.
Step X must be finished before step K can begin.
Step L must be finished before step M can begin.
Step A must be finished before step H can begin.
Step D must be finished before step H can begin.
Step U must be finished before step T can begin.
Step B must be finished before step K can begin.
Step S must be finished before step C can begin.
Step W must be finished before step R can begin.
Step M must be finished before step G can begin.
Step M must be finished before step H can begin.
Step J must be finished before step D can begin.
Step W must be finished before step Y can begin.
Step S must be finished before step Y can begin.
Step A must be finished before step G can begin.
Step P must be finished before step M can begin.
Step C must be finished before step R can begin.
Step Q must be finished before step Y can begin.
Step O must be finished before step H can begin.
Step O must be finished before step R can begin.
Step Q must be finished before step M can begin.
Step V must be finished before step B can begin.
Step H must be finished before step G can begin.
Step J must be finished before step V can begin.
Step M must be finished before step R can begin.
Step R must be finished before step G can begin.")

(defun parse-rule (stream)
  (let ((line (read-line stream nil)))
    (when line
      (assert (string= (subseq line 0 5) "Step "))
      (assert (string= (subseq line 6 36) " must be finished before step "))
      (assert (string= (subseq line 37) " can begin."))
      (list (aref line 36) (aref line 5)))))

(defun parse-rules (stream)
  (loop for rule = (parse-rule stream)
        while rule
        collect rule))

(let ((rules (with-input-from-string (s *input*) (parse-rules s))))
  (loop for next = (first (sort (remove-duplicates (loop for (target dep) in rules unless (find dep rules :key #'first) collect dep)) #'char<))
        while next
        do (format t "~a" next)
        do (setf rules (remove next rules :key #'second))))
;; The above doesn’t print the last character, and it’s not generally
;; correct (what happens if more than one target is unlocked at a
;; time?), but for our purposes it works.  The final target is K

(let ((deps (make-hash-table))
      (rules (with-input-from-string (s *input*) (parse-rules s)))
      (num-workers 5)
      targets
      working
      (done (make-hash-table)))
  (loop for (target dep) in rules
        do (push dep (gethash target deps))
        do (pushnew target targets)
        do (pushnew dep targets))
  (loop for time from 0
        while (and (or targets working) (< time 10000))
        do (setf working (loop for (task remaining) in working
                               if (= remaining 1)
                                 do (progn
                                      (incf num-workers)
                                      (setf (gethash task done) t)
                                      (loop for k being the hash-keys of deps using (hash-value v)
                                            do (setf (gethash k deps) (remove task v))))
                               else
                                 collect (list task (1- remaining))))
        do (loop for next in (sort (loop for target in targets
                                         unless (or (gethash target deps)
                                                    (gethash target done)
                                                    (find target working :key #'first))
                                           collect target)
                                   #'char<)
                 while (and next (plusp num-workers))
                 do (progn
                      (push (list next (+ (char-code next) -64 60)) working)
                      (decf num-workers)
                      (setf targets (remove next targets))))
        do (format t "~&~a: ~a~%" time working)))