blob: 18ed86f50fc03d5c65a11b9b810bd27bc0b6e348 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#lang racket
(require "../../jj-aoc.rkt"
threading)
(define path-pairs
(for/list ([l (in-lines (open-day 12 2021))])
(match (string-split l "-")
[(list start end) (cons start end)])))
(define edges-hash (make-hash))
(for ([pair (in-list path-pairs)])
(match-define (cons start end) pair)
(hash-update! edges-hash start (curry cons end) '())
(hash-update! edges-hash end (curry cons start) '()))
;; part 1
(define (backtracking-disallowed? next prevs)
(and (equal? (string-downcase next) next) (member next prevs)))
(define (look-for-next-cave [path-list '("start")] #:only-one-visit? [visit-used-up? #t])
(define current-cave (car path-list))
(cond
[(equal? current-cave "end") (list path-list)]
[else
(~>> (for/list ([next-path (in-list (hash-ref edges-hash current-cave null))]
#:when (and (not (equal? next-path "start"))
(not (and (backtracking-disallowed? next-path path-list)
visit-used-up?))))
(look-for-next-cave
(cons next-path path-list)
#:only-one-visit? (or (backtracking-disallowed? next-path path-list) visit-used-up?)))
(apply append))]))
(~> (look-for-next-cave) length time)
;; part 2
(~> (look-for-next-cave #:only-one-visit? #f) length time)
|
