A Brute Force Solution to the Penniless Pilgrim Riddle

The Kids Should See This posted a challenge known as the Penniless Pilgrim Riddle. There's a video describing the riddle as well as the solution below. Here's a summary of the puzzle.

Consider this map and your current location:

The rules are as follows:

• You start off with a tax of $4.00
• Every time you walk a block the tax owed is modified. Go east add 2, go west subtract 2, go south multiply by 2, go north divide by 2.
• You can't walk the same block more than once.

How can you go from the position shown on the map to the bottom right hand corner with an ending tax of $0.00?

On the surface, this doesn't seam possible. Every block you walk south, taking you closer to the end point, incurs a 2x penalty.

After pondering this puzzle for a few minutes I decided to write code to find me a solution. That counts as solving it, right?

My approach was to do a brute force attack on the problem. The poor pilgrim would have to walk every possible combination of legal routes until he found one that worked. The complete code I wrote is here. However, these two functions capture the essence of my solution.

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

solve takes in a current x/y position, current tax owed and a history of the blocks that have been walked. The function figures out which possible directions are legal to walk, and then calls try on the first one. try updates the state of pilgrim and then calls solve. solve returns false if the pilgrim didn't reach the destination, or reached the destination with a tax greater than zero. If try returns false, solve goes on and tries the next direction it found as valid. When all possible directions are exhausted, solve gives up returning false.

To find a solution to this riddle I kicked off solve like so:

(solve 2 4 4 '("3,4-4,4" "2,4-3,4"))

This invocation accounts for the fact that the pilgrim starts at 2,4 with a $4.00 tax. The list of blocks walked is a notation that names every street in the grid. It does so by combining the x,y coordinates of the street's end points. The smaller coordinate is always listed first. This insures that regardless of how the pilgrim approaches a road, it will be named properly.

I kicked off the above on my Galaxy S9+ under Termux and waited. A minute or so later, I had this output:

The pilgrim arrived at 0,0 with a $0.00 tax; it worked! The list of street names tells me the route that pilgrim took to get there. I transcribed the streets to a piece of scrap paper and arrived at a visual display of my discovered route:

I had a feeling that the grid size was small enough in this problem that a brute force attack would work, and it did.

There's something poetic about a recursive solution like this. So many attempts are made, yet the code to try all these attempts is relatively terse.

Definitely take the time to watch the video and accompanying solution. Most importantly, it walks you through the process of teasing out a valid route using little more than simple observation. It's inspirational: maybe next time I won't be so impatient and jump right to coding. But still, this was some fun code to write!