This code gives pending paths a boolean to to keep track of whether or not the path has twice visited a visit-1 node.
$ cat 12b.rkt #lang racket (require "12a.rkt") (define (aoc-12b input) ; Return all the paths between the start and end nodes in ; the given graph, assuming at most one visit-once node is ; visited twice. (let loop ((path-count 0) (pending-paths (pending-paths:new input))) (let-values (((pending-path pending-paths) (pending-paths:pick pending-paths))) (let-values (((pc pp) (advance-path pending-path pending-paths))) (let ((path-count (+ path-count pc))) (if (pending-paths:empty? pp) path-count (loop path-count pp))))))) (define (node:is-end? node) ; Return #t iff the given node is the end node. (string=? node "end")) (define (node:is-large? node) ; Return #t iff the given node is a large node. (char-upper-case? (string-ref node 0))) (define (node:is-start? node) ; Return #t iff the given node is the start node. (string=? node "start")) (define (pending-path:current-node pending-path) ; Return the given pending paths' current node. (car pending-path)) (define (pending-path:extend-to pending-path node) ; Return a pending path that's an extension of the given ; pending path via the given node. (let* ((visited-nodes (pending-path:visited-nodes pending-path)) (visited (and (not (node:is-large? node)) (member node visited-nodes)))) (list node (cons node visited-nodes) (pending-path:neighbors pending-path) (or visited (pending-path:revisited? pending-path))))) (define (pending-path:initial input) ; Return the inital pending path for the graph described ; by the given input. (list "start" (list "start") (read-graph input) #f)) ; Return the adjacency matrix for the graph of which the ; given pending path is a part. (define pending-path:neighbors caddr) (define (pending-path:next-nodes pending-path) ; Return a list of all acceptable next nodes for the given ; pending path. (let ((neighbors (hash-ref (pending-path:neighbors pending-path) (pending-path:current-node pending-path)))) (if (pending-path:revisited? pending-path) ; The pending path has revisited a small node, so ; filter out all the next small nodes that have been ; visited. (let ((visited-nodes (pending-path:visited-nodes pending-path))) (filter (lambda (n) (or (node:is-large? n) (not (member n visited-nodes)))) neighbors)) ; The given pending path hasn't revisited a small node ; yet, so assume all neighbors are acceptable, except ; for the start node, which can't be revisited. (filter (lambda (n) (not (node:is-start? n))) neighbors)))) ; Return #t if the given pending path has revisited a small ; node, #f otherwise. (define pending-path:revisited? cadddr) ; Return a list of all nodes visited by the given pending ; path. (define pending-path:visited-nodes cadr) (define (pending-paths:add pending-paths new-path) ; Return pending paths containing all the given pending ; paths and the given new path. (set:add pending-paths new-path)) (define (pending-paths:empty? pending-paths) ; Return #t if the given pending paths is empty, #f ; otherwise. (set:empty? pending-paths)) (define (pending-paths:new input) ; Return a new collection of pending paths based on the ; given graph description. (set:new (pending-path:initial input))) (define (pending-paths:pick pending-paths) ; Pick a pending path from the given pending paths, return ; the values (p pp) where p is the path picked and pp ; contains all the given pending paths except the one ; picked. (set:pick pending-paths)) (module+ main (aoc-12b problem-input) ) (module+ test (require rackunit "aoc.rkt") (check-eq? (aoc-12b "start-a") 0) (check-eq? (aoc-12b "start-end") 1) (check-eq? (aoc-12b "start-A\nA-a\nA-end\n") 3) (check-eq? (aoc-12b "start-A\nA-a\nA-b\nA-end\n") 13) (check-eq? (aoc-12b example1-input) 36) (check-eq? (aoc-12b example2-input) 103) (check-eq? (aoc-12b example3-input) 3509) (check-eq? (aoc-12b problem-input) 116692)) $ raco test 12b.rkt raco test: (submod "12b.rkt" test) 8 tests passed $