You cannot select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This repo is archived. You can view files and clone it, but cannot push or open issues/pull-requests.

38 lines
1.7 KiB

This file contains invisible Unicode characters!

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

#lang br
(require racket/file sugar rackunit racket/set racket/bool)
(define links (for/set ([line (file->lines "12.rktd")])
(list->set (string-split line "-"))))
(define (is-downcase? loc) (equal? (string-downcase loc) loc))
(define (paths-from last-loc links [small-caves (set)])
(match last-loc
["end" '(("end"))]
[loc #:when (and small-caves (set-member? small-caves loc))
(define pruned-links
(for*/set ([previous-locs (in-value (set-remove small-caves loc))]
[link links]
#:when (set-empty? (set-intersect link previous-locs)))
(paths-from last-loc pruned-links #false)]
(define next-lc-visited (cond
[(false? small-caves) #false]
[(and (is-downcase? loc) (not (equal? loc "start")))
(set-add small-caves loc)]
[else small-caves]))
(define links-with-loc (for/set ([link links]
#:when (set-member? link loc))
(define remaining-links (if (or (equal? loc "start")
(and (is-downcase? loc) (not small-caves)))
(set-subtract links links-with-loc)
(for*/list ([link links-with-loc]
[next-loc (in-value (set-first (set-remove link loc)))]
[path (paths-from next-loc remaining-links next-lc-visited)])
(cons loc path))]))
(check-equal? (length (paths-from "start" links #f)) 5576)
(check-equal? (length (paths-from "start" links)) 152837)