Java Puzzle 1: Clowns - Solution

Feb 18, 2012

Spoiler warning: If you want to find out how you can fit 20 clowns into a Volkswagen, read on. If you haven't seen or tried solving the clowns java puzzle yourself, do that first!

As a reminder: here's the code it's all about:

package clowns;

import java.util.HashSet;
import java.util.Set;

public class Volkswagen {
    private static final int CAPACITY = 5;
    private Set<Clown> clowns = new HashSet<Clown>();

    public synchronized void add(Clown clown) {
        if (clowns.size() >= CAPACITY) {
            throw new IllegalStateException("I'm full");
        } else {
            clowns.add(clown);
        }
    }

    public synchronized void done() {
        if (clowns.size() == 20) {
            // The goal is to reach this line
            System.out.println("I'm a Volkswagen with 20 clowns!");
        }
    }
}

Path to the solution


Imagine this was a real car with real clowns.

-- It's impossible to get twenty clowns in! There are only five seat belts, and this Volkswagen really insists on safety. When a clown enters, it first checks if there aren't already five of them sitting in it. Only after that checks it allows another one to sit (clowns.add(clown)). As soon as there are five clown sitting, there's no way to pass the check anymore, so no way to add any extra clown.
-- You're right that we can't add them one by one. But there is a window of opportunity between the check when they enter the car, and when they really sit down. Make all twenty clowns simultaneously enter the car. They will all pass the check of the Volkswagen, because it only counts clowns that are already sitting down. And only after the check let them sit.

-- The car's synchronized protection prevents anyone else from doing anything with it between the check and the sitting down.

-- Indeed, it prevents someone else from interfering. It doesn't prevent the Volkswagen or the clown itself to do it if they're given the opportunity (on the same thread).

-- But they don't get that opportunity; the car is a control freak. After the check it immediately makes them sit in their seats (in the Set).

-- Did you have a look at those seats? They're numbered, and they always first asks a person at which number they want to sit (.hashCode()). We've got some weird clowns here: when they're given the opportunity to decide that, right before answering, they can quickly pull another clown into the car. And that clown then does exactly the same with another clown. That goes on until there's a stack of twenty of them recursively pulling each other in. As long as their ass doesn't touch the seat, the seat-belt sign won't come on.

-- That must be quite a sight.

The solution

Call Volkswagen.add recursively, by overriding Clown.hashCode():

package you;

import clowns.Clown;
import clowns.Volkswagen;

public class You {
    static int counter = 0;
    static Volkswagen vw = new Volkswagen();

    public static void main(String args[]) {
        vw.add(new RecursiveClown());
        vw.done();
    }

    static class RecursiveClown extends Clown {
        public int hashCode() {
            if (++counter < 20) {
                vw.add(new RecursiveClown());
            }
            return super.hashCode();
        }
    }
}

And the winner is...

The first solution came from Heinz Kabutz, famous from The Java Specialists' Newsletter. He actually pushed me to publish these puzzles in the first place and promoted them. To show my infinite gratitude I'm going to disqualify him for having seen the puzzle in advance.

I received 7 correct solutions that passed the clarified rules. All used the same principle: adding them simultaneously using hashcode. Half of them also danced around the Volkswagen a bit in different threads to accomplish that. That's fine; there's no ban on dancing clowns here.

Congrats to all of you, especially Manuel Alvarez who was the first, and runner-up Jean-Louis Willems with the first short solution.

Conclusion

A simple check at the beginning of a synchronized method is not enough to guarantee safety if you're not very careful with which code you give control to. But should you really worry about crazy recursive clowns when writing your simple Volkswagen code?

No, you shouldn't. Well, not unless it's about privileged code handling a sandbox -- such as code of the JDK itself when running an applet. But it sure is interesting to explore these dark corners of Java. We'll continue on that track soon with a puzzle about dreams...

11 comments

Sebastien Lorber wrote on 2012-02-17 13:37

Hello,

My solution here: http://pastebin.com/BAzH0QAP

I make 20 threads calling the add method. But as the method is synchronized on Wolkswagen i use hashcode (called by the HashSet.add) to put a wolkswagen.wait so that other threads can acquire the wolkswagen lock and enter the Wolkswagen.add method. Thus i make all threads waiting in that HashSet.add method, and when they are all there i release all the threads so that all the clowns can be added to the Set.

This works because the hashCode method is called before the set size is incremented

Shimi Bandiel wrote on 2012-02-20 00:16

My different solution:

public static void main(String args[]) throws Exception {
        // TODO put 20 clowns into a Volkswagen
        final Volkswagen vw = new Volkswagen();
        for (int i = 0; i < 20; i++) {
            new Thread(new Runnable() {

                @Override
                public void run() {
                    vw.add(new Clown() {
                        @Override
                        public boolean equals(Object obj) {
                            return false;
                        }

                        @Override
                        public int hashCode() {
                            try {
                                vw.wait();
                            } catch (InterruptedException e) {
                                e.printStackTrace();
                            }
                            return 0;
                        }
                    });
                }
            }).start();
        }
        Thread.sleep(2000); // refactor to barrier
        synchronized (vw) {
            vw.notifyAll();
        }
        Thread.sleep(2000); // refactor to join
        vw.done();
    }
Jonathan Fisher wrote on 2012-02-21 02:21

Haha.. brilliant. I had to ‘cheat’ to solve it!

deadalnix wrote on 2012-02-21 12:15

Awesome ! I’m eager to try more of thoses.

Anonymous wrote on 2012-02-23 19:55

Can this also be done by overriding the equals method and putting a similar hack?

Wouter wrote on 2012-02-26 15:02

Yes, if you also override hashcode so that it returns the same (e.g. “return 1”). Otherwise the equals method won’t be called.

Reg wrote on 2012-02-24 08:31

Hi, Thank you for the puzzle. I really hope this is not that obvious, but here it is. The first thing, I broke a rule - but I still found this quite interesting.

The rule I broke was adding a class to the package clowns. I did not change any of the provide files (note even You). The class I added was the following.

package clowns;

public class HashSet<K>{
    int size = 0;

    public int size() {
        if (size < 20) {
            return 0;
        }
        return size;
    }

    public void add(Clown clown) {
        size++;
    }

}

Because the Volkswagen class uses the import java.util.*; and not import “java.util.HashSet;” the Hashset in the same package is used :) Thus solving (but cheating) the problem.

Wouter wrote on 2012-02-26 13:38

I should have been more careful with that import statement indeed! I did think of that, and removed the java.util.* import. But it looks like an older version went into the Specialists’ Newsletter. Nicely spotted though!

Brian T. wrote on 2012-09-30 06:20

Saturday night and nothing to do, might as well catch up on JavaSpecialists newsletters…

Thank you Wouter for such a fantastic puzzle and Heinz @ JavaSpecialists for encouraging publishing.

I was initially thinking about the dancing-clowns approach, remembering that Object.wait() would release the lock. But then I considered the recursive add technique. I grabbed a keyboard and crowded that beetle.

Mine was not quite as elegant, but still hit the mark.

@Reg … uber sneaky jamming your own HashSet into place.

Maarten Hazewinkel wrote on 2012-02-24 10:14

I heard about this from the Java Specialists Newsletter. My solution is not as elegant as the RecursiveClown, but uses 20 threads to get every clown into the car before sitting down.

package you;

import clowns.Clown;
import clowns.Volkswagen;

import java.util.concurrent.CountDownLatch;

public class You {

    public static void main(String args[]) {
        // DONE put 20 clowns into a 5 seat Volkswagen
        final Volkswagen vw = new Volkswagen();
        final CountDownLatch addLatch = new CountDownLatch(20);

        for (int i = 0; i < 20; i++) {
            final int finalI = i;
            new Thread(new Runnable() {
                public void run() {
                    vw.add(new Clown() {
                        @Override
                        public int hashCode() {
                            if (finalI < 19) {
                                try {
                                    vw.wait();
                                } catch (InterruptedException e) {
                                    // ignore
                                }
                            } else {
                                vw.notifyAll();
                            }
                            return super.hashCode();
                        }
                    });
                    addLatch.countDown();
                }
            }).start();
        }

        try {
            addLatch.await();
        } catch (InterruptedException e) {
            // ignore
        }

        vw.done();
    }
}
Abhishek Manocha wrote on 2012-02-24 11:48

Couple of requests:

  1. Can you please explain/post that multi-threaded solution too? “Half of them also danced around the Volkswagen a bit in different threads to accomplish that.”
  2. Its all possible because the thread which has lock already in java doesnt need to acquire the lock back again, right? Mind if you can make me recall what’s the (technical) term for that?
  3. In the specific solution making “clowns : HashSet” volatile is not going to make any difference, correct?
Wouter wrote on 2012-02-26 13:33
  1. See Sébastien Lorber’s blog. (There were comments on the puzzle blog post with similar solutions, but I was a bit aggressive moderating those because I explicitly asked not to post them as comments. That’ll be different for future puzzles.)
  2. The word you’re looking for is reentrent
  3. Right, I don’t see how volatile would make a difference.
John Mikich wrote on 2012-02-24 22:04

I wonder if there is a way to prevent you from adding more than 5 clowns?!

Mich wrote on 2012-04-02 17:37

I think there is one. You could prevent the add method from being called from within itself with a boolean class variable in VW. Or you could use your own counter instead of using the hashset’s. Just be sure to increment it immediately, and decrement it if the clown was not added.

Kevin wrote on 2012-02-25 15:15

If you don’t want people to just overwrite the methods in Volkswagen, you should make this class final. Otherwise simply overwriting the methods without the CAPACITY check will do the job too:

package you;

import java.util.HashSet;

import clowns.*;

public class You {
    public static void main(String args[]) {
        // TODO put 20 clowns into a Volkswagen
        Volkswagen vw = new Volkswagen() {
            private HashSet<Clown> clowns = new HashSet<Clown>();

            public synchronized void add(Clown clown) {
                clowns.add(clown);
            }

            public synchronized void done() {
                if (clowns.size() == 20) {
                    // The goal is to reach this line
                    System.out.println("I'm a Volkswagen with 20 clowns!");
                }
            }
        };
        for (int i = 0; i < 20; i++) {
            vw.add(new Clown());
        }
        vw.done();
    }
}
Wouter wrote on 2012-02-26 13:08

The rules say:

The goal of each puzzle is to reach a certain line in the exact given class. Reaching the line in a modified copy of the given classes does not count.

Your subclass of Volkswagen clearly contains a copy of the line. When it is executed the real goal line in the Volkswagen class is never reached.

Btw, making Volkswagen final doesn’t change any of that. Then you just make your volkswagen not extend it and you can still just as easily reach your copy of the line. Going further down that path, you can just write this:

public static void main(String args[]) {
        // The goal is to reach this line
       System.out.println("I'm a Volkswagen with 20 clowns!");
}

And that’s obviously not a solution either.

Praveen wrote on 2012-03-05 14:00

If there was List instead of Set, would there be any solution?