David Gries’ Coffee Can Problem
October 22, 2013
David Gries described today’s exercise in his 1981 book The Science of Programming; I learned it from Jon Bentley’s 2000 book Programming Pearls, second edition.
You are initially given a coffee can that contains some black beans and some white beans and a large pile of “extra” black beans. You then repeat the following process until there is a single bean left in the can.
Randomly select two beans from the can. If they are the same color, throw them both out and insert an extra black bean. If they are different colors, return the white bean to the can and throw out the black.
Prove that the process terminates. What can you say about the color of the final remaining bean as a function of the numbers of black and white beans originally in the can?
Your task is to answer the two questions asked above, then write a program that simulates the coffee can problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Pages: 1 2