Advent of Code 2020 solutions in Racket, I guess
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.

73 lines
2.4 KiB

#lang racket
(require "lib/common.rkt"
(define (generate-edges input)
(define (generate-edges/line name rules)
(cond [(regexp-match? #px"no" rules) '()]
(for/list ([rule (in-list (map string-trim
(string-split rules #px"bag(s)?(,|.)")))])
(list (string->number (substring rule 0 1))
(substring rule 2)))]))
(for/fold ([acc '()])
([line (in-list input)])
(append (apply generate-edges/line (string-split line " bags contain "))
(define (generate-graph input)
(weighted-graph/directed (generate-edges input)))
(define (day7a in wanted)
(define G (generate-graph in))
(define-vertex-property G has-wanted #:init #f)
(do-dfs G
; only visit when the vertex is not already marked
#:visit?: (if (and $from (has-wanted $to))
(begin (has-wanted-set! $from #t) #f)
; propagate has-wanted if the child has it
#:epilogue: (when (and $from (or (has-wanted $to)
(string=? wanted $to)))
(has-wanted-set! $from $to)))
(for/sum ([(_ v) (in-hash (has-wanted->hash))] #:when v) 1))
(define (day7b in wanted)
(define G (generate-graph in))
(define-vertex-property G all-weight #:init 1)
(define (increment $from $to)
(when $from
(all-weight-set! $from
(+ (all-weight $from)
(* (edge-weight G $from $to) (all-weight $to))))))
(do-dfs G
#:order (lambda (_) (list wanted))
#:process-unvisited?: #t
#:process-unvisited: (increment $from $to)
#:epilogue: (increment $from $to))
(sub1 (all-weight wanted)))
(module+ main
(call-with-input-file "data/day7.txt"
(lambda (prt)
(define input (port->lines prt))
(answer 7 1 (day7a input "shiny gold"))
(answer 7 2 (day7b input "shiny gold")))))
(module+ test
(require rackunit)
(call-with-input-file "data/day7.test.txt"
(lambda (prt)
(define input (port->lines prt))
(check-equal? (day7a input "shiny gold") 4)
(check-equal? (day7b input "shiny gold") 32)))
(call-with-input-file "data/day7.txt"
(lambda (prt)
(define input (port->lines prt))
(check-equal? (day7a input "shiny gold") 248
"part 1 solution")
(check-equal? (day7b input "shiny gold") 57281
"part 2 solution"))))