The Coach's Dilemma

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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:

  1. 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. 
  2. 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. 
  3. 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 

bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

Could we rank the players in 6 hours if we had four courts available?
What is the minimum number of matches if unlimited number of courts were available?
What if we allow other numbers of players?
I tried to an Updatedisplay routine  in SolveBtnClick processing to show viewers how the sort merge was proceeding.   The end result was confusing to me, and I knew what was supposed to be happening!  So it's commented out.   But there should be a way to animate the process by way of explanation.   Maybe little animated sprite guys that would sit in rows and columns of chairs based on their current rank, then run out to the court and play a few seconds before assuming their new ranking seats.

 

Original Date: May 11, 2003 

Modified: February 18, 2016

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.