# Euler Solution 205

### From ProgSoc Wiki

(Difference between revisions)

(→Solutions for Problem 205) |
(→Python by Althalus) |
||

Line 75: | Line 75: | ||

== Python by Althalus == | == Python by Althalus == | ||

- | Runtime: | + | Runtime: 448ms. Far more efficient than my first approach. Simpler, too. |

- | def | + | 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__': | |

- | for i in | + | 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 | |

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + | ||

[[Category: Euler]] | [[Category: Euler]] |

## Latest revision as of 05:25, 7 September 2010

# 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