The 16 Game

October 29, 2013

This is a trick question. There is no need to write a program; the solution is easy to work out just by reasoning. The numbers 4 through 16 don’t contribute to the solution, and can be ignored. There are 3! = 6 permutations of the numbers 1 through 3; two of them, (1 2 3) and (2 1 3), are winners, and the other four are losers. Thus, the average winning percentage is one-third. But if you really want to write a program, here it is:

(define (play xs)
  (let loop ((xs xs) (one #f) (two #f))
    (cond ((= (car xs) 1) (if two #t (loop (cdr xs) #t #f)))
          ((= (car xs) 2) (if one #t (loop (cdr xs) #f #t)))
          ((= (car xs) 3) #f)
          (else (loop (cdr xs) one two))))))

(define (plays n)
  (let loop ((n n) (wins 0))
    (if (zero? n) wins
      (if (play (shuffle (range 1 17)))
          (loop (- n 1) (+ wins 1))
          (loop (- n 1) wins)))))

Play plays a single card; plays plays n cards. The return value of (plays n) ought to be about one-third of n:

> (plays 3000)
1010
> (plays 3000)
978
> (plays 3000)
989

It looks like our random number generator is properly uniform. We used range, randint and shuffle from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/OQTymiiW.

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 600 other followers

%d bloggers like this: