Euler Solution 205

From ProgSoc Wiki

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