; penniless pilgrim (define (show . x) (for-each display x) (newline)) (define (++ x) (+ 1 x)) (define (-- x) (- x 1)) (define (street-name x0 y0 x1 y1) (apply string-append (if (or (and (< x0 x1) (= y0 y1)) (and (< y0 y1) (= x0 x1))) (list (number->string x0) "," (number->string y0) "-" (number->string x1) "," (number->string y1)) (list (number->string x1) "," (number->string y1) "-" (number->string x0) "," (number->string y0))))) (define (next-x x direction) (case direction ((east) (-- x)) ((west) (++ x)) (else x))) (define (next-y y direction) (case direction ((north) (++ y)) ((south) (-- y)) (else y))) (define (next-street x y direction) (street-name x y (next-x x direction) (next-y y direction))) (define (visited? x y direction history) (member (next-street x y direction) history)) (define (can-walk-north? x y history) (and (< y 4) (not (visited? x y 'north history)))) (define (can-walk-south? x y history) (and (> y 0) (not (visited? x y 'south history)))) (define (can-walk-west? x y history) (and (< x 4) (not (visited? x y 'west history)))) (define (can-walk-east? x y history) (and (> x 0) (not (visited? x y 'east history)))) (define (arrived? x y) (and (= x 0) (= y 0))) (define (try direction x y owed walked) (solve (next-x x direction) (next-y y direction) (case direction ((south) (* owed 2)) ((north) (/ owed 2)) ((east) (+ owed 2)) ((west) (- owed 2))) (cons (next-street x y direction) walked))) (define (solve x y owed walked) (cond ((arrived? x y) (list (= owed 0) owed (reverse walked))) (else (let loop ((options (apply append (list (if (can-walk-north? x y walked) '(north) '()) (if (can-walk-south? x y walked) '(south) '()) (if (can-walk-east? x y walked) '(east) '()) (if (can-walk-west? x y walked) '(west) '()))))) (cond ((null? options) (list #f owed walked)) (else (let ((attempt (try (car options) x y owed walked))) (if (car attempt) attempt (loop (cdr options)))))))))) (display (solve 2 4 4 '("2,4-3,4" "3,4-4,4"))) (newline)
Standard input is empty
(#t 0 (3,4-4,4 2,4-3,4 2,3-2,4 2,2-2,3 2,1-2,2 1,1-2,1 0,1-1,1 0,1-0,2 0,2-0,3 0,3-0,4 0,4-1,4 1,3-1,4 1,3-2,3 2,3-3,3 3,3-4,3 4,2-4,3 4,1-4,2 4,0-4,1 3,0-4,0 2,0-3,0 1,0-2,0 0,0-1,0))