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