Java Puzzle 2: Dreams

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.


5 comments

Georg wrote on 2012-02-24 16:40

This one is really tricky. I tried three different solutions but I have still found no way. Let’s see what the weekend brings :-).

Anyway, I am curious for the solution.

Dawid Weiss wrote on 2012-02-24 23:29

I am a very seasoned Java developer and I don’t see a solution to this after 30 mins (other than changing level via Unsafe ;). Man, this is awesome. Thanks for sharing.

finnw wrote on 2012-02-26 18:26

It took me about an hour.

Dawid Weiss wrote on 2012-02-24 23:30

Correction - if setAccessible is not allowed Unsafe won’t work either.

Nikhil wrote on 2012-02-26 22:54

I agree this is freaking awesome, have already spent 30mins or so, still trying to figure it out. Thanks for sharing, looking forward to the solution.

Wouter wrote on 2012-02-26 22:58

Thanks. The solution has just been posted today.

sznury wrote on 2012-03-16 14:05

Nice jigsaw, thanks for sharing such stuff. Did you encouter similar problems writing code for financial sector? I have read nice article this week: “When Milliseconds Make Millions” could be nice bridge between this jigsaw and real world. Here is an url: http://adtmag.com/articles/2011/07/29/why-hft-programmers-earn-top-salaries.aspx

Wouter wrote on 2012-03-16 14:55

The puzzles are about “hacking” from inside the JVM. If you’re letting untrusted code run inside the same JVM as code managing financial transactions, you’re probably doing it wrong.