; Program: A Pile Splitting Problem
; Solution: Originally written by Max Hailperin; modified by 
; Bill Marion (2/10/06)
; 
; Statement of the Problem: Given n objects in a pile (n >= 1),
; split the pile into two smaller piles. Continue to split each 
; pile into two smaller piles until there are n piles of size one.
; At each splitting compute the product of the size of the two 
; smaller piles. Once there are n piles, sum all the products
; computed. The result will always be the same no matter how each
; of the piles is split into two smaller piles. The sum of products
; is a function of n. (Rosen K., 2003; Tanton, J. 2004)


; This computational process allows the user repeatedly to input the number 
; of objects in the pile, n, (0 to quit), and, if n >= 1, calls the function
; to compute the sum of products and displays that sum.

(define pile-splitting-1
  (lambda ()
    (newline)
    (display "Enter the number of objects in the pile--or 0 to quit")
    (newline)
    (let ((n (read)))
          (if (= n 0)
              (begin
                (newline)
                (display "finished")
                (newline))
              (begin
                (let ((sumOfProducts (sum-of-products n)))
                (newline)
                (display "The sum of products is: ")
                (display sumOfProducts)
                (newline))
                (pile-splitting-1))))))
              
; This computational process generates a recursive process and splits
; the piles randomly into k and n-k piles until there are n piles of
; size 1. Then, the sum of products is computed.

(define sum-of-products  
  (lambda (n)             
    (if (= n 1)
        0
        (let ((k (+ 1 (random (- n 1)))))
          (+ (* k (- n k))     
             (sum-of-products k)
             (sum-of-products (- n k)))))))