# Euler Solution 205

(Difference between revisions)
 Revision as of 03:19, 7 September 2010 (view source)Althalus (Talk | contribs) (→Solutions for Problem 205)← Older edit Latest revision as of 05:25, 7 September 2010 (view source)Althalus (Talk | contribs) (→Python by Althalus) Line 75: Line 75: == Python by Althalus == == 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. + Runtime: 448ms. Far more efficient than my first approach. Simpler, too. - def do(s,n,k): + from itertools import product - ''' s = number of sides, n = number of dice, k = our target score. ''' + def calc(s,n): - if n == 1: + # s = sides on die, n = number of die - if k <= s: return 1.0/s + total_combinations = float(s**n) - else: return 0 + 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()]) - sum = 0 + if __name__ == '__main__': - for i in range(1,k-n+2): + peter = calc(4,9) - sum += do(s,1,i)*do(s,n-1,k-i) + colin = calc(6,6) - return sum + p2w=0 + for i in peter.items(): + colinthrow = 0 + for j in colin.items(): + if j[0] >= i[0]: break + colinthrow += j[1] + p2w += colinthrow*i[1] - peter = {} + print p2w - 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 + [[Category: Euler]] [[Category: Euler]]

# 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[0] >= i[0]: break
colinthrow += j[1]
p2w += colinthrow*i[1]

print p2w
```