## Penniless Pilgrim

### August 10, 2018

My solution to the Penniless Pilgrim Puzzle performs depth-first search through the graph with vertices consisting of street corners labelled A to Z (with J omitted) from top to bottom, left to right, along with edges consisting of blocks of the street. Unlike Ben, who calculated the graph in code, we represent the graph as data, with the adjacency matrix decorated with the functions that calculate the accumulated cost:

(define grid `( (A (B ,add2) (F ,double) ) (B (A ,sub2) (C ,add2) (G ,double) ) (C (B ,sub2) (D ,add2) (H ,double) ) (D (C ,sub2) (E ,add2) (I ,double) ) (E (D ,sub2) (K ,double) ) (F (A ,halve) (G ,add2) (L ,double) ) (G (B ,halve) (F ,sub2) (H ,add2) (M ,double)) (H (C ,halve) (G ,sub2) (I ,add2) (N ,double)) (I (D ,halve) (H ,sub2) (K ,add2) (O ,double)) (K (E ,halve) (I ,sub2) (P ,double) ) (L (F ,halve) (M ,add2) (Q ,double) ) (M (G ,halve) (L ,sub2) (N ,add2) (R ,double)) (N (H ,halve) (M ,sub2) (O ,add2) (S ,double)) (O (I ,halve) (N ,sub2) (P ,add2) (T ,double)) (P (K ,halve) (O ,sub2) (U ,double) ) (Q (L ,halve) (R ,add2) (V ,double) ) (R (M ,halve) (Q ,sub2) (S ,add2) (W ,double)) (S (N ,halve) (R ,sub2) (T ,add2) (X ,double)) (T (O ,halve) (S ,sub2) (U ,add2) (Y ,double)) (U (P ,halve) (T ,sub2) (Z ,double) ) (V (Q ,halve) (W ,add2) ) (W (R ,halve) (V ,sub2) (X ,add2) ) (X (S ,halve) (W ,sub2) (Y ,add2) ) (Y (T ,halve) (X ,sub2) (Z ,add2) ) (Z (U ,halve) (Y ,sub2) )))

It is nearly always preferable to represent complex data structures like this in data rather than code; the result is more compact and more readable. The `add2`

, `sub2`

, `halve`

and `double`

functions each take a single argument and do what you expect them to do. We need a quasi-quote so the function name is treated as a function and not as a symbol.

A path through the graph is represented as a list of vertices. Function `visited?`

calls function `follows?`

to index through the path to determine if an edge has previously been traversed in either direction:

(define (follows? y x xs) ; does y follow x in list xs? (if (null? xs) #f (let loop ((xs xs)) (cond ((null? (cdr xs)) #f) ((and (equal? (car xs) x) (equal? (cadr xs) y)) #t) (else (loop (cdr xs)))))))

(define (visited? from to path) (or (follows? from to path) (follows? to from path)))

The primary process is a depth-first search through the graph, keeping track of both the current path and its accumulated cost. Function `pilgrim`

checks each path to determine if the result has been found, and calls `extend`

to push more nodes onto the partial path:

(define (extend cost-and-path paths) (let ((cost (car cost-and-path)) (path (cdr cost-and-path)) (neighbors (cdr (assoc (cadr cost-and-path) grid)))) (let loop ((neighbors neighbors) (paths paths)) (cond ((null? neighbors) paths) ((not (visited? (car path) (caar neighbors) path)) (loop (cdr neighbors) (cons (cons ((cadar neighbors) cost) (cons (caar neighbors) path)) paths))) (else (loop (cdr neighbors) paths))))))

(define (pilgrim paths) (let loop ((paths paths)) (if (null? paths) #f (let ((path (car paths))) (if (and (zero? (car path)) (equal? (cadr path) 'Z)) (reverse (cdr path)) (loop (extend path (cdr paths))))))))

We call the program by initializing the list of paths with `(4 C B A)`

, which encodes the starting path A, B, C in reverse order along with its accumulated cost; note that street corner `H`

is visited twice, traversing the first time from north to south and the second time from east to west:

> (time (pilgrim (cons '(4 C B A) (list)))) (time (pilgrim (cons (...) ...))) 16 collections 842 ms elapsed cpu time, including 0 ms collecting 841 ms elapsed real time, including 1 ms collecting 68500632 bytes allocated, including 67328032 bytes reclaimed (A B C H N S T U P K E D I H G F L Q V W X Y Z)

You can run the program at ideone, where we compared the three available Scheme interpreters: Guile timed out after 15 seconds, Chicken completed the task in 5.25 seconds, and Stalin, after a lengthy compilation, completed the task in an astonishing 0.17 seconds.

Again BFI – works well as the grid is small – and need recursive code – keep track of “$h” and “$v” the state of the edges both horizontally and vertically….

Found 3 solutions

[sourecode]

eesswseene|nnwswwwssseeee

eesswsenesen|nnwswwwssseeee

eessseen|nnwswwwssseeee

[/sourecode]

which are all identical after where I’ve put the |

Here’s a solution in Python.

Output:

Here’s an alternative version of my earlier solution. This uses depth-first search instead of breadth-first search. This is slightly simpler since it doesn’t have the deque dependency.

Output:

Running @Praxis’s solution in Kawa took 3.5 seconds the first time. Subsequent runs dropped to ~3.04 (JIT kicks in after a method has been invoked enough times).

Ben’s solution isn’t the same one as in the video he embedded, so the obvious next question is: how many solutions are there? And are there any solutions that end with a negative cost (a tax refund, which presumably the pilgrim would give to the temple as an offering..)?

After 68 seconds, that spit out:

[pre]

((-2 A B C H G F L Q R S T U P K E D I H N M R W X Y Z)

(0 A B C H N M R S N O T U P K E D I H G F L Q V W X Y Z)

(0 A B C H N M R S T O P K E D I H G F L Q V W X Y Z)

(-2 A B C H N M R S T U P K E D I H G F L Q R W X Y Z)

(-4 A B C H N M R S T U P K E D I H G F L Q V W X Y Z)

(0 A B C H N S T U P K E D I H G F L Q V W X Y Z))

[/pre]

So, there are 3 zero-cost paths, and three negative-cost paths.