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.

72 lines
2.2 KiB

#lang racket
(require "lib/common.rkt"
graph)
(define (parse prt)
(define (parse-line str)
(define-values (ingredients contains)
(match str
[(pregexp #px"(.*) \\(contains (.*)\\)" (list _ a b)) (values a b)]
[(pregexp #px"(.*)" (list _ a)) (values a #f)]
[else (error "oh no")]))
(list (string-split ingredients)
(if contains
(map string-trim (string-split contains ","))
#f)))
(map parse-line (port->lines prt)))
(define (generate-mapping input)
(for*/fold ([acc (hash)])
([food (in-list input)]
[allergen (in-list (second food))])
(define ingredients (list->set (first food)))
(hash-update acc allergen (λ (e) (set-intersect ingredients e)) ingredients)))
(define (day21a input)
(define mapping (generate-mapping input))
(define with-allergens
(for*/fold ([acc (set)])
([(_ ingredients) (in-hash mapping)])
(set-union ingredients acc)))
(define all-ingredients
(for*/list ([food (in-list input)]
[ingredient (in-list (first food))])
ingredient))
(define no-allergens (set-subtract (list->set all-ingredients) with-allergens))
(for*/sum ([noa (in-set no-allergens)]
[ing (in-list all-ingredients)]
#:when (equal? ing noa))
1))
(define (day21b input)
(define mapping (generate-mapping input))
(define edges
(for*/list ([(k v) (in-hash mapping)]
[f (in-set v)])
(list k f)))
(define G (undirected-graph edges))
(define match-hash
(for/hash ([i (in-list (maximum-bipartite-matching G))])
(values (second i) (first i))))
(define sorted-allergens (sort (hash-keys match-hash) string<?))
(string-join
(for/list ([v (in-list sorted-allergens)])
(hash-ref match-hash v))
","))
(module+ main
(call-with-input-file "data/day21.txt"
(λ (prt)
(define input (parse prt))
(answer 21 1 (day21a input))
(answer 21 2 (day21b input)))))
(module+ test
(require rackunit)
(call-with-input-file "data/day21.test.txt"
(λ (prt)
(define input (parse prt))
(check-equal? (day21a input) 5)
(check-equal? (day21b input) "mxmxvkd,sqjhc,fvjkl"))))