Time to dream the solution to the dreams puzzle. As a reminder, here’s the challenge:

package sleep;

import dream.Dream;

public class Sleeper {
	private int level;

	public synchronized int enter(Dream dream) {
		level++;
		try {
			dream.dream(this);
		} finally {
			level--;
		}
		return level;
	}
}

package sleep;

import dream.Dream;

public class Main {
	public static void main(String[] args) {
		if (new Sleeper().enter(new Dream()) != 0) {
			// The goal is to reach this line
			System.out.println("Am I still dreaming?");
		}
	}
}

Solution

The synchronized on the dream method means that it takes the monitor (lock) of the Sleeper object when we enter it, and it releases it again when we leave it. No other thread can enter the method while the monitor is held.

But here’s the catch: the monitor isn’t necessarily held all the time while the method is running. With Object.wait you can release a monitor in the middle of a synchronized method.

How do we apply that to solve this puzzle? When we enter the outer dream, we use wait to release the monitor. But first we launch a separate thread, that will also enter a dream. Entering that inner dream makes the second thread take the monitor. So in the inner dream, we use wait a second time to release the monitor. That allows the main thread stop waiting, take the monitor back, and leave the outer dream. And there we are: we have woken up from the outer dream, back where we started in main, but the dream within the dream goes on in the second thread.

package dream;

import sleep.Sleeper;

public class Dream {
	private static void doWait(Sleeper s) {
		try {
			s.wait(200);
		} catch (InterruptedException e) {
		}
	}

	public void dream(final Sleeper s) {
		new Thread() {
			public void run() {
				s.enter(new Dream() {
					@Override
					public void dream(Sleeper s) {
						doWait(s);
					}
				});
			}
		}.start();

		doWait(s);
	}
}

And the winner is…

I got more answers than I expected. The first one came from David Shay. Congrats!

It’s a bit repetitive, but as promised, you can see and compare all dreams as comments below this post.

Conclusion

The moral of the story: synchronized on a method doesn’t mean two different threads can’t be in it at the same time. It only ensures that such threads cannot execute concurrently; at least one of them must be waiting.

You can prevent this kind of abuse and other problems, by using a private object as monitor:

public class Sleeper {
	private final Object lock = new Object();

	public int dream(Dream dream) {
		synchronized(lock) {
			...
		}
	}
}

But that still leaves me unsure if I actually woke up this morning.

Here’s another challenging Java Puzzle! The same rules as for the clowns puzzle apply. [Update: In short: anything in your code is allowed; any trick outside the code is not. You must run with -Djava.security.manager, so setAccessible won't work.].

We’ve learned our lesson from the clowns: There are no hidden calls behind the scenes here, and we embrace recursion; we count on it.

Have you ever woken up from a dream, to then discover that you’re actually still dreaming? If you then wake up, how do you know you’re back in reality? This puzzle implements a solution to that problem: you count the recursion level of your dreams as you enter and exit them:

package sleep;

import dream.Dream;

public class Sleeper {
	private int level;

	public synchronized int enter(Dream dream) {
		level++;
		try {
			dream.dream(this);
		} finally {
			level--;
		}
		return level;
	}
}

A sleeper starts sleeping and enters a dream (level one). He can have a dream within that dream, and even enter deeper dreaming levels. But when he leaves the outer dream, he’s awake again, so he should be at level zero again, right?

package sleep;

import dream.Dream;

public class Main {
	public static void main(String[] args) {
		if (new Sleeper().enter(new Dream()) != 0) {
			// The goal is to reach this line
			System.out.println("Am I still dreaming?");
		}
	}
}

The counting of the levels looks really safe, so this seems impossible:

• Every time you enter a dream level is increased. Because of the finally block, there’s no way to leave a dream without decreasing it again.
• The synchronized block makes sure no other thread can call it concurrently. The level is returned from the dream method to make sure it’s read within the synchronized block.
• dream is the very first thing that’s called on the Sleeper, so the level must be zero when entering it. The value that’s returned from it must be zero too then, because even if we call it recursively we must enter as many dreams as we exit.

// this is the only file you're allowed to edit
package dream;

import sleep.Sleeper;

public class Dream {
	public void dream(Sleeper s) {
		// TODO implement me
	}
}

Do you eat Java, breathe Java, and even dream in Java? Can you find the flaw in this reasoning? Can you imagine a really weird dream, that would make the sleeper lose count? If so, leave your code in a comment here!

To give everyone a fair chance, those comments will stay were hidden for a while. They will become public soon are now public, together with a follow-up blog post.
To be notified of that and the next puzzles, follow the feed or twitter.

PS: This puzzle is appearing simultaneously in the Java Specialists’ Newsletter.

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…

Introduction

This is the first in a series of Java puzzles, that put your Java skills to the test, in a challenging and fun way!
A puzzle consists of some given Java code with a line in it that seems to be impossible to reach. It’s up to you to find the hole in it, abuse a subtle behavior of Java to make execution reach that line anyways.

There almost aren’t any rules; any cheating inside your code is allowed; it is the whole point of the puzzle. [Clarification: Cheating the environment is not]. You must run with the security manager enabled (java -Djava.security.manager), otherwise it would be too easy (with setAccessible for example). [Update: Use common sense, and see the exact rules if you're in doubt].

The puzzle

How can you fit 20 clowns into a Volkswagen? Two classes are given: an empty Clown class, and a Volkswagen class to which you can add clowns. When you try to add a Clown, it is checked that it isn’t already full. But if you just try hard enough, there’s always room for some extra clowns…

package clowns;

public class Clown {
}

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!");
        }
    }
}

Write a class that when executed pushes 20 clowns into the little car, and reaches the marked line. Here is one that won’t really work, just to get you started:

package you;

import clowns.Clown;
import clowns.Volkswagen;

public class You {
    public static void main(String args[]) {
        // TODO put 20 clowns into a Volkswagen
        Volkswagen vw = new Volkswagen();
        for (int i = 0; i < 20; i++) {
            vw.add(new Clown());
        }
        vw.done();
    }
}

You can copy-paste the code into your IDE, or get it from github (zip).
If you’ve solved it, let me know (email or Twitter). If you’re the first, you’ll get… the honor of being the first. compare it to the solution posted here.
The solution and a new challenge will follow, so stay tuned!

Update: Don’t post answers as comments here, they will be blocked by moderation. You may comment, but no spoiler. If you have an alternative solution, post it as a comment on the solution post
Update 2: Added clarification of the rules.