A Program for Counting Paths through the City

Here is the program I wrote some years ago to count the numbber of non-backtracking diagonal paths through a rectangular lattice. My reason for presenting it here is certainly not pride of craftsmanship; the program takes a fairly clumsy and overspecialized approach to the problem, and it is grotesquely inefficient. But honesty demands that I disclose the program I actually wrote, rather than the one I wish I had written.

The programming language is Scheme, a dialect of Lisp.

;;; Counts the number of paths through a rectangular grid east blocks
;;; wide by north blocks high, assuming a path begins at the southwest
;;; corner and always proceeds either north or east until it reaches
;;; the northeast corner.

;;; The basic scheme is to convert a sequence of path segments into a
;;; numerical representation. For example, to enumerate the paths on a
;;; 3-by-4 grid, the program counts from 0000111 (binary) to 1110000;
;;; it examines each number in this range, throws out those that do not
;;; have exactly three 1's, and counts the remaining numbers.

;;; NOTE: Can be speeded up somewhat by replacing the multiplication
;;; and division operations with bit shifts--but the shift functions
;;; are not standard Scheme and are not portable across implementations.

(define count-paths
  (lambda (east north)
    (let* ((from (- (expt 2 north) 1))
           (to   (* from (expt 2 east))))
      (let loop ((n from) (paths 0))
        (cond ((> n to) paths)
              ((= (count-ones n) north) (loop (+ n 1) (+ paths 1)))
              (else (loop (+ n 1) paths)))))))

(define count-ones
  (lambda (n)
    (let loop ((n n) (ones 0))
      (cond ((zero? n) ones)
            ((odd? n) (loop (floor (quotient n 2)) (+ ones 1)))
            (else (loop (quotient n 2) ones))))))


>>> (count-paths 1 1)
2
>>> (count-paths 2 2)
6
>>> (count-paths 3 3)
20
>>> (count-paths 4 4)
70
>>> (count-paths 5 5)
252
>>> (count-paths 6 6)
924
>>> (count-paths 7 7)
3432
>>> (count-paths 8 8)
12870
>>> (count-paths 9 9)
48620
>>> (count-paths 10 10)
184756
>>> 


With a better mathematical understanding of where these numbers come from, one can write a much better program for calculating them. Here is a straightforward example. It is much more efficient than the program given above and could be made even moreso by simple refinements to the factorial function.


(define count-paths
  (lambda (east north)
    (binomial (+ east north) east)))

(define binomial
  (lambda (m n)
    (/ (factorial m)
       (* (factorial n)
          (factorial (- m n))))))

(define factorial
  (lambda (n)
    (if (< n 2)
        1
        (* n (factorial (- n 1))))))