guile-project-euler-solutions/015/solution.scm

;;; Lattice paths

;;; Problem 15

;;; Starting in the top left corner of a 2×2 grid, and only
;;; being able to move to the right and down, there are
;;; exactly 6 routes to the bottom right corner.

;;; How many such routes are there through a 20×20 grid?

;;; NOTE: This puzzle means to state, that the top left
;;; corner is on the LINES, that make the grid, not the top
;;; left SQUARE of the grid!

(import
 (except (rnrs base) let-values map)
 (only (guile)
       lambda* λ
       ;; printing
       display
       simple-format)
 (lib math))


(define count-paths
  (λ (grid-size)
    (let* (;; Half of the steps need to be to the right and
           ;; half of them downwards.
           [steps-one-direction (- grid-size 1)]
           ;; We need twice the (grid-size - 1) steps to get
           ;; from one corner to the other.
           [steps (* (- grid-size 1) 2)])
      (/
       (/
        ;; STEP 1: The first part is the number of ways to
        ;; pick positions for going into one direction (for
        ;; example towards the right). The first pick has a
        ;; choice of n positions, the second one has n-1
        ;; positions available, the third one n-2 and so on,
        ;; until all steps are taken.
        (factorial steps)
        ;;  STEP 2: However, we only need to look at half
        ;;  the steps being taken into a single direction
        ;;  and their positions. All other steps will
        ;;  automatically be towards the other
        ;;  direction. This means, that (factorial steps) is
        ;;  too large. To take away the part of the term,
        ;;  which is too much, we need to devide by
        ;;  (factorial steps-one-direction).
        (factorial steps-one-direction))
       ;; STEP 3: However, since all steps into one
       ;; direction are actually identical direction values,
       ;; whose order does not matter, we need to divide by
       ;; the factor of duplicates, that were introduced by
       ;; taking the factorial.
       (factorial steps-one-direction)))))


(let ([grid-size 21])
  (display
   (simple-format
    #f "possible paths: ~a\n"
    (count-paths grid-size))))