SOLVING PUZZLES WITH LOGO
Probability calculations made easy
by ERRIC SOLOMON with CHARLES JACKSON
Short puzzle-solving routines in Logo that demonstrate this language's logical analysis power. The program runs on all Atari computers, and requires the Atari Logo cartridge. Antic Disk subscribers, LOAD "D:BIRTHDAY.LGO then follow the instructions in the article.
If 25 people are in a room the chance is 56.78% that at least two of
them have the same birthday.
Puzzles like this are ideal exercises for the Logo programmer.
When solving a brain-twister with a computer, you should try to see it from at least three different perspectives. Look at the word puzzle as a problem in logic, then as a problem in math, and finally as a programming problem.
To define your word puzzle in logical terms, it's helpful to match all the information you know against the added information you will need for solving the problem. Use any patterns, trends or relationships you can discover to create an algorithm for the word problem. An algorithm is a logical set of steps you must take to solve a problem.
Use your algorithm to design a set of equations which will define your word puzzle mathematically. Finally, translate these equations into Logo procedures which your Atari can execute.
We'll use the Birthday Puzzle and Logo to illustrate each of these steps.
We know there are 25 people in the room, and that there are 365 days in a year (leap days are ignored). Since it is likely that a small group of people will have a wide range of birthdays, we'll first calculate the chances of at least two people having different birthdays. We'll subtract this result from one to find the probability of at least two people having the same birthday.
Next we'll break the problem down into smaller pieces, and define each piece with an equation.
Consider a room with one person standing in it. We are certain that nobody else in the room shares this person's birthday-nobody else is there. The birthday could occur on any one of the 365 days in the year. Mathematically, this probability can be represented by 365/365.
Now consider a room with only two people standing in it. The first person's birthday occurs on one of the 365 days in the year. If the second person's birthday is to be different, it can only occur on one of the 364 remaining days. In other words, the chances of two people having different birthdays is 364 out of 365. We can numerically represent this as 364/365 x 365/365.
If a third person's birthday is to be different from the rest, it can only occur on one of the remaining 363 days. The probability of the third person's birthday being different from both the first person's birthday and the second person's birthday is represented by 363/365 x 364/365 x 365/365.
When a fourth person enters the room, only 362 "unclaimed" days remain. Our probability becomes: 362/365 x 363/365 x 364/365 x 365/365.
This can be abbreviated as:
(365!/361!)/(365 to the 4th)
And we can make a general equation for N people as folows:
365!/(365-(N-1))!/(365 to the (N-1))
Again, this equation calculates the chances of at least two people having different birthdays in a room of N people. Subtract this value from one to determine the chances of two people having the same birthday in a room of N people. So our final equation becomes:
1-365!/(365-(N-1))!/(365 to the (N-1))
THE LOGO PROGRAM
We'll write three short routines to solve the Birthday Problem: an input procedure, an initializing procedure, and a procedure which solves probability equations. We'll call our procedures BIRTHDAY.PROBLEM, BEGIN.SOLVING and SOLVE.
To use the procedures, type in the listing at the end of this article with the Logo cartridge. Call the BIRTHDAY.PROBLEM procedure by typing the name of the procedure, followed by the arguments (numbers) required by the procedure. For instance, type BIRTHDAY.PROBLEM 25 to determine the likelihood of any two of 25 people in a room having the same birthday.
To use PROBLEM.SOLVING, you must type PR (or PRINT) before the name of the procedure, and follow the name with two numbers. See the examples at the end of this article.
The first procedure, BIRTHDAY. PROBLEM, accepts the variable PEOPLE, which represents the number of people in the room. Then, BIRTHDAY.PROBLEM calls the BEGIN.SOLVING procedure and tells it the value of PEOPLE along with the number 365, the number of days in the year.
BEGIN.SOLVING accepts these two values, and assigns them to the local variables EVENTS and POSSIBILITIES. The value once stored in PEOPLE is now contained in EVENTS. And POSSIBILITIES contains the number 365.
Then, BEGIN.SOLVING initializes the global variable PROBABILITY to one, and decreases the value of EVENTS by one. Finally, BEGIN. SOLVING calls the SOLVE procedure and tells it the values of EVENTS and POSSIBILITIES.
SOLVE uses these two values to solve our probability equations. Since Logo doesn't have a factorial function, the SOLVE routine must be used over and over again until it arrives at an answer. For example, after our first trip through SOLVE, the value of PROBABILITY is 341/365. After the second trip, the value becomes 341/ 365 x 342/365, and after the third, the value becomes 341/365 x 342/365 x 343/365.
Just as a procedure can call another procedure-it can call itself. This call forces the procedure to run itself over and over again, until another instruction tells it to stop. The process of a procedure calling itself over and over again is called "recursion." SOLVE is a recursive procedure, and calls itself in the fifth line.
SOLVE keeps calling itself until the value of EVENTS is zero. When this happens, the value of (POSSIBILITIES -EVENTS)/POSSIBILITIES is equal to one, and our modified factorial routine is complete. The result is subtracted from one, and printed on the screen.
BEGIN.SOLVING and SOLVE may be used with many other probability calculations, such as these two dice puzzles:
1. If you threw three dice, what are the odds that at least two would match?
How to Solve:
We know that a die has six sides, and we have three dice. We'll use our BEGIN.SOLVING procedure, and type:
PR BEGIN.SOLVING 3 6
2. Suppose a twelve-sided die has a different number on each face. If you threw four of these dice, what are the odds that at least two would match?
How to Solve:
Each die has twelve sides, and we have four of these dice. Using BEGIN. SOLVING, we'd type:
PR BEGIN.SOLVING 4 12
Take the time to thoroughly examine your word puzzle before writing a Logo program to solve it. Remember that there are many routes you can take to arrive at a correct answer. Selecting the most direct route is a key to efficient programming.
If you don't have an Atari Logo cartridge but have worked up a curiosity about these puzzles anyway, here are the answers ...
Three-dice problem: 44.44% Four-dice problem: 42.71%
Erric Solomon started programming with Logo at the age of 8. His aunt was on the MIT team that developed the Logo language and he was one of their earliest "guinea pigs." Currently he's the California consultant for Montreal-based Logo Computers Systems Inc., which produced Atari Logo and other microcomputer Logo translations.
TO BIRTHDAY.PROBLEM :PEOPLE
( PR BEGIN.SOLVING :PEOPLE 365 )
TO BEGIN.SOLVING :EVENTS :POSSIBILITIE
MAKE "PROBABILITY 1
OUTPUT SOLVE :EVENTS - 1 :POSIBILITIE
TO SOLVE :EVENTS :POSIBILITIES
MAKE "PROBABILITY :PROBABILITY * ( :PO
SSIBILITIES - :EVENTS ) / :POSSIBILITI
IF :EVENTS = 0 [OUTPUT WORD 100 * ( 1
- :PROBABILITY ) "%]
OUTPUT SOLVE :EVENTS - 1 :POSSIBILITIE