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.

About these ads

Pages: 1 2

6 Responses to “David Gries’ Coffee Can Problem”

  1. 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))])]))
    
  2. Graham said

    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;
        }
    }
    
  3. John said

    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

  4. Jussi Piitulainen said

    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.

  5. Mark said

    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;
        }
    
    }
    
  6. Jussi Piitulainen said

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 611 other followers

%d bloggers like this: