Programming Praxis

4 Responses to “Penniless Pilgrim”

1. James Curtis-Smith said

   August 10, 2018 at 9:59 AM

   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

   August 10, 2018 at 5:41 PM

   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

   August 10, 2018 at 7:52 PM

   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

   August 14, 2018 at 3:22 PM

   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.