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.
Programming Praxis 
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) ); } }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:
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:
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.