advent of code day 14

day14.rkt

#lang racket

(require racket/hash)

(define in (open-input-file "day14.in"))

(define (amount s)
  (match-let ([(list a b) (string-split s)])
    (cons (string->number a) b)))

(define-values (rules edges)
  (for/fold ([rules (hash)] [edges (hash)])
            ([rule (in-lines in)])
    (let* ([halves (string-split rule "=>")]
           [requisites (map (compose amount string-trim) (string-split (first halves) ","))]
           [product (amount (string-trim (second halves)))])
      (values
       (hash-set rules (cdr product) (cons (car product) requisites))
       (hash-union edges (make-immutable-hash (map (lambda (p) (cons (cdr p) 1)) requisites))
                   #:combine +)))))

(define (toposort s rules edges)
  (cond
    [(empty? s) '()]
    [else
     (let* ([node (first s)]
            [requisites (cdr (hash-ref rules node '(0 . ())))]
            [rules (hash-remove rules node)]
            [edges
             (for/fold ([edges edges])
                       ([node requisites])
               (hash-update edges (cdr node) sub1))]
            [next
             (for/list ([node requisites]
                        #:when (zero? (hash-ref edges (cdr node) 0)))
               (cdr node))])
       (cons node (toposort (append (rest s) next) rules edges)))]))

(define order (toposort '("FUEL") rules edges))
; create a hash for topological comparison
(define ordering (for/hash ([(node idx) (in-indexed order)]) (values node idx)))
(define (topo<? a b)
  (< (hash-ref ordering a) (hash-ref ordering b)))

(define multiple-proc
  (make-parameter (lambda (amount produced)
                    (floor (add1 (/ (sub1 amount) produced))))))
(define (process product amount inventory)
  (cond
    [(equal? product "ORE") (values amount inventory)]
    [else
     (let ([in-inventory (hash-ref inventory product 0)])
       (cond
         [(>= in-inventory amount) ; already have the required amount
          (values 0 (hash-set inventory product (- in-inventory amount)))]
         [else ; need to produce more
          (let* ([amount (- amount in-inventory)]
                 [recipe (hash-ref rules product)]
                 [multiple ((multiple-proc) amount (car recipe))] ; part 1: how many times we need to repeat the recipe
                 [prereqs (sort (cdr recipe) topo<? #:key cdr)])
            (let-values ([(cost inventory)
                          (for*/fold ([ore 0] [inventory inventory])
                                     ([prereq prereqs]
                                      [amount (in-value (* multiple (car prereq)))])
                            (let-values ([(cost inventory) (process (cdr prereq) amount inventory)])
                              (values (+ cost ore) inventory)))])
              (values
               cost
               (hash-set inventory product (- (* multiple (car recipe)) amount)))))]))]))

; cost to make n fuel
(define (fuel-cost n)
  (let-values ([(cost remaining) (process "FUEL" n (hash))])
    cost))

; part 1
(fuel-cost 1)

; part 2
(parameterize ([multiple-proc /])
    (floor (/ 1000000000000 (fuel-cost 1))))