Programming Praxis

My solution to the Penniless Pilgrim Puzzle performs depth-first search through the graph with vertices consisting of street corners labelled A to Z (with J omitted) from top to bottom, left to right, along with edges consisting of blocks of the street. Unlike Ben, who calculated the graph in code, we represent the graph as data, with the adjacency matrix decorated with the functions that calculate the accumulated cost:

(define grid `(
  (A (B ,add2)   (F ,double)                        )
  (B (A ,sub2)   (C ,add2)   (G ,double)            )
  (C (B ,sub2)   (D ,add2)   (H ,double)            )
  (D (C ,sub2)   (E ,add2)   (I ,double)            )
  (E (D ,sub2)   (K ,double)                        )
  (F (A ,halve)  (G ,add2)   (L ,double)            )
  (G (B ,halve)  (F ,sub2)   (H ,add2)   (M ,double))
  (H (C ,halve)  (G ,sub2)   (I ,add2)   (N ,double))
  (I (D ,halve)  (H ,sub2)   (K ,add2)   (O ,double))
  (K (E ,halve)  (I ,sub2)   (P ,double)            )
  (L (F ,halve)  (M ,add2)   (Q ,double)            )
  (M (G ,halve)  (L ,sub2)   (N ,add2)   (R ,double))
  (N (H ,halve)  (M ,sub2)   (O ,add2)   (S ,double))
  (O (I ,halve)  (N ,sub2)   (P ,add2)   (T ,double))
  (P (K ,halve)  (O ,sub2)   (U ,double)            )
  (Q (L ,halve)  (R ,add2)   (V ,double)            )
  (R (M ,halve)  (Q ,sub2)   (S ,add2)   (W ,double))
  (S (N ,halve)  (R ,sub2)   (T ,add2)   (X ,double))
  (T (O ,halve)  (S ,sub2)   (U ,add2)   (Y ,double))
  (U (P ,halve)  (T ,sub2)   (Z ,double)            )
  (V (Q ,halve)  (W ,add2)                          )
  (W (R ,halve)  (V ,sub2)   (X ,add2)              )
  (X (S ,halve)  (W ,sub2)   (Y ,add2)              )
  (Y (T ,halve)  (X ,sub2)   (Z ,add2)              )
  (Z (U ,halve)  (Y ,sub2)                          )))

It is nearly always preferable to represent complex data structures like this in data rather than code; the result is more compact and more readable. The add2, sub2, halve and double functions each take a single argument and do what you expect them to do. We need a quasi-quote so the function name is treated as a function and not as a symbol.

A path through the graph is represented as a list of vertices. Function visited? calls function follows? to index through the path to determine if an edge has previously been traversed in either direction:

(define (follows? y x xs) ; does y follow x in list xs?
  (if (null? xs) #f
    (let loop ((xs xs))
      (cond ((null? (cdr xs)) #f)
            ((and (equal? (car xs) x) (equal? (cadr xs) y)) #t)
            (else (loop (cdr xs)))))))

(define (visited? from to path)
  (or (follows? from to path) (follows? to from path)))

The primary process is a depth-first search through the graph, keeping track of both the current path and its accumulated cost. Function pilgrim checks each path to determine if the result has been found, and calls extend to push more nodes onto the partial path:

(define (extend cost-and-path paths)
  (let ((cost (car cost-and-path))
        (path (cdr cost-and-path))
        (neighbors (cdr (assoc (cadr cost-and-path) grid))))
    (let loop ((neighbors neighbors) (paths paths))
      (cond ((null? neighbors) paths)
            ((not (visited? (car path) (caar neighbors) path))
              (loop (cdr neighbors)
                    (cons (cons ((cadar neighbors) cost)
                                (cons (caar neighbors) path))
                          paths)))
            (else (loop (cdr neighbors) paths))))))

(define (pilgrim paths)
  (let loop ((paths paths))
    (if (null? paths) #f
      (let ((path (car paths)))
        (if (and (zero? (car path)) (equal? (cadr path) 'Z))
            (reverse (cdr path))
            (loop (extend path (cdr paths))))))))

We call the program by initializing the list of paths with (4 C B A), which encodes the starting path A, B, C in reverse order along with its accumulated cost; note that street corner H is visited twice, traversing the first time from north to south and the second time from east to west:

> (time (pilgrim (cons '(4 C B A) (list))))
(time (pilgrim (cons (...) ...)))
    16 collections
    842 ms elapsed cpu time, including 0 ms collecting
    841 ms elapsed real time, including 1 ms collecting
    68500632 bytes allocated, including 67328032 bytes reclaimed
(A B C H N S T U P K E D I H G F L Q V W X Y Z)

You can run the program at ideone, where we compared the three available Scheme interpreters: Guile timed out after 15 seconds, Chicken completed the task in 5.25 seconds, and Stalin, after a lengthy compilation, completed the task in an astonishing 0.17 seconds.

Pages: 1 2 3