I love puzzles and small little programming projects. When you can combine those two at get a project that you can use for a good learning/teaching experience it is just a bit of gold. When the concepts you can get into the project go beyond programming so much the better. And I think I have found one of these nuggets. About a week ago someone sent the following puzzle to a mailing list I am on.
You walk into a casino and discover that they are offering an exciting new game called 52-Card Match, which is played with two ordinary 52-card decks of playing cards. The player is handed one deck, and the dealer takes the other. The dealer thoroughly shuffles his deck and sets it face down in front of you. You can shuffle your deck as thoroughly as you please and then also set it face down in front of you. The cards are then turned over one at a time from each deck, i.e. one from each deck is turned over simultaneously each time. If any pair matches exactly (rank and suit), the game is over and the casino wins. If you make it through the whole deck without a match then the player wins, and is paid out at 2:1 odds. Should you play this game? What would fair odds be?
You walk into a casino and discover that they are offering an exciting new game called 52-Card Match, which is played with two ordinary 52-card decks of playing cards.
The player is handed one deck, and the dealer takes the other. The dealer thoroughly shuffles his deck and sets it face down in front of you. You can shuffle your deck as thoroughly as you please and then also set it face down in front of you.
The cards are then turned over one at a time from each deck, i.e. one from each deck is turned over simultaneously each time. If any pair matches exactly (rank and suit), the game is over and the casino wins. If you make it through the whole deck without a match then the player wins, and is paid out at 2:1 odds.
Should you play this game? What would fair odds be?
Now there is surely a good mathematical way to figure this out. No doubt it would make a great project for a class in statistics. But I’m a programming guy. I did take statistics in college – two or three courses of it – but it’s been 35 years and I haven’t kept up with it. What I do know how to do is simulate the game. So that is what I did. Basically what I did (rough outline) was this:
The results surprised me. Surprised me a lot. In fact this morning I had to take out two decks of real cards and try it in real life. Simulation and real life had the same sort of results. Makes one feel good when that happens.
I think this might be fun for students as well. And of course you have arrays (parallel arrays probably but maybe a two dimensional array if you want), loops, and the ever popular random numbers. The math/statistics involved are potentially interesting as well because you can compare the expected results with what you see in the simulations.
For added fun (and complexity) you could keep track of how many times there was a match in each run of the deck comparisons. Perhaps there is a variation (you have to match three or more times to lose for example) you could find that actually makes more sense to play? Get the kids in AP Statistics to do the math for you and compare their results with the simulation.
For a small experiment it matters little but for real card shuffling algorithms see en.wikipedia.org/.../Shuffling. Its very easy to make an algorithm mistake and end up with a statistically unshuffled deck. Very important if you want to start your own poker site.
Look at Alfred's Step # 1 -- "Create two 52 element integer arrays and fill them with the integer values 1 through 52."
Alfred -- You wrote that down pretty quickly. But I think it's the most critical step for those who teach CS !!
Step back and think --> Is Alfred's data structure a reasonable choice for this problem? Why? Could you explain why to your K-12 students?
We are all "math people" and "CS people", so we often take this data modeling for granted. But in reality...understanding this is a HUGE LEAP for many of our students, especially at the K-12 level. In fact, if we can use CS to teach our students to understand and model problems correctly (reducing them to simpler problems and representations), then I'd argue this is the BEST REASON WE SHOULD BE TEACHING CS TO ALL K-12 STUDENTS !! What incredible "real world" skills we'd be teaching, that can be used in all areas of our studies, our work, our lives, etc. !! Who says CS isn't relevant ? Who says it's just for geeks? :-)
We say we want our students to have "mathematical literacy" ! Absolutely! That means, in Alfred's problem, they should be able to tell us...
...why it's ok to represent a real deck of cards (with rank and suit) using just the integers 1-52?
...why the rules OF THIS PARTICULAR GAME allow us to do this.
...why if the rules were slightly different, THE SAME DATA STRUCTURE WOULD NOT WORK !! For example, what if the cards needed to match only on rank and color, but not suit ? (For example, what if the 6 of Diamonds was considered to "match" the 6 of Hearts?). Then Alfred's 1-52 representation wouldn't be sufficient !
The real value of teaching Computer Science, I argue, is not about teaching students to use technology ! Rather, it's about teaching students to understand and model problems, so they can simplify the problem into its basic, truly important elements to solve it.
If we're not teaching this, then I agree with those who say that CS isn't valuable for all kids to learn -- we should only be teaching it to those who will be future programmers.
Charley you are right. And on of the things I would love to have happen if for people, especially teachers and students, discuss if this is the right data structure. As someone who is an old school (almost 40 years of programming) programmer it is what comes to my mind first. That does not automatically make it right. In fact there are all sorts of things that a project like this could lead to discussion about. That is one reason I included no code samples.
I totally agree -- Discussions on "different ways to solve the problem" are great for students to participate in.
I loved this blog post -- very interesting problem and can open doors to some great classroom ideas. (...and captures some of the best reasons for teaching this subject!)
introducing arrays to my 11th grade programming class this week. think I'll use this one for homework.
I love how I can recreate the scenario in real life with two ACTUAL decks of cards and ask them to make an assumption, and then defend their decision with a computer simulation that will calculate a large amount of data faster than we could test it.
thanks for sharing!
Ben, please let me know how it goes with your students. I would to share ideas of what works well and what doesn't work as well. Thanks
Alfred, here's my follow up post.
My class consists of 3 students. Two high school juniors with NO programming experience and one sophomore who has memorized a few DOS commands, but is still unable to articulate the concepts behind programming. After the first week one of the juniors asked "What is code?" :D
We've dabbled with www.yoyogames.com/gamemaker and are now using www.justbasic.com I really want them to understand the concepts before we jump into Visual Basic. I make them flowchart their programs and even act out the program (think of the classic Hi/Low number guessing game).
This will be an easy enough program for them to write using arrays and random functions. It also illustrates the power of computers apart from graphics.
is there anywhere on here to get the solution to see if i have done it correctly?
Oliver, what result did you get?
I gave this to my senior class 3 class periods ago (3 X 1.5 hour periods ago). The assignment I gave them required that there be a visual representation of the cards flipping and keeping track of the matches. The first period consisted of finding cards on the internet and making a file of them. The second period was spent making a cool GUI and menus. The first two periods do not sound productive but if the kids cannot have fun with a project like this it is not worth the time. Third period we discussed shuffling cards and possible algorithms. They then hit the internet looking for card shuffling algorithms. They found several, modified one to suit and ended up with a program that does the deed. What had me worried initially was the cut and paste approach to programming. Would they really understand the card shuffling if they are just going to paste and pray? No problem. The shuffling procedure they used required modification so they had to tear it apart and rebuild it. An excellent learning exercise. Now they each have a program with a large button that they click to flip individual pairs of cards. It took them all of a half hour to write the major part of the code. I have changed the problem on them now (kind of like the client asking for a product modification). How many pairings in n decks of cards? The button press per card is not going to work quite as well. I still want the simulated card flipping, but now it will be very fast with a brief pause at a match. Each new set of decks will require a “re-shuffle” in a manner of speaking. This kind of program is much more interesting to them that the coffee shop point-of-purchase type programs the present book has them writing.
Garth, that is great stuff! I love the way you added to make it more visual and more interesting for the students. Thanks for sharing what you have done.