🎄⌨️ Advent of Code 2018

#lang racket

(require rackunit sugar/debug)

(define input (file->lines "day07-input.txt"))

; A "step rule" is a list of the form `(prerequisite prereq-for)
(define (inputlines->steprules str)
  (rest (regexp-match #px"Step ([A-Z]) must be finished before step ([A-Z]) can begin." str)))

(define steprules (map inputlines->steprules input))

;; A hash table: for each step, a list of prerequisite steps
(define starting-prereqs
  (for/fold ([result (hash)])
            ([steprule (in-list steprules)])
    (let ([existing-prereqs (hash-ref result (second steprule) '())])
      (hash-set result (second steprule) (cons (first steprule) existing-prereqs)))))

(define alphabet
  (map (lambda(c) (list->string (list c))) ; Convert #\A to "A"
       (map integer->char (range 65 91))))

;; The starting step is the one that’s NOT in `rule-dependencies`
;; -- because, by definition, the first step has no dependencies.
(define starting-step
  (first (remove* (hash-keys starting-prereqs) alphabet)))

;; Return the first item in a list of steps that have no remaining prerequisites
;; sorted alphabetically
(define (next-available-step h)
  (define avail-steps
    (sort (filter identity (hash-map h (lambda (k v) (if (empty? v) k #f)))) string<?))
  (cond [(not (empty? avail-steps)) (first avail-steps)]
        [else '()]))

;; Remove the given step from all prerequisite-lists for other tasks, then
;; remove its own prerequisite-list from the hash table
(define (remove-from h step)
  (define updated-prereqs
    (for/hash ([(k v) (in-hash h)])
              (values k (remove step v))))
  (hash-remove updated-prereqs step))

(define (day07-part1)
  (let loop ([prereqs starting-prereqs]
             [current-step starting-step]
             [done-steps '()])
    (cond
      [(hash-empty? prereqs) (apply string-append (reverse done-steps))]
      [else
       (let* ([next-prereqs (remove-from prereqs current-step)]
              [next-step (next-available-step next-prereqs)])
         (loop next-prereqs next-step (cons current-step done-steps)))])))

(module+ test
  (check-equal? (day07-part1) "BGJCNLQUYIFMOEZTADKSPVXRHW")) ; Correct answer for part 1

;; The worker list is a hash table. Each worker is an entry in the hash which contains
;; a list of the form '(task secs-remaining).
(define starting-workers
  (make-hash '((0 0 0) (1 0 0) (2 0 0) (3 0 0) (4 0 0))))

;; Returns seconds needed to complete a task
(define (secs-to-complete step)
  (+ 60 (- (char->integer (first (string->list step))) 64)))

;; Return all the steps with no prerequisites that are not already being worked on
(define (available-steps h workers)
  (define ready-steps (filter identity (hash-map h (lambda (k v) (if (empty? v) k #f)))))
  (define being-worked-on (filter string? (map first (hash-values workers))))
  (remove* being-worked-on ready-steps))

;; Assign any newly-ready steps to available workers, return the new worker list
(define (assign-tasks workers prereqs)
  (define ready-steps (available-steps prereqs workers))
  (define available-workers
    (for/list ([(worker task) (in-hash workers)]
               #:when (not (string? (first task))))
              worker))
  (cond [(and (not (empty? ready-steps)) (not (empty? available-workers)))
         (for ([worker (in-list available-workers)]
               [task (in-list ready-steps)])
              (hash-set! workers worker (list task (secs-to-complete task))))])
  workers)

;; Subtract 1 sec from time remaining for any workers with active tasks
(define (tick workers)
  (for ([(worker task) (in-hash workers)])
       (match-let ([(list task-id secs-left) task])
         (cond [(> secs-left 0)
                (hash-set! workers worker (list task-id (sub1 secs-left)))])))
  workers)

;; For any tasks that have hit 0 secs remaining, remove them from the list of
;; prerequisite tasks, and signal that the worker is now free for a new task
;; (by assigning her a task of `0`)
(define (update prereqs workers)
  (for/fold ([result-prereqs prereqs])
            ([(worker task) (in-hash workers)])
    (cond [(and (equal? (second task) 0) (string? (first task)))
           (begin
             (hash-set! workers worker '(0 0))
             (remove-from result-prereqs (first task)))]
          [else result-prereqs])))

;; Bring it all together now
(define (day07-part2)
  (let loop ([prereqs (hash-set starting-prereqs starting-step '())]
             [workers starting-workers]
             [sec-elapsed 0])
    (cond [(hash-empty? prereqs) sec-elapsed]
          [else (let ([next-workers (tick (assign-tasks workers prereqs))])
                  (loop (update prereqs next-workers) next-workers (add1 sec-elapsed)))])))

(module+ test
  (check-equal? (day07-part2) 1017)) ; Correct answer for part 2