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.

About these ads

Pages: 1 2

4 Responses to “The 16 Game”

  1. Jussi Piitulainen said

    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. 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. 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

    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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: