## Penniless Pilgrim

### August 10, 2018

Ben’s solution performs a brute-force search of all possible paths through the grid. The essence of the program is in the `try`

and `solve`

functions:

(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))))))))))

The `solve`

function takes the current *x*/*y* position, the current accumulated cost and a history of the current path. It figures out which directions are available to walk, then calls `try`

. The `try`

function updates the state of the pilgram and then recursively calls `solve`

, which returns `#f`

if the pilgrim can’t reach the temple, or reaches the temple with an accumulated cost greater than zero. If `try`

returns `#f`

, `solve`

tries the next possible direction, or returns `#f`

if no possibilities remain. Here is the solution:

> (solve 2 4 4 '("2,4-3,4" "3,4-4,4")) (#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"))

We see `#t`

indicating a solution has been found, 0 for the total accumulated cost, and a list of grid points in the order they are walked. Look at Ben’s blog to see a picture of the solution.

You can see the rest of the code and run the program at https://ideone.com/UNB7Al. My solution is on the next page.

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.