The 16 Game
October 29, 2013
A local store has a promotional game in which scratch-off cards have sixteen spaces that cover a random permutation of the numbers 1 through 16. Customers scratch off the spaces at random. If the scratch-off reveals the number 3, the card loses. If the scratch-offs reveal the numbers 1 and 2, in either order, the card wins. Winning cards receive a discount on store merchandise.
Your task is to write a program that determines the average winning percentage. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
The only thing that matters is the relative order of 1, 2, and 3 in a permutation. Since 1/3 of the permutations have 1 and 2 before 3, the classical probability of winning is 1/3 and the expected percentage of winning cards in a pack is a little above 33. I didn’t write a program.
Solution in Racket.
#lang racket (define (shuffle! v) (define len (vector-length v)) (for ([i (in-range len)]) (define j (+ i (random (- len i)))) (define tmp (vector-ref v i)) (vector-set! v i (vector-ref v j)) (vector-set! v j tmp)) v) (define slots-per-card 16) (define (scratch-card card) (for*/fold ([x 0]) ([i (shuffle (range slots-per-card))] [c (in-value (vector-ref card i))] #:break (or (= c 3) (= x 2)) #:when (or (= c 1) (= c 2))) (add1 x))) (define (winning-% [tries 10000]) (define card (build-vector slots-per-card add1)) (define n (for*/sum ([_ (in-range tries)] [_ (shuffle! card)] [x (in-value (scratch-card card))] #:when (= 2 x)) 1)) (exact->inexact (/ n tries)))Oops! The winning-% function had a bug in the second for*/sum clause.
(define (winning-% [tries 10000]) (define card (build-vector slots-per-card add1)) (define n (for*/sum ([_ (in-range tries)] [_ (in-value (shuffle! card))] ;; <== [x (in-value (scratch-card card))] #:when (= 2 x)) 1)) (exact->inexact (/ n tries)))Trying Nimrod:
import math var numTrials = 1000000 j, tmp: int a = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] tot = 0 for n in 1..numTrials: for i in countdown(15,1): j = random(i+1) tmp = a[i] a[i] = a[j] a[j] = tmp if a.find(3) > a.find(2) and a.find(3) > a.find(1): tot += 1 echo(tot / numTrials)A slightly different approach, which recursively calculate the probability. It is “generalized” to take any N >= 3, but that doesn’t matter :-)
module TheSixteenGame(
solve
) where
solve :: Int -> Double
solve n
| n <= 2 = error "Input integer should be >= 3"
| otherwise = twoLeft n
twoLeft :: Int -> Double
twoLeft n
| n == 2 = 1.0
| otherwise = pickOne * oneLeft (n – 1) + pickNone * twoLeft (n – 1)
where
pickOne = 2.0 / fromIntegral n
pickNone = fromIntegral (n – 3) / fromIntegral n
oneLeft :: Int -> Double
oneLeft n
| n == 1 = 1.0
| otherwise = pickOne + pickNone * oneLeft (n – 1)
where
pickOne = 1.0 / fromIntegral n
pickNone = fromIntegral (n – 2) / fromIntegral n