logo
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.
THE ALGORITHM
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.
THE MATH
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.
RECURSION
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.
ANSWERS
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.
LISTING 1
TO BIRTHDAY.PROBLEM :PEOPLE
( PR BEGIN.SOLVING :PEOPLE 365 )
END
TO BEGIN.SOLVING :EVENTS :POSSIBILITIE
S
MAKE "PROBABILITY 1
OUTPUT SOLVE :EVENTS - 1 :POSIBILITIE
S
END
TO SOLVE :EVENTS :POSIBILITIES
MAKE "PROBABILITY :PROBABILITY * ( :PO
SSIBILITIES - :EVENTS ) / :POSSIBILITI
ES
IF :EVENTS = 0 [OUTPUT WORD 100 * ( 1
- :PROBABILITY ) "%]
OUTPUT SOLVE :EVENTS - 1 :POSSIBILITIE
S
END