Euler Solution 205

From ProgSoc Wiki

Revision as of 03:19, 7 September 2010 by Althalus (Talk | contribs)
Jump to: navigation, search

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
Personal tools