# Euler Solution 205

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

# 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: 448ms. Far more efficient than my first approach. Simpler, too.

```from itertools import product
def calc(s,n):
# s = sides on die, n = number of die
total_combinations = float(s**n)
res = {}
possible_rolls = product(range(1,s+1),repeat=n)
for i in possible_rolls:
total = sum(i)
res[total] = res.setdefault(total, 0) +1
return dict([(x,(y/total_combinations)) for x,y in res.items()])

if __name__ == '__main__':
peter = calc(4,9)
colin = calc(6,6)
p2w=0
for i in peter.items():
colinthrow = 0
for j in colin.items():
if j >= i: break
colinthrow += j
p2w += colinthrow*i

print p2w
```