Project 1, Part III

Astrological Toys

Day Finder: The Day Finder, though a small extension to the Zodiac program, is significant because it introduces a powerful algorithm, binary search, and introduces a fundamental component of algorithmic thinking, procedures.

Searching for a day. The Day Finder is an extension of the Zodiac application, in which the user is asked questions that enable the program to discover his or her birthday. So, Leo’s are known by the Zodiac application to be born between July 23 and August 22. (Remember this includes both the starting and ending dates.) The task is to formulate questions whose answers will determine the user’s actual birthday. One strategy would be to ask, "Were you born after July 23?" If the answer were "no", then the program could say, "You were born on July 23", but if the answer were "yes", the program would have to try another question, like "Were you born after July 24?" If the person were born on August 22, this strategy would take 30 questions to cover the 9 days in July (23-31) and the 22 days in August (1-22), which is actually 31 days, but we don’t have to ask about the last day, since a "no" to "Were you born after August 21" implies an August 21 birthday, while a "yes" implies an August 22 birthday.

There is a better way. The Day Finder will use an intelligent searching strategy, called the binary search algorithm. Binary search can be used on any ordered objects, like letters or the dates of a Zodiac sign. It uses a series of questions, sometimes called probes, to eliminate half of the remaining possibilities with each question. For example, suppose I’m thinking of a letter. You may ask, "Is the letter between N and Z?", a question that is equivalent to asking if it is in the last half of the alphabet. Regardless of which answer is given half of the alphabet is eliminated. The binary search for the letter "L" goes as follows:

Question Is the letter after M? Is the letter after G? Is the letter after J? Is the letter after L? Is the letter after K? The letter must be L

Ans N Y Y N Y

Letters Eliminated A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Notice three points about the example: First, the questions always ask if the letter is after the probe letter. It is possible to ask before and after questions, but always asking the same type simplifies the programming. Second, the intervals sometimes have an odd number of letters and sometimes an even number. When it is an odd number, then the middle letter is the probe. When it is an even number, e.g. H-M, then the probe is the last element of the first half of the interval. This is because of the "after formulation" of the questions. If the questions had been formulated as before questions, then the first element in the second half would be used. These choices have been made to assure that half of the interval will be eliminated when the answer is received. Third the binary search scheme requires only five questions to find any letter. Scientifically, and only for those interested in such things, the binary search takes log₂ n probes to find the answer among n items, which is the minimum. The point to remember is that this is the best way to find an item in an ordered sequence.

Finding a birthday works in the just the same way. The only complication is that the sequence of days changes months under the sign, e.g. Leo goes from July to August. This is not really a problem, however, since it is possible to imagine looking for the birthday from July 23^rd through July 53^rd. Of course, there is no July 53; that’s what August 22 would be if the month didn’t change. The 53 is how far past the end of July the Leo sign goes, which is computed by adding the number of days in July, 31, to the last day of the sign, the 22^nd, giving 31 + 22 = 53. This means that the search can look for the birthday between 23 and 53, and whenever a question must be asked about a date larger than 31, the day gets 31 subtracted from it and the month becomes August. Otherwise it is just a normal July date.

For example, to figure out the first question to ask, we find the mid point between July 23 and July 53 by subtracting the smaller endpoint from the larger:

53 – 23 = 30

and dividing by 2

30 \ 2 = 15

If the number had been odd, the 0.5 would have been truncated (or rounded down). Then this number is added to the start of the Leo sign, the 23^rd

23 + 15 = 38

which is a day in August since it is larger than the largest day in July, the 31^st. Thus, July 38 is really August 7^th, since 38-31 = 7. And, it can be checked that this is the middle of the Leo range, just by counting out the days. The result of this computation would be to ask the question:

Were you born after August 7?

which to us is July 38. If the answer is "no," then the new interval is 23 to 38. Remember, August 7 (= July 38) is still a possibility. If the answer is "yes" then the interval is 39 to 53. By repeatedly shrinking the interval we can reduce the interval size to one day, say 32 to 32. And that must be the person’s birthday.

The questions to find the birthday August 1 are as follows, where Lo is the lower end of the interval, Hi is the upper end of the interval, Mid is the computed midpoint and Size is the size of the interval.

Lo 23 23 31 31 31

Hi 53 38 38 34 32

Size 30 15 7 3 1

Mid 38 30 34 32 31

Question Were you born after August 7? Were you born after July 30? Were you born after August 3? Were you born after August 1? Were you born after July 31? You were born on August 1.

Ans No Yes No No Yes

NewLo 23 31 31 31 32

New Hi 38 38 34 32 32

Notice that when the endpoints are the same, then they must be for the birthday being sought.

Window asking the first question for the Day Finder application.

Encoding the Binary Search. The overall plan is to extend the Zodiac program by adding a procedure to make guesses, and include the other features needed to implement a Yes/No dialog to produce a program finding the user’s birthday. The guess procedure will generate questions of the form

"Were you born after <month> <day>?"

where the <month> and <day> are chosen to reduce the interval by half, as described above. The interval begins as the whole interval for whatever Zodiac sign was chosen by the user, i.e. the output of Zodiac. After Zodiac displays the interval, the program will make the first guess, and set up the Yes/No buttons for the reply. On each response by the user, the interval will be reduced, a check will be made as to whether the interval has shrunk to a length of 0, i.e. the endpoints are the same, and if the interval is nontrivial another guess will be formulated. Thus, there are three places where a guess must be made: When the interval is first defined and the computation begins, and on both the Yes and No replies.

The first step is to make a copy of the Zodiac program, and save it as the initial version of the Day Finder program. Next, the form must be enhanced by adding the "Y" and "N" buttons, the labels "Were you born after ", "Month" and "Day", all of which should be hidden during the initial operation of the program. In addition to the declared variables, loMo, hiMo, loDate and hiDate of the Zodiac program, more variables will be needed and must be declared: numDays, loEnd, hiEnd, and midPt, all integers. Declarations for these variables should be added after the declarations made for the Zodiac program. Finally, once the declarations are in, the twelve Zodiac option event handlers must be augmented to assign to the variable numDays, the number of days in their loMo month. This tells the program on what day the month changes. For example, for Leo July is the loMo, which has 31 days, so numDays = 31 must be added to Leo.

Next, you will declare a new procedure (Private Sub) named guess. (We will not use parameters, but will refer to the variables globally.) guess includes the logic to make a guess for the interval ranging from loEnd to hiEnd, inclusively. (This logic is spelled out above.) It will do this by figuring the midpoint (use integer division) of the interval and assigning the value to the variable midPt. It then looks to see which month midPt is in: If midPt is less than or equal to numDays, then the month field is loMo, but if it is greater than numDays, then the month field is hiMo. In the latter case, the day value must also be reduced by numDays. The procedure should modify the captions on the labels for the <month> and <day> fields of the question so as to present the question to the user.

The last set of changes involves calling the guess procedure. It will be called with the program text

Call guess

but the critical thing is to locate where it must be called and to set up the variables so it works correctly at each place. There are three locations for a guess call and in each case preparations must be made before the call:

1. As discussed above, guess must be called after the Zodiac program prints out the interval, i.e. the call will be from the OK command button event handler. Since this is the first call, the interval must be set up. This means the loEnd and hiEnd must be assigned the values defining the interval before guess is called. All of the other values used in the procedure should have had their values set by the revised code from Zodiac.
2. There is a call within the Yes command button event handler.
3. There is a call within the No command button event handler.

For the latter two calls, similar preparatory code must be written. First, the interval must be reduced. It will either be loEnd to midPt because the person clicked on No (birthday not after <month> <day>), or it will be midPt + 1 to hiEnd because the person clicked on Yes, (birthday after <month> <day>). Either way one of the end points will be changed. Once the end points have been changed, it is necessary to test to see if the birthday has been found. As mentioned above this case occurs when the new interval has no other days in it, i.e. loEnd = hiEnd. If the birthday is found, it is necessary to confirm to the user that the birthday has been found by typing, "You were born on" followed by the <month> and <day>. The Yes/No buttons should be hidden, just to clean things up.

That’s it. Review the following checklist to verify that you’ve incorporated all the changes:

1. Form modifications to Zodiac form, including labels for the question, <month> and <day>, and Y/N buttons. All should be invisible
2. Four new variable declarations, all integers
3. Each option button event handler must include an assignment to numDays.
4. The guess procedure declaration including logic to find the middle of the interval, testing for completion and revising the <month> and <day> of the question, or confirming that the birthday has been found.
5. A call to guess from the end of the OK button’s event handler, preceded by setting the interval initially and making the question and buttons visible.
6. A call to guess from the Y and N command buttons’ event handlers, preceded by shrinking the intervals appropriately.
7. All visibilities are set properly so that the Y/N buttons come and go when appropriate.

Your program should now run. There will likely be some bugs in the program so try it out on the Leo Þ August 1 birthday example given above, since all of the correct intermediate steps have been worked out and the relevant values shown in the table. Once that’s working, try it out on your own birthday.

Très cool, n’est-ce pas? Try it out on your roommate and friends. Look on as they become mesmerized, repeatedly asking Day Finder to locate some birthday, dumbfounded that it always finds the answer in 5 questions and amazed at how effortlessly it navigates back and forth across the month boundaries. Please do not reveal our secrets to them. If the public finds out how easy this stuff is, everyone will be doing it and programmers’ salaries will go into the toilet. Not good.

And here's a sample executable that you can tinker around with if you'd like.