Solutions for Problem 205

Given a Player A who rolls nine 4-sided dice and a Player B who rolls six 6-sided dice, what is the probability (to 7 decimal places) of Player A winning any given roll.

Lisp by SanguineV

Runtime: 6111ms (with aglaope)

```; Determines the result of crossing two value/probability pairs.
; E.g. (2,1/16)x(1,1/4) = (3,1/65)
(define (crossElems a b)
(cons (+ (car a) (car b)) (cons (* (car (cdr a)) (car (cdr b))) ())))

; Cross product of lists of probability pairs.
(define (cross a b)
(if (null? a)
()
(append (map (lambda (x) (crossElems (car a) x)) b) (cross (cdr a) b))))

; Given a function to determine if a given value matches and a list of
; value/probability pairs. Determine the probability of the sum of all
; the values that match.
(define (probs f ps)
(if (null? ps)
0
(if (f (car (car ps)))
(+ (car (cdr (car ps))) (probs f (cdr ps)))
(probs f (cdr ps)))))

; Define the values and probabilities for a 4 sided dice.
(define p4
(map (lambda (x) (cons x (cons (/ 1 4) ()))) '(1 2 3 4)))

; Define the values and probabilities for a 6 sided dice.
(define p6
(map (lambda (x) (cons x (cons (/ 1 6) ()))) '(1 2 3 4 5 6)))

; Determine the raw (with repeating values) values and probabilities for
; rolling nine 4-sided dice.
(define p4-9
(cross p4 (cross p4 (cross p4 (cross p4 (cross p4 (cross p4 (cross p4 (cross p4 p4)))))))))

; Determine the raw (with repeating values) values and probabilities for
; rolling six 6-sided dice.
(define p6-6
(cross p6 (cross p6 (cross p6 (cross p6 (cross p6 p6))))))

; Determine the probabilities that the player using 4-sided dice wins any given roll,
; with known possible results for the value.
(define p4win
(map (lambda (x) (cons x (cons (probs (lambda (z) (< z x)) p6-6) ())))
'(9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36)))

; Determine the probability of rolling any given value using 4-sided dice.
(define p4probs
(map (lambda (x) (cons x (cons (probs (lambda (z) (= z x)) p4-9) ())))
'(9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36)))

; Calculate the probability of an event, given two lists, one representing the
; probabilities of each roll and the second the probability of that event for
; that roll.
(define (calc rolls odds)
(if (null? rolls)
0
(+ (* (car (cdr (car rolls))) (car (cdr (car odds)))) (calc (cdr rolls) (cdr odds)))))

; Calculate the probability of the player using 4-sided dice winning.
; Note: Added 0.0 to the result to convert to real from rational (i.e. fraction) format.
(begin (display (+ 0.0 (calc p4probs p4win))) (newline))
(exit)
```

Did the rounding by hand upon entry to the solution page. You can remove the conversion to real format to display the rational representation.

Note: The problem is fairly simple if you understand probabilities, coding it is more of a convenience than anything else.

Python by Althalus

Runtime: 4m20.237s. Seems like I could do with a more efficient way to calculate probabilities for the totals. Rounded final answer by hand.

```def do(s,n,k):
s = number of sides, n = number of dice, k = our target score.
if n == 1:
if k <= s: return 1.0/s
else: return 0

sum = 0
for i in range(1,k-n+2):
sum += do(s,1,i)*do(s,n-1,k-i)
return sum

peter = {}
colin = {}
for i in range(1,37):
peter[i] = do(4,9,i)
colin[i] = do(6,6,i)

p2w=0
for i in range(1,37):
colinthrow = 0
for j in range(1,i):
colinthrow += colin[j]
p2w += colinthrow*peter[i]

print p2w
```