(c) Copyright 1996, Joseph Bergin. All rights reserved.

The Object Is Computer Science-- C++ edition

Joseph Bergin

Chapter 8 Projects

8.1 The Vending Machine

A vending machine accepts money and distributes products of vairous kinds. It has the following parts:

A vending machine has a cash slot that accepts nickels, dimes, and quarters. It also has a cancel button, which returns any money inserted but not applied to any product.

A vending machine has a front panel that associates product names/descriptions, prices for the products, and internal vending slot numbers. It accepts choices for product by name and causes vending of the product provided sufficient money has been inserted.

A vending machine has a chooser that associates vending slot numberes with the actual slots that contain the product.

A vending machine has several vend slots that contain the product. Each has a fixed capacity, which may vary depending on the product, and accepts commands to fill the slot and to vend one item of product.

A vending machine has a change maker that gives back correct change in nickels, dimes, and quarters. It always gives back the minimum number of coins from among those it currently has available. If the change maker cannot guarantee to give back change for a purchase it goes into "exact change mode" in which it requires exact change from a customer.

A vending machine has a cash box that holds nickels, dimes, and quarters.

A vending machine accepts commands from a customer. In a real vending machine these would be connected to physical devices. In this simulation you will need a command driven front end. A simple possibility for comands follows. Feel free to design and build a more elaborate one.

N - put in a nickel
D - put in a dime
Q - put in a quarter
X - cancel the purchase
C productName - choose a product to purchase
R - print a report
. - finish the simulation

8.2 More on the Vending Machine

Add a dollar bill facility to the cash slot. Refuse to accept dollar bills if there is no way to make change for some possible purchase, since once a dollar bill is accepted it cannot be returned.

Have the vending machine "call its home office" when it needs servicing. It needs servicing when its ability to vend or to make change is impared for any reason. Note: some vending machines are, indeed, connected to phone lines and do call for servicing.

8.3 The Post Office Box

The post office has a large number of numbered boxes. Each can hold letters. Larger boxes can hold parcels as well. Each box has an owner. Owners may own more than one box. A box may have more than one owner. Only an owner may retrieve items from the box.

Letters and parcels are addressed to people at box numbers. They are inserted into a box if the name and the number are correct. If the name and number do not correspond to a box, but the customer name is known, then the item is inserted by name If the customer name is not known, then the item is inserted into the box it is addressed to. Some items arrive with only a name or a box number. These are inserted accordingly.

People may pick up their mail or they may have it forwarded to another post office.

8.4 Probability Distributions

The simple uniform distribution provided by dice can be used as the basis of more complex probability experiments. For example, the sum of two identical uniform distributions (The sum of rolling two identical dice) is called the binomial distribution. We can also use the uniform integer distribution to obtain a fairly good uniform real distribution over the interval 0...1. Any positive valued function over an interval may be used as a probability distribution provided that the area under the curve over the interval is exactly 1. The probability that a random variable "sampled from" the distribution falls between two values is just the area under the curve and between vertical lines through the two values. This is the definite integral of Calculus.

Given a uniform distribution over (0,1) we can easily get uniform distributions over any interval by scaling. If r is uniform over (0,1) then (r * (b - a) + a) is uniform over (a,b).

Many important distributions are not uniform. The exponential distribution with mean m describes random arrivals of bank or post office customers in whch the average time between arrivals is m. It depends on the arrivals being independet of each other. It might be suspect in a restraunt where customers arrive in groups, though it would probably measure time between arrivals of groups quite well. Exponentially distributed numbers can be generated from a uniform (0,1) distribution, r, by computing -m.ln(r). The natural log function, ln, is available in <math.h>, but it has name log. Given the time of arrival of one customer, this will give you the arrival time of the next. Recall that the log of numbers between 0 and 1 are all negative.

8.5 The Post Office

The post office has one or more service windows (may be quite a few in larger offices). Customers arriving stand in a single line until one of the windows is free to serve them. The free window takes the customer at the head of the line. Customers arrive at varying times and rates, depending on time of day. Customers may buy stamps and may post letters and parcels. These transactions take short, but varying amounts of time. Box holders may forget the keys/combinations to their boxes and go to a window to retrieve the contents of their boxes.

Customers don't like to spend more than 10 minutes in line. The post office doesn't like to have more windows open than necessary.

8.6 Polynomials

Polynomials should really be a template so that we can specify the kind of data that we insert. They shouldn't be restricted to doubles.

8.7 Fractions

Fractions have a numerator and a denominator. The denominator is never zero. A fraction is in lowest terms if the numerator and denominator have no common factors and the denominator is positive. Fractions can be added, subtracted, multiplied, and divided. They can also be read and written. Use the form < n, d> to write a fraction, where n is the numerator and d is the denominator and the fraction is in lowest terms. It is an error to try to create a fraction with a zero denominator or to try to divide by zero. An integer should be considered to be a fraction with 1 as the denominator. A fraction should be convertable to an equivalent double, or to an integer, either by truncating to the next smallest integer, or by rounding to the closest integer.

8.8 Fraction Polynomials

Test polynomials that have fractions for coefficients.

8.9 Complex Numbers

Complex numbers have a real part and an imaginary part. Both of these are doubles. A complex number can be written (r,i) where r is the real part and i is the imaginary part. The number (0,1) has square -1. Yes, negative one. We add and subtract imaginary numbers by adding and subtracting their corresponding parts. We multiply imaginary numbers using a distributive law: (a,b) * (c,d) = (ac - bd, ad + bc). If zero is the imaginary part then the number is just a double. If zero is the real part, then the number is "pure imaginary". If we let the pure imaginary number (0,1) to be represented by the letter i, then (a,b) is consistent with a + b*i) according to the above rules of addition and multiplication. Notice that (a+bi) * (a-bi) = a2 - b2. If this latter quantity is denoted by r then 1/(a+bi) = (a/r) - (b/r)i. Division can then be defined in terms of multiplication by such a reciprocal.

Complex numbers can be graphed on a two dimensional grid where the horizontal axis is used for the real part and the vertical axis for the imaginary part.

8.10 Complex Polynomials

Test polynomials that have complex numbers as coefficients.

8.11 The Game of Life

Life is "played" on a board that is a two dimensional array of cells. The cells may be in state alive or dead. The game progresses through stages. The state of a cell in one stage is determined by the states of its eight nearest neighbors in the previous stage. If a cell has exactly three or four live neighbors in one stage it will be alive in the next. Otherwise it will be dead in the next stage. One way to play Life on a computer is to use two boards and alternate between them so that they represent alternating stages. One way to have two boards is to have an array of two boards. It is helpful in this case to notice that if i has value 0 or 1 then 1-i will have the opposite value.

8.12 Freebles

Freebles live on a rectangular array of cells. Freebles come in several varieties and which variety they are determines several things about them, including how they move. Some of the types are described as follows. Lurkers don't move at all. Stay_at_homes only wander around a small area. Prowlers cover all of the cells eventually moving in some determined pattern. Drunks wander randomly. (Or maybe they are philosophers wandereing aimlessly.)

When exactly two Freebles meet on the same cell they reproduce a third on that cell. If too many (more than three?) Freebles occupy a cell at the same time they have a war and all die. One unanswered question is what kind of Freeble is born when two Freebles of different kind meet. If attributes are determined numerically then this is easier to handle. It should also be possible for some attributes to reinforce in offspring of similar parents.

Are there some kinds of Freebles that tend to have growing populations and others shrinking? What kinds of attributes might be most likely to be passed on to offspring?

Can freebles be give any sensory organs? Can these be attributes passed on in different degree? Can Freebles be given any tasks to accomplish? Any tasks that might be harder or easier depending on their attributes? Are there other objects in the world that Freebles can manipulate, or collect, or eat, or ....?

8.13 Mancala

Mancala is an African game of strategy that is played with pits and pebbles. There are two players. The board has two rows of six pits each, plus a larger pit at each end; the Mancalas. The goal of the game is to collect the most pebbles in your own Mancala. The game starts with four (or five, or six) pebbles in each of the regular pits. Each player has a row of smaller pits in front of them and the Mancala to that player's right. On a turn a player picks up all the stones in one of their own pits and distributes them into consecutive pits moving to the right (counterclockwise), including that player's own Mancala, but not the opponents. If a player's last pebble lands in her/his Mancala, she/he gets another turn. If your last pebble lands in one of your own empty pits then that stone and all of the stones in the opponent's opposite pit if any are captured and placed in your Mancala. The game ends when one player has no pebbles to play. The other player then automatically captures all pebbles remaining on their own side. The player with the most pebbles wins. Other variations of the game are possible. Sets and Arrays might be used to develop a computerized game. You might try to let the computer play one side and develop a strategy for the computer to play.

8.14 Random Haiku

Haiku is a Japanese poetry form that has very rigid rules of structure. This makes it difficult to write, but easy to computerize. You can keep lists (or Arrays) of words of various kinds; nouns, verbs,... and then select randomly to fill in slots of the required kind in a form. Quite interesting effects can be achieved if you choose good words for your word lists. It ought to be easy to add words, and it ought to be easy to save the words to a file for restoration when running the program again. Limericks are another form that might be handled in this way, though Haiku, depending on subtlety for its major poetic effect, actually works better.

8.15 Fortune Cookies

You may have gotten fortune cookies that did not use perfect English, since they may have been translated from other languages, by translators with an imperfect knowledge of English. A computer could probably write such fortune cookies given a vocabulary and some rudimentary rules of English. The results could be quite amusing.

8.16 99 Bottles of Beer on the Wall

When I was a kid we sang a song:

99 bottles of beer on the wall, 99 bottles of beer.

If one of those bottles should happen to fall:

98 bottles of beer on the wall.

98 bottles of beer on the wall, 98 bottles of beer.


It drove our parents crazy, I think, but they probably sang it themselves. Did you? I'm not sure we ever finished it. With a computer, it is easy to finish. How short a program can you write for this song? Use total tokens as your measure of shortness, not characters. Each identifier (variable name, etc.) counts as one. So does each built-in symbol such as while, {, and &&.

8.17 Self-Replicating Programs

It is possible to write a program that, when run, produces an exact copy of itself. It does not do this by reading a copy from the disk. It embeds a copy of itself within itself that it write to cout. Such a program can be surprisingly short. Such a program can also contain any arbitrary text or code that you like. This is actually the theoretical basis of computer viruses.

8.18 Other Games

Other games you might be familiar with could be computerized. Many of these are trademarked and copyrighted so there are strict limitations on what you can legally do with such a program. Chutes and Ladders. Monopoly. Trivial Pursuit. Risk. Battleship. Checkers. Backgammon. Go. Use your own imagination and interests. You might even be inclined to design your own game.

8.19 Personal Database

Build a database of names and phone numbers. To be useful, the storage must be permanent. It should also have a nice interface so that users find it easy to insert and update information. Some databases use the idea of a "current" record that is the focus of update. This might make it easier to change information already in the database. Add addresses as an additional field.

8.20 Ant World

Ants live in a world populated with food and, perhaps, other things. Explore this and expand it. Ants can be given energy levels and these can deplete with time and action, requiring them to find food.

8.21 Mazes

Walls can be added to the ant world. Ant's don't walk through walls. They must go around them. Walls occur between coordinate positions. A one unit wall can be put to the left or below any coordinate. These sections can be used to build long walls and even mazes. Ants can be given a sensory organ to sense a wall in front of them. Then they can be taught how to walk a maze to find the exit, or to find food in the center.

8.22 Shortest Path

A graph can be used to represent a transportation network. The nodes represent cities and the arcs represent roads between them. Each road is marked with its length, the distance between two cities along that road. If two cities are not conneced directly by a road it can be a difficult problem to find the shortest path between them. Backtracking can be used.

8.23 Spelling Dictionary

A big-long list of words is very useful; especially if alphabitized (sorted). One way to get one is to take a long text, reduce it to one word per line, sort the lines, and then remove duplicate lines. The result can be used as a spelling dictionary. Binary search can aid lookups. You can also play a game with it. In the children's game Letter Ladder, one person thinks of a word and gives the first letter. The next person thinks of a word that starts with that letter and gives the second letter. The next person thinks of a word that begins with the first two letters given and gives the third letter. You lose if you can't extend the word. A computer with a spelling dictionary would be good at this game, especially if it inserts the new words into the dictiionary whenever it loses.

8.24 Send + More = Money

The above is a coded message. The letters stand for digits. Solve it.

8.25 Cards

You have 16 cards; the aces, kings, queens, and jacks of each of the four suits. They are to be arranged so that each row and each column contain exactly one card of each suit and one card of each rank. Find a solution. Find all solutions.

8.26 Card Games

In Blackjack you are dealt cards until you decide to stop. The goal is to get as close to 21 as possible without going over. Face cards count 10. The ace counts as 1 or 11. Other cards count their face value.