David Gries’ Coffee Can Problem
October 22, 2013
Each time you reach into the coffee can, you remove two beans then put one in, so the number of beans in the can is reduced by one and the process must eventually terminate when one bean remains. Since either zero or two white beans are removed each time you reach into the coffee can, the even/odd parity of the number of white beans never changes, so the final remaining bean is white if and only if there were initially an odd number of white beans in the coffee can. Here is our simulation:
(define (coffee b w)
(if (and (zero? b) (= w 1)) 'w
(if (and (zero? w) (= b 1)) 'b
(if (and (zero? b) (= w 2)) 'b
(if (and (zero? w) (= b 2)) 'b
(if (and (= b 1) (= w 1)) 'w
(let* ((one (if (< (randint (+ b w)) b) 'b 'w))
(b (if (eq? one 'b) (- b 1) b))
(w (if (eq? one 'w) (- w 1) w))
(two (if (< (randint (+ b w)) b) 'b 'w))
(b (if (eq? two 'b) (- b 1) b))
(w (if (eq? two 'w) (- w 1) w)))
(if (eq? one two)
(coffee (+ b 1) w)
(coffee b (+ w 1))))))))))
We handle all combinations of two or less beans as special cases because the main calculation in the let* accesses two beans. Here are some examples:
> (coffee 5 8)
b
> (coffee 5 7)
w
We can demonstrate both that our code is correct and that our statement about the color of the remaining bean is correct by testing all combinations of up to 50 beans:
> (do ((b 1 (+ b 1))) ((= b 50))
(do ((w 1 (+ w 1))) ((= w 50))
(if (even? w)
(assert (coffee b w) 'b)
(assert (coffee b w) 'w))))
>
The test prints nothing, on the theory that no news is good news. We used randint and assert from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/qEpegqCq.
Programming Praxis 
A solution in Racket and a proof by induction in “engrish”:
#lang racket #| Let 'n' be the number of beans in the can. For n = 1, the process terminates, as there is only one bean. For n = 2, there are three possible cases: a) Both beans are black, b) both are white, c) one is black and the other white. For a) and b), both beans are thrown away and a new one is inserted. As n was 2, now n = 1 and so the process is finished. In case c), we return the white bean to the can and throw away the black bean. Now, there are n = 1 beans in the can and the process terminates Now let n = k for some k > 2 and assume that for n=k-1 the process terminates. As in the case for n = 2, there are three different cases: a) and b) where both beans are of the same color, c) when they are of different colors. In both cases, we end up with n = k-1, and by the induction hypothesis, the process finishes. |# (struct can (p q)) (define (select-bean c) (match-define (can p q) c) (define x (random (+ p q))) (cond [(> x p) (values (can (sub1 p) q) 'black)] [else (values (can p (sub1 q)) 'white)])) (define (select-pair c) (define-values (c1 a) (select-bean c)) (define-values (c2 b) (select-bean c1)) (values a b c2)) (define (insert-bean c b) (match-define (can p q) c) (cond [(eq? b 'white) (can p (add1 q))] [else (can (add1 p) q)])) (define (coffe-can c) (match-define (can p q) c) (cond [(< (+ p q) 3) 'finished] [else (define-values (a b nc) (select-pair c)) (cond [(eq? a b) (coffe-can (insert-bean nc 'black))] [else (coffe-can (insert-bean nc 'white))])]))I went a slightly different route, both with language (C++11) and simulation
technique. As for the problems, the second one tripped me up. Moreover, it
reminded me of a similar problem in Hofstadter’s “Godel, Escher, Bach” that
also stumped me a bit. You’d think I would have learned my lesson.
#include <iostream> #include <random> auto coffee_can(uintmax_t black, uintmax_t white) -> char { if ((black + white) == 0) { return 'X'; } // error auto d = std::uniform_real_distribution<double>{0.0, 1.0}; auto e = std::default_random_engine{std::random_device{}()}; auto ww = [&d, &e](uintmax_t b, uintmax_t w) -> double { return d(e) < ((w * (w - 1.0)) / ((w + b) * (w + b - 1.0))); }; while ((black + white) > 1) { if (ww(black, white)) { ++black; white -= 2; } else { --black; } } return (black == 1 ? 'b' : 'w'); } auto main(int argc, char *argv[]) -> int { if (argc != 3) { std::cerr << "usage: " << argv[0] << " <#black> <#white>" << std::endl; return EXIT_FAILURE; } else { auto black = uintmax_t(std::stol(argv[1])), white = uintmax_t(std::stol(argv[2])); std::cout << coffee_can(black, white) << std::endl; } }Solution in ruby
WHITE = ‘W’
BLACK = ‘B’
class CoffeCan
def initialize
@beans = []
end
def add_bean(bean)
@beans.push bean
end
def fill_randomly(size)
amount = rand size
(0..amount).each do
if (rand 2) == 0
@beans.push WHITE
else
@beans.push BLACK
end
end
end
def remove_two_beans
[@beans.delete_at(rand(@beans.size)), @beans.delete_at(rand(@beans.size))]
end
def is_possible
(@beans.size > 1) || false
end
def to_s
@beans.join ‘ ‘
end
end
class SimulateCan
def run (size=10000)
can = CoffeCan.new
can.fill_randomly size
puts can.to_s
while can.is_possible
beans = can.remove_two_beans
if beans[0] == beans[1]
can.add_bean BLACK
else
can.add_bean WHITE
end
puts can.to_s
end
end
end
sim = SimulateCan.new
sim.run
First, clearly this problem calls for a coffee-associated programming language. As I find that I need to learn some Coffeescript anyway, here’s my first ever Coffeescript program.
Second, while the randomness specification is a red herring, let’s at least make it more realistic: my replacement step shuffles some number of the beans on top, not the whole can. To do this, I represent the can as an array of distinct beans. I also take care to return the same white bean to the can (another red herring in the specification).
I omit the Fisher-Yates shuffle code that I found on the web.
replace = (can) ->
[a, b] = [can.shift(), can.shift()]
if a[0] is b[0] then can.unshift(['black'])
else can.unshift(if a[0] is 'white' then a else b)
top = Math.min(some, can.length)
can[0...top] = shuffle(can[0...top])
can
process = (can) ->
while can.length > 1
replace(can)
To make and shuffle an initial can, run the process on it with the number of shuffled top beans specified, and print the final can, I had the following. It appears to print a can with a white bean in it when there is an odd initial number of white beans.
some = 8
whites = 39
beans = 41
can = ([if k < whites then 'white' else 'black'] for k in [0...beans])
shuffle(can)
process(can)
console.log(can)
This was fun.
Is this an acceptable simulation of the problem in Java?
public class CoffeeBeansProblem { final static String BLACK = "black"; final static String WHITE = "white"; List<String> can; List<String> blackPile; public static void main(String[] args) { new CoffeeBeansProblem().runSimulation(); } private void runSimulation() { can = generateRandomBeans(100000); blackPile = generateBlackBeans(100000); Random random = new Random(); while(true){ /* randomly select two beans from the can */ int limit = can.size() - 1; int indexOne = random.nextInt(limit); int indexTwo = random.nextInt(limit); String beanOne = can.get(indexOne); String beanTwo = can.get(indexTwo); /* If they are the same color, throw them both out and insert an extra black bean. */ if(beanOne.equals(beanTwo)){ can.remove(indexOne); can.remove(indexTwo); blackPile.remove(0); can.add(BLACK); } else { /*If they are different colors, return the white bean to the can and throw out the black*/ can.remove(beanOne.equals(BLACK) ? indexOne : indexTwo); } if(can.size() == 1){ break; } } System.out.println("Terminated, remaining in the can " + can); } private List<String> generateBlackBeans(int size) { List<String> list = new ArrayList<String>(); for(int i = 0 ; i < size ; i++){ list.add(BLACK ); } return list; } private List<String> generateRandomBeans(int size) { List<String> list = new ArrayList<String>(); Random random = new Random(); for(int i = 0 ; i < size ; i++){ int nr = random.nextInt(size); list.add(nr % 2 == 0 ? BLACK : WHITE); } return list; } }Mark, I think it would be better if the simulation could be run with different numbers of beans and different proportions of white and black. Your program generates only cans (of 100000, quite a lot) with roughly equal proportions of the colours.
It would also be appropriate to print the initial numbers of white and black beans together with the colour of the final bean. Or let the user supply the initial numbers.
It’s unrealistic that every bean is equally likely to be picked but the framers of the problem didn’t have such realism in mind. The original framers didn’t even have simulation in mind. It was about reasoning.
And yes, Java is an appropriate language for coffee-can problems.