## Penniless Pilgrim

### August 10, 2018

Today’s exercise comes to us courtesy of long-time reader and contributor Ben Simon; you might like to look at his version of the task:

You must travel from the top-left corner of a five-by-five grid of points to the bottom-right corner, stepping from one point to another without retracing any edge. The first two steps must be eastward through the grid. Each step has a cost. An eastward step adds 2 to the current accumulated cost (so you start with an accumulated cost of 4), a westward step subtracts 2 from the current accumulated cost, a northward step halves the current accumulated cost, and a southward step doubles the current accumulated cost. It is possible to reach the bottom-right corner with an accumulated cost of zero.

Ben’s version of the task has a pretty map of Duonia, and a story about a penniless pilgrim who longs to visit the temple.

Your task is to write a program to find the zero-cost path through the grid. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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.