Racket implementation for JiaXian triangle

jiaxian-triangle

#lang racket

(define (Mb-to-B n) (* n 1024 1024))
(define MAX-BYTES (Mb-to-B 64))
(custodian-limit-memory (current-custodian) MAX-BYTES)

(define nil (list))

(define (string-multiplier a-string factor)
  (cond 
    [(< factor 1) ""]
    [(= factor 1) a-string]
    [else
      (string-append a-string (string-multiplier a-string (- factor 1)))]))

(define (printline elems #:sep [sep " "] #:end [end "\n"] #:element-converter [element-converter identity])
  (define (iter remaining-elements result-string)
    (cond
      [(empty? remaining-elements) (string-append result-string end)]
      [(empty? (rest remaining-elements))
        (iter (rest remaining-elements)
              (string-append result-string
                             (element-converter (first remaining-elements))))]
      [else
        (iter (rest remaining-elements)
              (string-append result-string
                             (element-converter (first remaining-elements))
                             sep))]))
  (cond
    [(empty? elems) (display end)]
    [(not (list? elems)) (display (string-append (element-converter elems) end))]
    [else (display (iter elems ""))]))

(define (second a-list)
  (first (rest a-list)))

(define number-to-string-converter
  (lambda (integer-value)
    (number->string integer-value)))

;; ================================
;; ITERATIVE PROCESS IMPLEMENTATION
;; ================================
(define (jiaxian-iterative-process depth)
  (define (build-next-level current-level)
    (define (iter numbers result)
      (cond
        ;; no more numbers to work with
        [(empty? numbers) result]
        ;; is the result still empty, we are at the beginning,
        [(empty? result)
          (iter numbers
                (cons 1 result))]
        ;; if we are at any position after the beginning
        [else
          (cond
            [(empty? (rest numbers)) (iter nil (cons (first numbers) result))]
            [else 
              (iter (rest numbers)
                    (cons (+ (first numbers) (second numbers))
                          result))])]))

    (iter current-level nil))

  (define (calculate-triangle depth result)
    (cond
      [(= depth 0) result]
      [(< depth 0) (printline "Use numbers greater than zero to calculate the triangle.")]
      [else
        (calculate-triangle (- depth 1)
                            (cons (build-next-level (first result))
                                  result))]))

  (reverse (calculate-triangle depth (list (list 1)))))

;; ================================
;; RECURSIVE PROCESS IMPLEMENTATION
;; ================================
;; This procedure is not optimal, as it calculates many elements of the triangle multiple times.
(define (jiaxian-recursive-process depth)
  (define (calculate-cell row col)
    (cond
      [(= row 0) 1]
      [(= col 0) 1]
      [(= row col) 1]
      [else
        (+ (calculate-cell (- row 1) (- col 1))
           (calculate-cell (- row 1) col))]))

  (define (calculate-row row current-col result)
    (cond
      [(= current-col row) (cons (calculate-cell row current-col) result)]
      [else
        (calculate-row row
                       (+ current-col 1)
                       (cons (calculate-cell row current-col) result))]))

  (define (calculate-triangle depth result)
    (cond
      [(= depth 0) (cons (list 1) result)]
      [else (calculate-triangle (- depth 1) (cons (calculate-row depth 0 nil) result))]))

  (calculate-triangle depth nil))



;; This procedure prints out a triangle.
(define (jiaxian-print triangle)
  (define (iter triangle remaining-rows)
    (cond
      [(empty? triangle) (printline "Done.")]
      [else
        (begin
          (display (string-multiplier " " remaining-rows))
          (printline (first triangle) #:element-converter number-to-string-converter #:sep " ")
          (iter (rest triangle) (- remaining-rows 1)))]))

  (iter triangle (length triangle)))

(time (jiaxian-print (jiaxian-iterative-process 20)))
(time (jiaxian-print (jiaxian-recursive-process 20)))

This implementation includes an iterative process version and a recursive process version for calculating the Jia Xian triangle, also known as the Pascal's triangle, although Pascal did not even discover it first. I suspect the recursive process procedure could be made more efficient, by handling an additional vector containing all already calculated cells of the triangle, in order to avoid calculating them multiple times.