Can you answer this mathematical poseur<?

curiously that gives me precisely 14

0 Replies

curiously that gives me precisely 14

don't think i can proceed from there

I get exactly 14 as well when I use your formulas instead of your data. Take at look at the next-to-last multiplicand of your last term - it's -1/2. That ought to be a red flag. This approach is flawed. Great care is given to ensure that the second card doesn't match the first, but after that no care is taken to ensure that the nth card doesn't match the n-1th prior to n being the position we're currently interested in. At this point, I trust my simulation to be much closer to the actual answer.

Maybe Drewdad will give the simulation another shot...

2 Replies

@markr,

I will, when I get some free time. May not be for several days, though.

0 Replies

@markr,

I've spent some time thinking about the best way to figure out the exact numbers, taking into account the previous non-snap value matches. I came up with one that I'm pretty sure is correct, and is pretty neat. Wrote a Python program to do it, and it actually runs pretty quickly. It works by keeping track of, not which cards match other cards or even which card positions match other card posistions, but rather the possibilities of matching previous matching groups of different sizes (sizes 1-4).

I have tried including the program here, but the formatting gets completely screwed up, which is a disaster in trying to understand Python because of the significance of white space. This happens even when I use code and /code tags. Those tags do put the program in a code box, but the formatting is still screwed up. If anybody knows a way around this, I'll be happy to post the program.

Here's the output of the program (values for cards 4 and 5 are the same as I got manually in posts above):

(Note that these numbers are not applying an expected value formula - they are the current and cumulative snap chances for each card number.)

Code:



Card #, Current snap chance, Cumulative snap chance:

 1   0                 0

 2   0.0588235294118   0.0588235294118

 3   0.0564705882353   0.1152941176471

 4   0.0530132052821   0.1683073229292

 5   0.0497959183673   0.2181032412965

 6   0.0467778600802   0.2648811013767

 7   0.0439447712480   0.3088258726247

 8   0.0412852415712   0.3501111141959

 9   0.0387885329895   0.3888996471854

10   0.0364445705912   0.4253442177766

11   0.0342439087387   0.4595881265153

12   0.0321776916758   0.4917658181911

13   0.0302376163500   0.5220034345411

14   0.0284158976056   0.5504193321467

15   0.0267052355871   0.5771245677338

16   0.0250987852119   0.6022233529457

17   0.0235901275781   0.6258134805238

18   0.0221732431865   0.6479867237103

19   0.0208424868574   0.6688292105677

20   0.0195925642372   0.6884217748049

21   0.0184185097915   0.7068402845964

22   0.0173156661904   0.7241559507868

23   0.0162796649969   0.7404356157836

24   0.0153064085764   0.7557420243601

25   0.0143920531485   0.7701340775086

26   0.0135329929080   0.7836670704165

27   0.0127258451491   0.7963929155656

28   0.0119674363266   0.8083603518923

29   0.0112547889963   0.8196151408886

30   0.0105851095774   0.8302002504660

31   0.0099557768862   0.8401560273522

32   0.0093643313906   0.8495203587428

33   0.0088084651408   0.8583288238836

34   0.0082860123330   0.8666148362166

35   0.0077949404653   0.8744097766819

36   0.0073333420499   0.8817431187318

37   0.0068994268443   0.8886425455761

38   0.0064915145710   0.8951340601471

39   0.0061080280919   0.9012420882389

40   0.0057474870120   0.9069895752510

41   0.0054085016827   0.9123980769337

42   0.0050897675803   0.9174878445140

43   0.0047900600363   0.9222779045503

44   0.0045082292971   0.9267861338474

45   0.0042431958925   0.9310293297400

46   0.0039939462927   0.9350232760327

47   0.0037595288369   0.9387828048696

48   0.0035390499157   0.9423218547853

49   0.0033316703912   0.9456535251765

50   0.0031366022400   0.9487901274166

51   0.0029531054057   0.9517432328223

52   0.0027804848466   0.9545237176689

1 Reply

@solipsister,

go away practice your English and ask again.

On second thoughts dont bother.

0 Replies

@rg123,

Looks like I may be able to successfuly post the program if I break it into more than one post...

Code:



# snapchance.py



# Written and tested with Python 2.5.2 (not compatible with Python 3000)



# Calculate chances to "snap" at each card position in a deck of

# 52 cards.  A snap means matching the value (ignoring suit) of the

# immediately previous card.



from __future__ import division # prevent / division from truncating



from copy import deepcopy

from bisect import insort



print "Card #, Current snap chance, Cumulative snap chance:"

print " 1   0                 0"

# That one was easy enough.  ;-)



# At each position (card_number), there is a group of matching previous

# cards (a group can be composed of 1-4 cards) which includes the last

# card played.  I will say that this group is "in snap position."

# There is also some number of other groups (this number is 0 at

# card_number==2).  There can never be more than 13 previous groups

# total, since there are only 13 card values.



# The chance for the next card to match an existing group is

# 4-(number of cards in group)/cards remaining.



# At each position (ie card_number), for each possible combination

# of groups, I will determine the snap chance and add these chances

# up for that row of branch values to get the current_snap_chance.

# Snap cases, and groups of 4 cards (which cannot be subsequently

# matched) will not be carried forward.  The cases where other

# groups are matched, and where no groups are matched, will be used to

# construct the list of possible group combinations for the next

# position.



# Each possibility (branch value at a level) has:

# [size_of_group_in_snap_position, [list of sizes of other groups],

# branch_probability]

# The list below has one item, itself a list which represents a group

# of size 1 in snap position, a curently empty list of sizes of other

# groups, and a probability of 1.  This is what we start with as the

# root of the tree before card_number 2:

old_branches = [[1,[],1],]



cumulative_snap_chance=0



for card_number in xrange(2,53):   # for card_number == 2 to 52...

    

    cards_remaining=53-card_number # cards remaining at

                                   # current card number

    current_snap_chance=0

    new_branches=[] #list of new branch possibilities starts out empty



    while len(old_branches)>0: # while there's a possibility left in the

                               # old list...

        branch=old_branches.pop() # Get a possibility out of the old list,

                                  # reducing the size of the old list

                                  # while building the new one to save

                                  # memory.

        

        current_numerator=0 # running total used below when determining

                            # the chance of matching no cards.

        

        #first, to handle the snap match...

        matches_remaining=4-branch[0] # 0 is index of first list item

        # if size of group in snap position is less than 4...

        if matches_remaining>0:

             current_numerator=current_numerator+matches_remaining

             # backslash at end of next line is for line continuation

             # in Python...

             current_snap_chance=current_snap_chance+branch[2]* \

                                 matches_remaining/cards_remaining



        #now for matches to the other groups...

        for size in branch[1]: # for each group size in the list of other

                               # groups...

            matches_remaining=4-size

            if matches_remaining>0:

                current_numerator=current_numerator+matches_remaining

                # construct a new possibility...

                # deepcopy() below creates a copy of branch for us to

                # modify.  new_branch=branch would just create another

                # reference to the same list object, and conflict with

                # later cases.

                new_branch=deepcopy(branch)

                # the group in snap position becomes one of the others...

                # (the insort() function inserts into a list in such a way

                # as to keep it sorted)

                insort(new_branch[1], branch[0])

                # move the matched group to snap position...

                new_branch[0]=size+1 # it's size is incremented too, since

                                     # we are adding a match to it.

                new_branch[1].remove(size)

                # probability of this new possibility is...

                new_branch[2]=branch[2] * matches_remaining/cards_remaining

                # If there's already an existing branch in the new branch

                # list with the same snap group size and list of other

                # group sizes, we can combine the new probability with that

                # existing one to save size in the new list:

                for prior_branch in new_branches:

                    if prior_branch[0]==new_branch[0] and \

                       prior_branch[1]==new_branch[1]:

                        prior_branch[2]=prior_branch[2] + \

                                         new_branch[2]

                        break

                else: # Python allows an else clause on the for loop.  This

                      # will execute if the for loop completes without a

                      # break above.

                    insort(new_branches,new_branch)



        # now for the case where no existing groups are matched...

2 Replies

@rg123,

Program continued. First line here is last line in previous post...

Code:



        # now for the case where no existing groups are matched...

        if cards_remaining>current_numerator:

            # construct a new possibility...

            # (can modify branch here instead of deepcopying it,

            # since this is the last case)

            # the group in snap position becomes one of the others

            insort(branch[1],branch[0])

            # a new group of 1 goes into snap position...

            branch[0]=1

            # probability of this possibility is...

            branch[2]=branch[2]*(cards_remaining-current_numerator)/ \

                          cards_remaining



            # If there's already an existing branch in the new branch

            # list with the same snap group size and list of other

            # group sizes, we can combine the new probability with that

            # existing one to save size in the new list:

            for prior_branch in new_branches:

                if prior_branch[0]==branch[0] and \

                   prior_branch[1]==branch[1]:

                    prior_branch[2]=prior_branch[2] + \

                                     branch[2]

                    break

            else:

                insort(new_branches,branch)

            

    cumulative_snap_chance=cumulative_snap_chance+current_snap_chance



    print '%2u  %16.13f  %16.13f' % (card_number, current_snap_chance,

                                     cumulative_snap_chance)



    old_branches=new_branches # new list becomes the old one to work with

                              # in next iteration.



# *** End of Program ***

0 Replies

@rg123,

Fantastic! I don't know if it's correct, but it matches my simulation results. If expected value is applied to the data as shown (SUM(n*P(n))), then the result is 14.73. However, if each P(n) is divided by 0.9545237176689 (your cumulative total) to factor out the non-snap permutations, the expected value is 15.43 (what my sim came up with).

I'm a C programmer, not a Python programmer. How long does this take to run? I'll try to figure out what you're doing, but can you provide a bit more detailed explanation - perhaps an example for some card_number?

If you enjoy this kind of problem, you should check out projecteuler.net.

1 Reply

@markr,

Although I don't code in Python, I have Python installed on my machine. It runs in well under a minute. Also, I printed old_branches for each of the first few card_numbers:

1 0 0
[[1, [], 1]]

2 0.0588235294118 0.0588235294118
[[1, [1], 0.94117647058823528]]

3 0.0564705882353 0.1152941176471
[[1, [1, 1], 0.82823529411764707],
[2, [1], 0.056470588235294113]]

4 0.0530132052821 0.1683073229292
[[1, [1, 1, 1], 0.67611044417767108],
[1, [1, 2], 0.050708283313325324],
[2, [1, 1], 0.10141656662665066],
[2, [2], 0.0034573829531812724]]

5 0.0497959183673 0.2181032412965
[[1, [1, 1, 1, 1], 0.50708283313325331],
[1, [1, 1, 2], 0.12677070828331333],
[1, [2, 2], 0.0031692677070828332],
[2, [1, 1, 1], 0.12677070828331333],
[2, [1, 2], 0.015846338535414166],
[3, [1, 1], 0.0021128451380552217],
[3, [2], 0.00014405762304921967]]

6 0.0467778600802 0.2648811013767
[[1, [1, 1, 1, 1, 1], 0.34524788638859799],
[1, [1, 1, 1, 2], 0.19420193609358638],
[1, [1, 1, 3], 0.0017981660749406142],
[1, [1, 2, 2], 0.016183494674465532],
[1, [2, 3], 0.00013486245562054606],
[2, [1, 1, 1, 1], 0.12946795739572425],
[2, [1, 1, 2], 0.040458736686163829],
[2, [1, 3], 0.00026972491124109213],
[2, [2, 2], 0.0010114684171540957],
[3, [1, 1, 1], 0.0053944982248218436],
[3, [1, 2], 0.00094403718934382263],
[3, [3], 6.1301116191157308e-006]]

I see now what you're doing with the branches. I haven't checked out the probability calculation, but I don't doubt that it is correct. Great job! Check out projecteuler.net.

1 Reply

@markr,

Thanks ;-)

I was working on a response, but you beat me to it. Python's a great language for problems like this. Nice to not have to worry about memory management, etc.

1 Reply

@rg123,

By the way... "The C Programming Language" by K&R is one of my favorite programming books. (Was a C programmer for a while a long time ago - haven't really done anything with it in years.)

If you, too, like that kind of concise book and might be interested in learning Python - my favorite Python book is "Python in a Nutshell" by Alex Martelli (2nd edition is his latest, dealing with up to Python 2.5, but you could then read about the changes in Python 3000 at www.python.org).

Another favorite programming book is "Thinking in Java" by Bruce Eckel (is up to 4th edition, but earlier ones are out there free online) - that's the book that really got me to understand OO programming, but after getting used to Python, I have lost all patience for Java.

Can you answer this mathematical poseur<?

Related Topics