(in-package :cl-user)

;;; What is the probability that throwing an n-sided die m times
;;; will result in a sum larger/smaller than a given value?

(defparameter *sides* 8)
(defparameter *throws* 19)
(defparameter *threshold* (* 19 5))
(defparameter *largerp* t)

(defun dice (n k)
  "Generates all possibilities of K throws that sum above/below N.
Two series that are permutations of each other are treated as one.
The throws are returned as increasing sequences."
  (let ((fn (if *largerp* #'< #'>)))
    (labels ((rec (n k min)
               (if (zerop k)
                   (if (funcall fn n 0) '(()) '())
                   (iter (for i from min to *sides*)
                         (appending
                          (mapcar (lambda (lst) (cons i lst))
                                  (rec (- n i) (1- k) i)))))))
      (rec n k 1))))

(defun permutations (lst)
  "Computes the permutation with repetitions according to LST,
e.g. for (1 2 2 3 5 5 5) it is 7! / (1! * 2! * 1! * 3!).
Assumes that the numbers in the list are sorted."
  (labels ((rec (lst last n)
             (cond ((null lst) (factorial n))
                   ((= (car lst) last)
                    (rec (cdr lst) last (1+ n)))
                   (t (* (factorial n)
                         (rec (cdr lst) (car lst) 1))))))
    (/ (factorial (length lst))
       (rec lst 0 0))))

#| Example:
  (defparameter *dice* (dice *threshold* *throws*))
  (defparameter *sum* (reduce #'+ (mapcar #'permutations *dice*)))
  (format t "~,2f%~%" (* 100 (/ *sum* (expt *sides* *throws*))))
  => 15.96%
|#