You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('') and can be up to 35 characters long.
75 lines
2.8 KiB
75 lines
2.8 KiB
#lang debug br


(require graph)




#


Track the progress through the steps with a dag,


but track the state of the prerequisites with another dag (in the reverse direction)


#




(define dag (directedgraph null))


(define prereqs (weightedgraph/directed null))




(define (initgraphs!)


(for ([ln (inlines (openinputfile "07.txt"))])


(matchdefine (list (list left) (list right))


(map string>list (regexpmatch* #rx"(?<=[Ss]tep )." ln)))


(adddirectededge! dag left right)


(adddirectededge! prereqs right left +inf.0)))




(define (meetprereq! v1 v2)


;; a prereq is "met" if the edge weight is zero


(adddirectededge! prereqs v2 v1 0))




(define (prereqsmet? v)


;; check if all v's edges in the prereq graph are zero


(zero? (for/sum ([n (inlist (getneighbors prereqs v))])


(edgeweight prereqs v n))))




(define (findavailable g)


(filter prereqsmet? (getvertices g)))




(define (★)


(initgraphs!)


(let loop ([vsavailable (findavailable prereqs)] [done null])


(cond


[(= (length done) (length (getvertices dag))) (list>string (reverse done))]


[else


(matchdefine (list thisv others ...) (sort vsavailable char<?))


(for ([n (inlist (getneighbors dag thisv))])


(meetprereq! thisv n))


(define thisvisited (cons thisv done))


(loop (filternot (λ (v) (memv v thisvisited)) (findavailable prereqs))


thisvisited)])))




(define (workerdone? worker)


(matchdefine (cons char time) worker)


(= time (+ 60 ( (char>integer char) 65))))




(define (★★)


(initgraphs!)


(define workercount 5)


(let loop ([workers null][done null][steps 0])


(cond


[(= (length done) (length (getvertices dag))) (sub1 steps)]


[else


(definevalues (donews workingws) (partition workerdone? workers))


(define donevs (map car donews))


(for* ([v (inlist donevs)]


[n (inlist (getneighbors dag v))])


(meetprereq! v n))


(define nextdone (append donevs done))


(define updatedws (for/list ([w (inlist workingws)])


(matchdefine (cons v time) w)


(cons v (add1 time))))


(define vsavailable (for/list ([v (inlist (findavailable prereqs))]


#:unless (memv v (append nextdone (map car updatedws))))


v))


(define newvs (take (sort vsavailable char<?)


(min (length vsavailable) ( workercount (length workingws)))))


(define newworkers (map (λ (v) (cons v 0)) newvs))


(loop (append newworkers updatedws) nextdone (add1 steps))])))




(module+ test


(require rackunit)


(checkequal? (time (★)) "GNJOCHKSWTFMXLYDZABIREPVUQ")


(checkequal? (time (★★)) 886)) 