Thursday, January 6, 2011

Winning money with Python

Recently someone posted the following on Reddit:

Given a pack of playing cards, select two cards (at random) from the pack. Suppose these are a two and a ten. Replace the cards in the pack and shuffle. Now turn each card over in turn and look for one of the cards (eg. two or ten) followed by the other either as the next card or the card following the next card. You should have a better than 50% chance of that happening.

There were a few posts trying to explain why this may happen and a few posts showing code (often in Python) that gave a simulation.

The first code that I came across was the following:

import random

cards = ['Ace','King','Queen','Jack','Ten','Nine','Eight','Seven','Six','Five','Four','Three','Two']

suits = ['Clubs','Spades','Hearts','Diamonds']

deck = []

for s in suits:
    for c in cards:
        deck.append(c + ' of ' + s)

NUM_TRIALS = 100000

wins = 0

for trial in range(0,NUM_TRIALS):
    #pick two non_identical card values
    card_one = cards[random.randint(0,len(cards)-1)]
    identical = True
    while identical:
        card_two = cards[random.randint(0,len(cards)-1)]
        if card_one <> card_two:
            identical = False

#shuffle the deck:
#Separated by one?
sepaRated = False
i = 0
while i < len(deck) and not separated:    
    if card_one[0:2] == deck[i][0:2]:
        if i+1 <= len(deck)-1:
            if card_two[0:2] == deck[i+1][0:2]:
                separated = True

        if i+2 <= len(deck)-1:
            if card_two[0:2] == deck[i+2][0:2]:
                separated = True                

        if card_two[0:2] == deck[i][0:2]:
            if i+1 <= len(deck)-1:
                if card_one[0:2] == deck[i+1][0:2]:
                    separated = True

     if i+2 <= len(deck)-1:
         if card_one[0:2] == deck[i+2][0:2]:
             separated = True 


    if separated:

print float(wins)/float(NUM_TRIALS)
The second solution was this one:
sum(map(bool,[(lambda k: k &(k >> 1 | k >> 3 | (k & ((2 << 116) - 1) / 3) 
>> 5))(int('0b00' + ''.join(__import__('random').sample(['01']*4+['10']
*4+['00']*44,52)),2)<<7) for i in range(2000000)]))/2000000.0  
This got me thinking about Python, readibility and 'Pythonicness'. The first solution is much closer to the problem domain - almost painfully so. The cards have been modeled as cards and the values are all strings. It took me a few seconds to parse the following statement in my head:
if card_two[0:2] == deck[i+1][0:2]
And then realised that because we are using strings for the value, we need to compare the first two characters of each string. The author of the first program claims not to have much Python experience. The second program is painfully short. It would appear that the author has going to pains to fit it all onto one line. It may appear that the author has too much Python experience (although I realise s/he was just trying to make a point). Anyway, I thought it was a nice problem and so tried to come up with a Goldilocks solution... not too much experience, not too little experience. Not too much in the problem space and not too much in the solution space. I came up with the following solution:
Given a deck of cards, select two cards at random
and run a simulation to determine how often those
two cards appear within two cards of each other.

import random

Since we are not concerned with the suit, we shall 
represent the deck as 4 lists of the cards from 1..13.
cards = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] * 4

trials = 1000 # number of simulations

def check_sequence(deck, c1, c2):
    Given a deck of cards and two single cards, return True if the
    two cards appear within 2 cards of each other in the deck, else
    return False.
    for i in range(len(deck) - 2):
        if deck[i] == c1 and (deck[i+1] == c2 or deck[i+2] == c2):
    return True

    if deck[i] == c2 and (deck[i+1] == c1 or deck[i+2] == c1):
        return True

    return False

def run_simulation():
    Run a single event.
    Without loss of generality, we may assume that the two
    random cards we selected were 1 and 2.
    return 1 if check_sequence(cards, 1, 2) else 0

def main():
    successes = 0 # number of trials where we find the two cards within 1

    for i in xrange(trials):
        successes += run_simulation()

    print float(successes) / trials

if __name__ == '__main__':
Running this version gave me similar results to the previous two versions (about 0.73 - or, in other words, 73% of the time, we would expect to find two random cards within 1 card of each other). I was pleasantly surprised to find that my code was the most efficient of the lot (i.e. ran in the shortest time). I suspect that this was because I used
rather than

In order to try to monetarise my code, I offered a friend a $5.00 bet. I lost. I took another bet and lost again.

I guess there is a moral there somewhere, but I am not exactly sure what it is.

No comments:

Post a Comment