## 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.

Pages: 1 2 3

### 4 Responses to “Penniless Pilgrim”

1. 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 |

```move( 4, 'ee', 2, 0,
'111001 100001 100001 100001 100001',
'11111 00000 00000 00000 00000 11111',
'2 4' );

sub move {
my( \$s, \$path, \$x, \$y, \$h, \$v, \$ss ) = @_;
if( \$x == 4 && \$y == 4 && \$s == 0) {
printf "%30s [%s]\n", \$path, \$ss;
}
unless( substr \$h, \$x+1 + \$y * 7, 1 ) {
substr my \$t = \$h, \$x+1 + \$y * 7, 1, '1';
move( \$s+2, \$path.'e', \$x+1, \$y, \$t, \$v, \$ss.' '.(\$s+2) );
}
unless( substr \$h, \$x + \$y * 7, 1 ) {
substr my \$t = \$h, \$x + \$y * 7, 1, '1';
move( \$s-2, \$path.'w', \$x-1, \$y, \$t, \$v, \$ss.' '.(\$s-2) );
}
unless( substr \$v, \$x + \$y * 6 + 6, 1 ) {
substr my \$t = \$v, \$x + \$y * 6 + 6, 1, '1';
move( \$s*2, \$path.'s', \$x, \$y+1, \$h, \$t, \$ss.' '.(\$s*2) );
}
unless( substr \$v, \$x + \$y * 6, 1 ) {
substr my \$t = \$v, \$x + \$y * 6, 1, '1';
move( \$s/2, \$path.'n', \$x, \$y-1, \$h, \$t, \$ss.' '.(\$s/2) );
}
}
```
2. Daniel said

Here’s a solution in Python.

```from collections import deque
from fractions import Fraction

# Elements in queue are tuples of:
#   (cost, x-position, y-position, path, edges)
q = deque([(Fraction(4), 2, 0, 'ee', set([(1,0), (3,0)]))])
while q:
c, x, y, p, e = q.popleft()
if (len(p) != len(e)) or  not (x in range(0,5) and y in range(0,5)):
continue
if x == 4 and y == 4 and c == 0:
print(p)
q.append((c + 2, x + 1, y, p + 'e', e | set([(x * 2 + 1, y * 2)])))
q.append((c - 2, x - 1, y, p + 'w', e | set([(x * 2 - 1, y * 2)])))
q.append((c / 2, x, y - 1, p + 'n', e | set([(x * 2, y * 2 - 1)])))
q.append((c * 2, x, y + 1, p + 's', e | set([(x * 2, y * 2 + 1)])))
```

Output:

```eessseennnwswwwssseeee
eesswseenennwswwwssseeee
eesswsenesennnwswwwssseeee
```
3. Daniel said

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.

```from fractions import Fraction

q = [(Fraction(4), 2, 0, 'ee', set([(1, 0), (3, 0)]))]
while q:
c, x, y, p, e = q.pop()
if (len(p) != len(e)) or not (x in range(0, 5) and y in range(0, 5)):
continue
if x == 4 and y == 4 and c == 0:
print(p)
q.append((c + 2, x + 1, y, p + 'e', e | set([(x * 2 + 1, y * 2)])))
q.append((c - 2, x - 1, y, p + 'w', e | set([(x * 2 - 1, y * 2)])))
q.append((c / 2, x, y - 1, p + 'n', e | set([(x * 2, y * 2 - 1)])))
q.append((c * 2, x, y + 1, p + 's', e | set([(x * 2, y * 2 + 1)])))
```

Output:

```eessseennnwswwwssseeee
eesswsenesennnwswwwssseeee
eesswseenennwswwwssseeee
```
4. Jamie Hope said

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..)?

```(define (pilgrim-all paths)
(let loop ((paths paths) (soln '()))
(if (null? paths) soln
(let ((path (car paths)))
(if (and (<= (car path) 0) (equal? (cadr path) 'Z))
(loop (cdr paths) (cons (cons (car path) (reverse (cdr path))) soln))
(loop (extend path (cdr paths)) soln))))))
```

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.