Problem Description
Coach
Ed
McGraw, USA Olympic tennis coach visits the famous Dr. Ecco with a problem:
"Yesterday my top-ranking tennis team members were all injured in a freak plane accident. They will recover soon, but I need to prepare substitutes for tomorrow to play England's team. I know who the 8 players of my substitute team will be, but I must rank them in a day."
"So far, I've been able to get only one court to play on. I want to set up singles matches of one hour each among the players in such a way that I can figure out who is best, who is second best, and so on for all 8 players.
I was going to use an old fashioned tennis ladder, but that always seems to take a week or so to sort itself out. I need to do it all in 20 hours. Dr. Ecco, can you tell me what to do?"
Ecco though a few moments. Then he asked "May we assume that if player X beats player Y and player Y beats player Z then X would defeat Z if they played?"
"Well, that's not always true, but if you need to, then assume it. Also you should know that the players are all in good shape and any one of them is capable of playing a few matches in a row."
"Well, then Mr. McGraw, I've got good news for you. You can rank your eight players from best to worst in less than 20 hours, provided that each match lasts just one hour. Here's how."
Can you figure it out?
Background & Techniques
This puzzle is from "The Puzzling Adventures of Doctor
Ecco", Dennis Shasha, Dover Publications. It's an
excellent book with some thought provoking puzzles. This is
one of the simpler ones, but if you find it too simple, there are
variations of this puzzle as well as 37 others in the book.
The single court problem is essentially a sorting
problem. How can we sort 8 items in the minimum number of
comparisons? The auto-solve technique I implemented here
uses a merge sort. The trick is to rearrange the 8
players into 4 ranked groups of 2 players each, (four games), then
merge them into 2 ranked groups of 4 players each (at most 6 more games),
and finally merge the two groups into a single ranked list which will
require at most 7 more matches.
Playing the puzzle is straightforward.
Select one player, labeled "A" through "H" from each of
the two rows and the results of that game are displayed.
Continue until all players are ranked. A display on the right
side of the form simplifies the task by showing you an optimized list
of the ranks that have been determined so far.
Three buttons , "Solve",
"Restart" and "New Players" have functions that I'm
sure you can figure out without additional explanation from
me.
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to
download executable version of the program.
Programmer's Notes
The program assigns secret rankings randomly to
the eight players initially and whenever the :"New Players"
button is pressed.
I had assumed that the "SolveBtnClick"
procedure would be the most complex part of this program,. But that
turned out not to be the case. I created an array of string
lists and use them to contain ranked lists of player
"names" (the letters "A" through
"H"). We start by putting each single letter in a
list. We can treat this as 8 ranked lists each containing one
member. The objective is make successive passes through the lists,
merging pairs of lists so each pass cuts the number of lists in half and
double the size of each list. Three passes are enough to
convert the eight lists with one member each down to one list with eight
members.
Each pass selects successive pairs of lists and
passes them to the Merge procedure along with the name of an output
work list to contain the merged lists. After clearing the
output list, Merge works like this:
- If either list is empty, go to Step
3. If both lists have members, compare the first member of
each list. Merge does this by calling function Beats
with the two member names . Beats compares the
"secret" ranking score of each and returns true if the first
member passed is the winner.
- The winner of the two members is added to the
output list and removed from the input list where it resided. Go To
step 1.
- When either list is empty, move all remaining
members in the other list to the end of the output list.
That's about all there is to
that I call the SolveBtnClick routine with a
"NoShow" flag set whenever a new set of players is
assigned so that when the user complete a match I'll be able to compare his
score to the minimum score achieved by the program.
The most complex part of the program turned to be
procedure Showranks, the routine that updates the rankings display
as the user defines each match. Integrating the results of a new game
into known rankings requires several passes through the know ranking
grids. For example, if the new winner is at the right end of a
ranking grid, we can just tack the new loser on to the end of that
list. Similarly if the new loser already exists at the
left end of a grid (he is the best of that set of players), we can just
insert the new winner at the beginning of that grid.
There are a couple of other tests that I developed through trial and error
to simplify the lists - see the source code for details. The final
pass after each match deletes any grid that is already contained in another
grid.
The 500+ lines of user written code here are
enough to put this program into the "Advanced"
category. But about 400 of them are straight
forward. Have a look.
Running/Exploring the Program