Java Puzzle 2: Dreams

3 min read Original article ↗

Feb 23, 2012

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.