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.

Advertisements

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: