Wrox Home  
Search
Puzzles for Programmers and Pros
by Dennis E. Shasha
May 2007, Paperback
US $24.99 Add To Cart


Excerpt from Puzzles for Programmers and Pros

Can You Solve this Strange Slot Machine Puzzle?

by Dennis Shasha

Puzzles as an interviewing tool have many detractors. Criticism often comes down to the implausibility of a puzzle scenario in which, say, a perfectly logical person is mute and refuses to write. Now, I admit to having written such puzzles, but most of my puzzles come from real problems (e.g., occasionally failing hardware being modeled by occasional liars). In my own research, I try to abstract the problem at hand to a puzzle, in the hopes that I can understand the fundamental issues and take care of the window dressing later. It works pretty well. So, to me, puzzles, especially the right kinds of puzzles, provide a tunnel into scientific and engineering insight.

To illustrate this point, let's take a trip to a strange casino. The casino has a special slot machine with five wheels. One has four different values. The others have three each.

wheel 1: apples, cherries, grapes, pears
wheel 2: cherries, grapes, pears
wheel 3: apples, grapes, pears
wheel 4: apples, cherries, pears
wheel 5: apples, cherries, grapes

In this machine, the player sets the wheel values then pulls the lever. If it's a winning combination, the payout is $500. Each pull of the lever costs $10. The winning combination depends on only three wheels. You don't know which three, but you know that the first wheel is one of them. If you are lucky enough to find the correct values of the correct three wheels, the values in the remaining two wheels don't matter. For example, suppose the winning combination is apples on wheel 1, grapes on wheel 3, and pears on wheel 4. If you set those values correctly, then the values on wheels 2 and 5 can be anything at all and you will receive the payout.

Warm-Up

The house changes the winning combinations after either 50 attempts or a payout, whichever comes first. If each attempt costs $10 and the payout is $500, can you make this into a good game for the player?

Solution to Warm-Up

In order to understand how to go about solving this problem, realize first that there are nine winning combinations since there are nine possible settings of the remaining wheels. The total number of combinations of all wheels is 4 × 3 × 3 × 3 × 3 = 324. So the odds of winning are 9/324 = 1/36. Because each pull of the lever costs $10 and the payout is $500, this is a good bet. That would be true even if the winning combination were changed after every attempt.

In fact, the odds are better than this, because each attempt reduces the search space. This increases the odds just as your chances of winning increase as the deck empties in black jack, if you keep track of the cards thrown.

Notice that you want to combine each value of wheel 1 with every pair of values of every pairs of other wheels. For example, if the order of these fruits correspond to wheel numbers, then the three lever pulls

1,apples,pears,apples,pears,apples
2,apples,cherries,apples,apples,grapes
3,apples,grapes,apples,cherries,cherries

correspond to setting apples for wheel 1 and then testing all other wheels against apples for wheel 3. At the same time, we have tested pears vs. pears, cherries vs. apples, and grapes vs. cherries for wheels 2 and 4. So we can test many wheel-to-wheel pairs with just a few lever pulls.

If you replace wheels by function points and fruit by parameter settings, you might observe that this is a technique for testing five function points such that for every setting of the first function point and any pair of settings of two of the other function points, you have found a test. The idea is that even if you don't test the full search space, perhaps you can be systematic in some sense at least. (I myself have used this idea in work with biologists.) Ok, enough blah-blah.

Can you absolutely guarantee to win in 36 lever pulls

Have fun and good luck.