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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
5 Comments »

5 Responses to “The 16 Game”

  1. Jussi Piitulainen said
    October 29, 2013 at 3:32 PM

    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.

  2. Adolfo Pérez Álvarez (@xardon) said
    October 29, 2013 at 5:13 PM

    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)))
  3. Adolfo Pérez Álvarez (@xardon) said
    October 29, 2013 at 5:22 PM

    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)))
  4. Mark said
    October 30, 2013 at 10:42 PM

    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)
  5. Greg Yang said
    June 7, 2016 at 6:46 PM

    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

Leave a comment