Feb

2012

Java Puzzle 2: Dreams – Solution

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.

| 151 Comments, add your own » | Tags: java, puzzle, solution

151 comments to “Java Puzzle 2: Dreams – Solution”

Alexander Filipchik says:

February 24, 2012 at 12:05 am

package sleep;

public class Dream {
  private static boolean runned = false;

  public void dream(final Sleeper s) {
    System.out.println("Entering dream");
    final Dream dream = this;
    Runnable runnable = new Runnable() {

      @Override
      public void run() {
        System.out.println("Entering sleep from new thread");
        s.enter(dream);
        System.out.println("Left sleep from new thread");
      }
    };

    if (runned) {
      s.notifyAll();
      try {
        s.wait();
      } catch (InterruptedException e) {
      }
      Thread.yield();
      try {
        System.out.println("New Thread going to sleep");
        Thread.sleep(1000);
      } catch (InterruptedException e) {
      }
      return;
    }

    runned = true;
    Thread thread = new Thread(runnable);
    thread.start();
    try {
      System.out.println("Old thread entering sleep");
      s.wait();
      System.out.println("Old thread leaving sleep");
    } catch (InterruptedException e) {
    }
    System.out.println("Left sleep from old thread");
    s.notifyAll();
  }
}

Dominique Laurent says:

February 24, 2012 at 12:20 am

This one wasn’t that hard…

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

import sleep.Sleeper;

public class Dream {

    public void dream(final Sleeper sleeper) {
        // The current (main) thread holds the exclusive lock on sleeper

        Thread concurrentDreamThread = new Thread(new Runnable() {
            public void run() {
                sleeper.enter(new Dream() {
                    @Override
                    public void dream(Sleeper s) {
                        synchronized (sleeper) {
                            try {
                                sleeper.wait(10L);
                                sleeper.notify();
                                sleeper.wait();
                            } catch (InterruptedException e) {
                                e.printStackTrace();
                            }
                        }
                    }
                });
            }
        });
        concurrentDreamThread.setDaemon(true);
        concurrentDreamThread.start();

        // we have to release the lock on sleeper
        try {
            sleeper.wait();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // the main thread has been notified so inner dream is now waiting
        // exit
        System.out.println("Gotcha!");

    }
}

Jaroslav Sedlacek says:

February 24, 2012 at 12:40 am

package dream;

import sleep.Sleeper;

public class Dream {
    public void dream(final Sleeper s) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                s.enter(new WaitingDream());
            }
        }).start();
        try {
            s.wait();
        } catch (InterruptedException e) {
        }
    }

    static class WaitingDream extends Dream {
        @Override
        public void dream(Sleeper s) {
            s.notifyAll();
            try {
                s.wait();
            } catch (InterruptedException e) {
            }
        }
    }
}

Naree Song says:

February 24, 2012 at 12:44 am

package dream;

import sleep.*;

public class Dream {
    public void dream(final Sleeper sleeper) {
        new Thread(new Runnable() {
            public void run() {
                sleeper.enter(new Dream() {
                    public void dream(Sleeper sleeper) {
                        sleeper.notify();
                        try {
                            sleeper.wait();
                        } catch (InterruptedException e) {}
                    }
                });
            }
        }).start();

        sleeper.enter(new Dream() {
            public void dream(Sleeper sleeper) {
                try {
                    sleeper.wait();
                } catch (InterruptedException e) {}
            }
        });
    }
}

Filo Relaylon says:

February 24, 2012 at 12:48 am

package dream;

import sleep.Sleeper;

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

		try {
			s.wait();
		} catch (InterruptedException ie) {}
	}
}

class AnotherDream extends Dream {
	@Override
	public void dream(Sleeper s) {
		s.notify();
			try {
			s.wait(1);
		} catch (InterruptedException ie) {}
	}
}

Tim Lammens says:

February 24, 2012 at 12:52 am

package dream;

import sleep.Sleeper;
import sleep.Main;


public class Dream {
    
    private static boolean hasBeenEntered = false;
    
    public void dream(final Sleeper s) throws Exception {
        
        if(!"otherThread".equals(Thread.currentThread().getName())){
            new Thread(new Runnable(){
                public void run(){
                    s.enter(new Dream());
                }
            }, "otherThread").start();
            // give otherThread some time to enter a new Dream.
            while(!hasBeenEntered){
                s.wait(1000);
            }
        } else {
            // ok, we have entered the new dream
            hasBeenEntered = true;
            //now wait forever
            s.wait();
        }
    }
}

Siam says:

February 24, 2012 at 1:56 am

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

import sleep.Sleeper;

public class Dream {

	public void dream(final Sleeper s) {
		
		final Thread t = new Thread(){
			public void run() {
				s.enter(new Dream());
			};

		};
		
		synchronized(s){
			t.start();
			try {
				s.wait(1);
			} catch (Exception e) {
				e.printStackTrace();
			}
		}


	}

}

nobullet says:

February 24, 2012 at 1:57 am

    public static class Dream {

        public void dream(final Sleeper s) {
            try {
                Thread t = new Thread(new Runnable() {

                    @Override
                    public void run() {
                        synchronized (s) {
                            s.enter(new Dream() {

                                @Override
                                public void dream(final Sleeper s) {
                                    s.notifyAll();
                                    try {
                                        s.wait(1000 * 1);
                                    } catch (InterruptedException ex) {
                                         // log this
                                    }
                                }
                            });
                        }
                    }
                });
                t.start();
                s.wait();
            } catch (InterruptedException ex) {
               // log this
            }
        }
    }

Siam says:

February 24, 2012 at 2:02 am

(slightly more succinct than previous entry)

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

import sleep.Sleeper;

public class Dream {

	public void dream(final Sleeper s) {
		synchronized(s){
			new Thread(){
				public void run() {
					s.enter(new Dream());
				};
			}.start();
			try {
				s.wait(1);
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
	}

}

Soheil Hassas Yeganeh says:

February 24, 2012 at 2:18 am

Another solution I hope this one is valid.

package dream;

import sleep.Sleeper;

public class Dream {
  int count = 0;
  public void dream(Sleeper s) {
    final Sleeper s2 = s;
    if (count == 0) {
      count++;
      new Thread() {
        @Override
        public void run() {
          s2.enter(Dream.this);
        }
      }.start();
    } else {
      s.notify();
      try {
        s.wait();
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }

    try {
      s.wait();
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
  }
}

Stefan Riesen says:

February 24, 2012 at 3:03 am

My solution uses the fact that Object.wait releases the sleeper’s monitor, allowing another Thread to call the enter method and wait as well allowing the main Thread to continue:

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

import sleep.Sleeper;

public class Dream {

	private static final int JUST_NAP = 1;
	private static final int NEVER_WAKE_UP = 0;

	private final class WaitingDream extends Dream {
		
		private long timeout;
		
		public WaitingDream(long timeout) {
			super();
			this.timeout = timeout;
		}

		@Override
		public void dream(Sleeper s) {
			synchronized(s) {
				try {
					s.wait(timeout);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}
	}

	public void dream(final Sleeper s) {
		Thread otherDreamer = new Thread(new Runnable() {
			public void run() {
				s.enter(new WaitingDream(NEVER_WAKE_UP));
			}
		});
		otherDreamer.setDaemon(true);
		otherDreamer.start();
		s.enter(new WaitingDream(JUST_NAP));
	}

}

Nephilim Faustus says:

February 24, 2012 at 4:20 am
```
// this is the only file you're allowed to edit
package dream;

import sleep.*;

public class Dream {
  public void dream(Sleeper s) {
    s.enter(self);
  }
}
```
This will result in an infinite loop until Sleeper.java:11 throws java.lang.IllegalArgumentException. By then, level should have a value of Integer.MAX_VALUE, decrement it will return value of Integer.MAX_VALUE-1

Alternatively, it would have recursed so such that Sleeper.java:11 actually throws java.lang.StackOverflowError. When this happens the value of level is likely to be a value more than 2. Decrementing it will return a value more than 0

Reply
- Wouter says:
  
  February 26, 2012 at 5:41 pm
  
  This doesn’t work. See also comment from Usman a little lower. Does it work for you, or did you not even try to run it?
  
  Reply

Sam says:

February 24, 2012 at 4:21 am

This is some nice brain teaser. It took me quite a while.

The key idea is to release the lock obtained when entering the synchronized dream method.

    public void dream(final Sleeper s) {
        Thread t = new Thread(new Runnable() {
            @Override
            public void run() {
                s.enter(new Dream() {
                    @Override
                    public void dream(Sleeper s) {
                        System.out.println("entered inner dream");
                        try {
                            Thread.sleep(1000);
                            System.out.println("waking up outter");
                            s.notifyAll();
                            System.out.println("inner back to sleep");
                            s.wait(); // release synchronize lock
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                });
            }
        });

        t.start();

        try {
            System.out.println("main going to sleep");
            s.wait(2000); // release synchronized lock
            // by now, the inner dream stuck
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

Tate says:

February 24, 2012 at 5:20 am

public void dream(final Sleeper s) {
	new Thread() {
		public void run() {
			synchronized (s) {
				s.notify();
				s.enter(Dream.this);
			}
		};
	}.start();
	synchronized (s) {
		try {
			s.wait();  // The lock is released after calling wait().
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}
}

Usman says:

February 24, 2012 at 6:33 am

Recursively overflow int value.
```
private static long counter = 0L;
public void dream(Sleeper s) {
                counter++;
                if(counter <= Integer.MAX_VALUE+1L) {
                        s.enter(this);
                }
    }
```
However had to increase stack size -Xss. However, this makes my machine extremely slow to respond . Will try to come up with some alternate mechanism.

Reply
- Wouter says:
  
  February 26, 2012 at 5:24 pm
  
  Doesn’t work for me.
  I don’t see how it can work; because even in case of an overflow, counter– undoes what counter++ did.
  
  Reply

Muel says:

February 24, 2012 at 7:06 am

public class Dream implements Runnable {

      private final AtomicReference<Sleeper> sleeper = new AtomicReference<Sleeper>();

      public void dream(Sleeper s) {
        if (sleeper.compareAndSet(null, s)) {
          new Thread(this).start();
        } else {
          s.notify();
        }
        try {
          s.wait(50L);
        } catch (InterruptedException e) {/* ignored */}
      }

      @Override
      public void run() {
        sleeper.get().enter(this);
      }

    }

Chandan says:

February 24, 2012 at 7:13 am

Please find my solution below:

public class Dream {

	public void dream(final Sleeper sleeper) {
		new Thread() {
			public void run() {
				sleeper.enter(new Dream() {
					public void dream(Sleeper sleeper) {
						wait(sleeper, 2000);
					};
				});
			}
		}.start();
		wait(sleeper, 1000);
	}

	public void wait(Sleeper sleeper, long timeout) {
		try {
			sleeper.wait(timeout);
		} catch (InterruptedException e) {
		}
	}

}

Jesper Udby says:

February 24, 2012 at 9:03 am

package dream;

import sleep.*;

public class Dream {
	public void dream(final Sleeper s) {
		try {
			s.notifyAll();
			Thread thread = new Thread() {
				public void run() {
					s.enter(Dream.this);
				}
			};
			thread.start();
			s.wait();
		} catch (Exception ignored) {
		}
	}
}

Maarten Hazewinkel says:

February 24, 2012 at 9:09 am

In the Dream, recursively enter the same dream again in a second thread, using wait and notify on the Sleeper to work around it’s synchronized block. Then release the master dream before the recursive dream is done.

package dream;

import sleep.Sleeper;

public class Dream {
    private volatile boolean recurse = true;
    public void dream(final Sleeper s) {
        try {
            if (recurse) {
                recurse = false;
                new Thread() {
                    @Override
                    public void run() {
                        s.enter(Dream.this);
                    }
                }.start();
                s.wait();
            } else {
                s.notify();
                s.wait(1000);
            }
        } catch (InterruptedException e) {
            // ignore
        }
    }
}

I found this one much easier to solve than the clowns puzzle, but once I did I was ably to apply a similar multi-threaded solution for that one.

Sergey says:

February 24, 2012 at 9:24 am

package dream;

import sleep.*;

public class Dream {
  public void dream(Sleeper s) {
    final Dream dream = new Dream() {
      @Override
      public void dream(Sleeper s) {
        try {
          // Make sure main thread goes to sleep.
          synchronized(this) {
            wait(1000);
          }
        } catch (InterruptedException e) {
          // Noop.
        }

        s.notify();
        try {
          s.wait();
        } catch (InterruptedException ex) {
          // Noop.
        }
      }
    };

    class MyThread extends Thread {
      private final Sleeper s;

      public MyThread(Sleeper s) {
        this.s = s;
      }

      @Override
      public void run() {
        s.enter(dream);
      }
    }

    new MyThread(s).start();

    try {
      s.wait();
    } catch (InterruptedException ex) {
      // Noop.
    }
  }
}

Renaud Michel says:

February 24, 2012 at 9:24 am

Here is my proposed solution, taking advantage that Sleeper synchronizes on himself.

public class Dream implements Runnable {
	private Sleeper sleeper;
	public Dream(){}
	private Dream(Sleeper sleeper){
		this.sleeper=sleeper;
	}
	public void run() {
		if(sleeper!=null) sleeper.enter(this);
	}
	public void dream(Sleeper s) {
		if(sleeper==null){
			Thread t=new Thread(new Dream(s));
			t.start();
		}
		try{
			s.notify();
			s.wait();
			s.notifyAll();	//to stop the thread
		}catch(InterruptedException ex){
			System.out.println("dream interrupted...");
		}
	}
}

Ives says:

February 24, 2012 at 9:35 am

The trick is that s.wait() will release the monitor that Java uses to synchronize the Sleeper.enter() call.

public class Dream
{
    public void dream(final Sleeper s) {
        startWeirdDream(s);
        waitFor(s);
    }

    private void startWeirdDream(final Sleeper s) {
        new Thread() {
            @Override
            public void run()
            {
                s.enter(new WeirdDream());
            }
        }.start();
    }

    public class WeirdDream extends Dream {
        @Override
        public void dream(Sleeper s) {
            s.notifyAll();
            waitFor(s);
        }
    }

    private void waitFor(Sleeper s) {
        try {
            s.wait();
        } catch (InterruptedException e) {
        }
    }
}

Prince John Wesley says:

February 24, 2012 at 10:05 am

	public void dream(Sleeper s) {
		try {
			final Sleeper s1 =s;
			Thread t =new Thread( new Runnable() {
				public void run() {
					s1.enter(Dream.this);
					synchronized (s1) {
						s1.notify();
					}
				}
			});
			t.setDaemon(true);
			t.start();
			synchronized (s) {				
				s.wait();
			}
			
		} catch(Throwable e) {
		}
	}

Lucian Szantho says:

February 24, 2012 at 10:08 am

The idea is that wait releases the current monitor, thus we can enter a new dream on a new thread.

public class Dream {
  public void dream(final Sleeper s) {
    new Thread() {
      public void run() {
        s.enter(new Dream() {
          public void dream(Sleeper s) {
	    s.notifyAll();
	      try {
	        s.wait();
	      } catch (InterruptedException e) {e.printStackTrace();}
	  }
        });
      }
    }.start();
    try {
      s.wait();
    } catch (InterruptedException e) {e.printStackTrace();}
  }
}

Aksel Schmidt says:

February 24, 2012 at 10:10 am

too eager to make proper formatting – here we go again:
There, did it (but not in 15 minutes)

package dream;

import sleep.Sleeper;

public class Dream {
    private Thread aMainThread;

    public void dream(final Sleeper s) {
        if (aMainThread == null) {
            aMainThread = Thread.currentThread();
        }
        if (Thread.currentThread() == aMainThread) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    synchronized (s) {
                        // count up...
                        s.enter(Dream.this);
                    }
                }
            }).start();
            try {
                // park main
                s.wait();
            } catch (InterruptedException e) {
            }
        } else {
            // start main...
            aMainThread.interrupt();
            try {
                // and park other thread while dreaming
                s.wait();
            } catch (InterruptedException e) {
            }
        }
    }
}

Paul Macdona says:

February 24, 2012 at 10:44 am

  
class Dream
{
	public void dream(final Sleeper s)
	{
		new Thread(new RunningSleeper(s)).start();

		synchronized (s)
		{
			try
			{
				s.wait();
			}
			catch (Exception e)
			{
				//
			}
		}
	}

	class RunningSleeper implements Runnable
	{
		private final Sleeper s;

		public RunningSleeper(final Sleeper s)
		{
			this.s = s;
		}

		@Override
		public void run()
		{
			s.enter(new WeirdDream());
		}
	}

	class WeirdDream extends Dream
	{
		@Override
		public void dream(final Sleeper s)
		{
			synchronized (s)
			{
				s.notify();
			}
			synchronized (s)
			{
				try
				{
					s.wait();
				}
				catch (Exception e)
				{
					// Zzzz
				}
			}
		}
	}
}

Paul Macdona says:

February 24, 2012 at 10:47 am

  
class Dream
{
	public void dream(final Sleeper s)
	{
		new Thread(new RunningSleeper(s)).start();

		synchronized (s)
		{
			try
			{
				s.wait();
			}
			catch (Exception e)
			{
				//
			}
		}
	}

	class RunningSleeper implements Runnable
	{
		private final Sleeper s;

		public RunningSleeper(final Sleeper s)
		{
			this.s = s;
		}

		@Override
		public void run()
		{
			s.enter(new WeirdDream());
		}
	}

	class WeirdDream extends Dream
	{
		@Override
		public void dream(final Sleeper s)
		{
			synchronized (s)
			{
				s.notify();
				try
				{
					s.wait();
				}
				catch (Exception e)
				{
					// Zzzz
				}
			}
		}
	}
}

Oleksiy Dyagilev says:

February 24, 2012 at 11:15 am

class Dream {
    
	public void dream(final Sleeper sleeper) {

    	new Thread(new Runnable() {
            public void run() {
                sleeper.enter(new Dream() {
                    public void dream(Sleeper s) {
                        synchronized (s) {
                        	System.out.println("notify");
                            s.notify();
                            try {
                            	System.out.println("before 2nd wait");
								s.wait();
							} catch (InterruptedException e) {}
                        }
                    }
                });
            }
        }).start();
    	
    	
        synchronized (sleeper) {
            try {
            	System.out.println("before 1st wait");
                sleeper.wait();
                System.out.println("after 1st wait");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
	
}

Stephan Feder says:

February 24, 2012 at 12:52 pm

Release the lock with wait()!

package dream;

import sleep.Sleeper;

public class Dream {
    public void dream(Sleeper s) {
        final Sleeper sleeper = s;
        new Thread () {
            public void run () {
                sleeper.enter (new Dream () {
                    public void dream (Sleeper s) {
                        s.notify ();
                        try {
                            s.wait ();
                        }
                        catch (final InterruptedException e) {
                            // ignore
                        }
                    }
                 });
            }
        }.start ();
        try {
            sleeper.wait ();
        }
        catch (final InterruptedException e) {
            // ignore
        }
        sleeper.notify ();
    }
}

Per Claesson says:

February 24, 2012 at 1:33 pm

Hi, last night I posted an idea. Here’s code too:

    public class Dream {
        private boolean dejaVu;
        
        public void dream(Sleeper s) {
            if (dejaVu) {
                secondDream(s);
            } else {
                dejaVu = true;
                firstDream(s);
            }
        }

        private void firstDream(Sleeper s) {
            anotherDream(s);
            waitForOther(s);
            s.notify();
        }

        private void secondDream(Sleeper s) {
            s.notify();
            waitForOther(s);
        }

        private void waitForOther(Sleeper s) {
            try {
                s.wait();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }

        private void anotherDream(final Sleeper s) {
            new Thread() {
                public void run() {
                    s.enter(Dream.this);
                }
            }.start();
        }
        
    }

Sleeper is actually exposing an undocumented API: synchronization on itself. Sleeper could fix this by using an internal Object for synchronization.

Sean Reilly says:

February 24, 2012 at 2:02 pm

The bug is that the class is synchronizing on an object reference that is passes to untrusted code. The Dream implementation can release the lock, enter the enter(Dream) method on another thread, and then wake up the initial thread. At this point, the Sleeper class will have entered the enter(Dream) method twice, and exited it once.

Here’s an implementation:

package dream;

import sleep.Sleeper;

public class Dream {
    public void dream(final Sleeper s) {

        new Thread(new Runnable() {
            @Override
            public void run() {
                s.enter(new Nightmare());
            }
        }).start();

        try {
            s.wait();
        } catch (InterruptedException e) {
            //won't happen in this example
        }
    }
    
    static class Nightmare extends Dream {

        @Override
        public void dream(Sleeper s) {
            synchronized (s) {
                s.notify();
                try {
                    s.wait(100L);
                } catch (InterruptedException e) {
                    //won't happen in this example
                }
            }
        }
    }
}

Adam says:

February 24, 2012 at 2:04 pm

package dream;

import sleep.Sleeper;

public class Dream {
	
	private boolean _isMain;
	
	public Dream(boolean isMain) {
		_isMain = isMain;
	}
	
	public Dream() {
		this(true);
	}
	
	public void dream(final Sleeper s) {
		if (!_isMain) {
			synchronized(s) {
				s.notifyAll();
				try {
					s.wait();
				} catch (InterruptedException eInterrupted) {}
			}
		} else {
			Thread dreamWaitThread = new Thread(new Runnable() {
				public void run() {
					s.enter(new Dream(false));
				}
			});
			dreamWaitThread.setDaemon(true);
			dreamWaitThread.start();
			
			synchronized(s) {
				try {
					s.wait();
				} catch (InterruptedException eInterrupted){
				}

			}
		}
	}

}

Adam Crevel says:

February 24, 2012 at 2:07 pm

This code seems to work, creates an inner dream that never ends in another thread:

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

import sleep.Sleeper;

public class Dream {
    public void dream(Sleeper s) {
        Thread t = new Thread(new InnerDream(s));
        t.setDaemon(true);
        t.start();

        try {
            s.wait();
        }
        catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
    private static class InnerDream extends Dream implements Runnable {
        public InnerDream(Sleeper s) {
            this.s = s;
        }

        public void run() {
            s.enter(this);
        }

        public void dream(Sleeper s) {
            try {
                s.notify();
                s.wait();
            }
            catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        
        private Sleeper s;
    }
}

Solf says:

February 24, 2012 at 2:30 pm

Rough and unpolished (and probably creates extra unneeded thread, but who cares ).

// this is the only file you're allowed to edit
package dream;
 
import sleep.Sleeper;
 
public class Dream {
	static volatile int count = 0;
    public void dream(final Sleeper s) {
    	if (count > 1)
    		return;
    	count++;
    	
    	new Thread()
    	{
			@Override
			public void run()
			{
				s.enter(new Dream());
			}
    		
    	}.start();
    	synchronized(s)
    	{
    		try
    		{
    			s.notifyAll();
    			s.wait();
    			s.notifyAll();
    		} catch (InterruptedException e)
    		{
    			// 
    		}
    	}
    }
}

Trevor Fowell says:

February 24, 2012 at 2:34 pm

public class Dream {
    static class DreamBlocker extends Dream {
        public void dream(final Sleeper s) {
            try  {
                s.wait(100000000);
            }
            catch (Exception e) {
            }
        }
    }

    public void dream(final Sleeper s) {
        try {
            new Thread(new Runnable() {
                public void run() {
                    try {
                        s.enter(new DreamBlocker());
                    }
                    catch (Exception e) {
                    }
                }
            }).start();

            s.wait(1000);
        }
        catch (Exception e) {
        }
    }
}

gru says:

February 24, 2012 at 2:47 pm

public class Dream {
  public static class InnerDream extends Dream {
    @Override
    public void dream(Sleeper s) {
      try {
        s.notify();
        s.wait(5000);
      } catch (InterruptedException e) {}
    }
  }

  public void dream(final Sleeper s) {
    new Thread() {
      @Override
      public void run() {
        s.enter(new InnerDream());
      }
    }.start();
    try {
      s.wait();
    } catch (InterruptedException e) {}
  }
}

Dawid Murgała says:

February 24, 2012 at 3:10 pm

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

import sleep.Sleeper;

public class Dream {
    private static volatile boolean visited = false;

    public void dream(final Sleeper sleeper) {
        if (!visited) {
            visited = true;
            new Thread(new Runnable() {
                public void run() {
                    sleeper.enter(Dream.this);
                }
            }).start();

            try {
                sleeper.wait();
            } catch (InterruptedException e) {
            }

        } else {
            try {
                sleeper.notify();
                sleeper.wait(1);
            } catch (InterruptedException e) {
            }
        }
    }
}

Pavel G says:

February 24, 2012 at 3:10 pm

package dream;
 
import java.util.concurrent.Executors;
import sleep.Sleeper;
 
public class Dream implements Runnable {

	private static volatile byte n = 0;

	private Sleeper sleeper;
	
	public Dream() {
		
	}
	
	public Dream(Sleeper sleeper) {
		this.sleeper = sleeper;
	}
	
	public void dream(Sleeper s) {
        try {
        	if (n == 0) {
                System.out.println("Main begin: " + Thread.currentThread().getId());
        		n = 1;
        		Thread t = new Thread(new Dream(s));
        		t.setDaemon(true);
            	Executors.newSingleThreadExecutor().submit(t);
    			s.wait(); // release lock and wait
    	        System.out.println("Main end: " + Thread.currentThread().getId());
        	} else if (n == 1) {
        		System.out.println("Daemon begin: "  + Thread.currentThread().getId());
        		n = 2;
        		Thread t = new Thread(new Dream(s));
        		t.setDaemon(true);
            	Executors.newSingleThreadExecutor().submit(t);
    			s.wait(); // release lock and wait
        		System.out.println("Daemon end: "  + Thread.currentThread().getId());
        	} else {
        		System.out.println("Notify: "  + Thread.currentThread().getId());
        		s.notify();
        		throw new ThreadDeath(); // die
        	}
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
    }

    public void run() {
    	try {
	        System.out.println("Run sleeper ones again: " + Thread.currentThread().getId());
			Thread.sleep(100); // ensure that wait executed
			sleeper.enter(new Dream());
	        System.out.println("Run sleeper ones again - finished: " + Thread.currentThread().getId());
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
    }

}

Jan Christoph Thoelken says:

February 24, 2012 at 3:51 pm

Hello,

it indeed took me a while to get this done, but here is my solution:

The Trick is to have a second that will increase the level but will not end, i therefore chose the name EndlessDream (we’ll see the code later). The first dream howewer needs to end, so the sleeper method will return and the required line will be printed.

At first sight, this seems imposisble with the synchronized method, but i then remembered, that you can temporarily leave a monitor using wait.

First we start our second endless dream in a new thread. The endless dream will however block because its synchronized on the sleeper object and our first dream has the lock.

We therefore need to give the endless dream a chance
to start, which we do by using s.wait() in our first dream after starting the thread. The endless dream will then wake up and increase the level. We then use notify inside the endless dream to wake up our first dream. Here we need do consider that the notify will not give control to our first dream but continue our endless dream. Therefore a call to s.wait() is also needed in our endless dream.

Lots of explanations but i hope that made it clear. Finally, here is the code:
```
package dream;

import sleep.*;

public class Dream {
  
  public static class EndlessDream extends Dream {
    @Override
    public void dream(Sleeper s) {
      // notify first dream
      // this will leave control flow in this dream
      s.notifyAll();
      try {
        // temporarily leave monitor so our first
        // dream can continue without ending this dream
        s.wait();
      } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
      }
    }
  }
  
  public void dream(final Sleeper s) {
    // start new thread with endless dream
    new Thread() {
      @Override
      public void run() {
        s.enter(new EndlessDream());
      }
    }.start();
    
    try {
      // wait until endless dream is started
      // and give it a chance to start
      s.wait();
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
  }
  
}
```
Reply
- Jan Christoph Thoelken says:
  
  February 24, 2012 at 3:52 pm
  
  I forgot to mention, that this code will indeed make the second dream an endless one, as no one ever wakes the thread up again.
  
  Reply

Silviu Julean says:

February 24, 2012 at 3:58 pm

Here’s my solution:

public class Dream {
	private boolean firstDream;

	public Dream() {
		this.firstDream = true;
	}

	public Dream(boolean iWait) {
		this.firstDream = iWait;
	}

	public void dream(final Sleeper s) {
		if (firstDream) {
			// I'm the thread with the first dream.
			// Spawn a new thread for the second dream.
			new Thread(new Runnable() {

				@Override
				public void run() {
					s.enter(new Dream(false)); // Enter the second dream
				}

			}).start();
			// Release the sleeper lock and wait
			try {
				s.wait();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		} else {
			// I'm the thread with the second dream.
			// Stop the main thread from waiting
			s.notify();
			// Release my own sleeper lock, so the main thread can actually
			// return from wait()
			try {
				s.wait(100); // The timeout makes sure that I don't run forever
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
	}
}

Kofa says:

February 24, 2012 at 4:51 pm

package dream;

import sleep.Sleeper;

public class Dream {
	public void dream(Sleeper s) {
		// at this point, level = 1
		new DreamThread(s).start();
		try {
			// lock on s is released
			s.wait(1000);
		} catch (InterruptedException e) {
		}
		// the other thread has called s.enter while we released the lock, level = 2
		// now we have the lock on s; the other dream has begun but will never end
		// once we exit, level will be 1, not 0
	}

	static class DreamThread extends Thread {
		private final Sleeper s;
		DreamThread(Sleeper s) {
			this.s = s;
			setDaemon(true);
		}
		@Override
		public void run() {
			// blocks until the other thread goes to sleep, then calls s.sleep, where level is incremented
			s.enter(new FinalDream());
		}
	}
	static class FinalDream extends Dream {
		@Override
		public void dream(Sleeper s) {
			try {
				// releases lock, the other thread will carry on
				s.wait();
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}

}

Dennis says:

February 24, 2012 at 5:11 pm

It can be done by two simple threads.

package dream;

import sleep.*;

public class Dream {
	private final class NestedDream extends Dream {
		@Override
		public void dream(Sleeper s) {
			try {
				s.wait(1000);
			} catch (InterruptedException e) {
			}
		}
	}

	public void dream(final Sleeper s) {
		new Thread() {
			public void run() {
				s.enter(new NestedDream());
			};
		}.start();
		try {
			s.wait(10);
		} catch (InterruptedException e) {
		}
	}
}

Andreas Senft says:

February 24, 2012 at 5:13 pm

This is really a cool puzzle. Thanks for it!

My solution uses a separate thread which lets the sleeper enter a second dream which endures while the first dream ends.
The trick is to let the threads yield the lock, so that the synchronized method can be entered twice. Object.wait() does allow that.

I guess a counter-measure would be for the Sleeper to use a private lock object instead of synchronizing on the instance itself.

Regards,
Andreas

package dream;

import sleep.*;

public class Dream {
    private final boolean first;

    public Dream() {
        this(true);
    }

    public Dream(boolean first) {
        this.first = first;
    }

    public void dream(final Sleeper s) {
        if (this.first) {
            // first dream:
            // start a thread that enters a second dream
            Thread t = new Thread() {
                public void run() {
                    s.enter(new Dream(false));
                }
            };
            t.setDaemon(true);
            t.start();
            // wait a moment so the second dream could be entered
            try {
                synchronized(s) {
                    s.wait(1000L);
                }
            } catch (InterruptedException e) {} 
        } else {
            // second dream:
            // wait for a longer time, so we keep the sleeper's level increased 
            // while the first dream already ends.
            try {
                synchronized(s) {
                    s.wait(5000L);
                }
            } catch (InterruptedException e) {} 
        }
    }
}

Jared Bunting says:

February 24, 2012 at 5:33 pm

The key seems to be to make sure that the DreamForever thread gets access to the monitor and then never exits.

package dream;

import sleep.Sleeper;

public class Dream {
    public void dream(Sleeper s) {
	    Thread t = new Thread(new DreamForever(s));
	    t.setDaemon(true);
	    t.start();
	    try {
		    s.wait();
	    } catch (InterruptedException e) {
		    throw new RuntimeException(e);
	    }
    }

	private class DreamForever extends Dream implements Runnable {

		private volatile Sleeper s;

		public DreamForever(final Sleeper s) {
			this.s = s;
		}

		public void run() {
			s.enter(this);
		}

		@Override
		public void dream(final Sleeper s) {
			s.notifyAll();
			try {
				s.wait();
			} catch (InterruptedException e) {
				throw new RuntimeException(e);
			}
		}
	}
}

Roel Spilker says:

February 24, 2012 at 5:45 pm

package dream;

import sleep.*;

public class Dream {
	
	public void dream(final Sleeper s) {
		new Thread(new Runnable() {
			@Override
			public void run() {
				s.enter(new OtherDream());
			}
		}).start();
		try {
			s.wait();
		} catch (InterruptedException e) {}
	}
	
	static class OtherDream extends Dream {
		@Override
		public void dream(Sleeper s) {
			s.notify();
			try {
				s.wait();
			} catch (InterruptedException e) {}
		}
	}
}

Jamie H says:

February 24, 2012 at 5:50 pm

Thanks for these puzzles, really enjoyed the first one, and this was also fun. I’m with Heinz – more hard ones please, don’t bother with the easy ones!

My solution for the Sleeper:

public class Dream {

    public void dream(final Sleeper s) {

        Thread t = new Thread(new Runnable() {
            public void run() {
                s.enter(new LongDream());
            }
        });
        t.setDaemon(true);
        t.start();

        distractSleeper(s,1);
    }

    public class LongDream extends Dream {
        @Override
        public void dream(Sleeper s) {
            distractSleeper(s,5000);
        }
    }

    private void distractSleeper(final Sleeper s, long time) {
        try {
            s.wait(time);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

Maris says:

February 24, 2012 at 6:23 pm

package dream;

import sleep.Sleeper;

public class Dream {
    int num = 0;
    public void dream(final Sleeper s) {
        if (num++ < 10) {
            Thread thread = new Thread(new Runnable() {
                public void run() {
                    s.enter(Dream.this);
                }
            });
            thread.start();
            synchronized (s) {
                try {
                    s.wait(100);
                } catch (InterruptedException e) { }
            }
        }
    }
}

Ivan says:

February 24, 2012 at 8:29 pm

That was cool – tried various options on killing the other thread, while eventually it appeared not necessary procedure

package dream;

import sleep.Sleeper;

public class Dream {
	public void dream(final Sleeper sleeper) {
		boolean isMainThread = Thread.currentThread().getName().equals("main");
		if (isMainThread) {
			spawnDaemonThread(sleeper);				
		} else {
			giveUpLockToMainThread(sleeper);
		}
		letOtherThreadLockTheMonitorAndIncreaseCounter(sleeper);
	}

	private void giveUpLockToMainThread(final Sleeper s) {
		s.notify();
	}

	private void spawnDaemonThread(final Sleeper s) {
		Thread t = new Thread() {
			@Override
			public void run() {
				synchronized (s) {
					s.enter(Dream.this);					
				}
			}
		};
		t.setDaemon(true);
		t.start();
	}

	private void letOtherThreadLockTheMonitorAndIncreaseCounter(final Sleeper s) {
		try {
			s.wait();
		} catch (InterruptedException ex) {
			ex.printStackTrace();
		}
	}
}

Nick Dermott says:

February 24, 2012 at 8:50 pm

Probably (almost definitely) not the best solution but seems to work. Spent ages trying to get the second thread to exit/interrupt so that it wouldn’t execute the finally block in Sleeper but didn’t seem to work.

Welcome any feedback.

Cheers,
Nick.

final Sleeper sleeper = s;
		if(++counter<=1) {
			Thread t = new Thread(new Runnable() {
				@Override
				public void run() {
					sleeper.enter(new Dream());
				}
			});
//			t.setDaemon(true); // Doesn't seem to force the shutdown of the app - expected only deamon threads would result in shutdown
			executor.execute(t);
			try {
				synchronized(s) {
					sleeper.wait();
				}
			} catch (InterruptedException e) {}
		}
		else {
			s.notify();
			try {
				sleeper.wait(100);
				// Not sure any of the following guarantee that that finally block doesn't execute
//				Thread.currentThread().interrupt();
//				Thread.currentThread().stop();
//				System.exit(0);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}

Nick Dermott says:

February 24, 2012 at 8:58 pm

Correction – should have pasted in the whole class:

package main.teasers.dreams;

import java.util.concurrent.Executor;
import java.util.concurrent.Executors;

public class Dream {
	private static volatile int counter;
	private static Executor executor = Executors.newSingleThreadExecutor();

	public void dream(Sleeper s) {
		final Sleeper sleeper = s;
		if(++counter<=1) {
			Thread t = new Thread(new Runnable() {
				@Override
				public void run() {
					sleeper.enter(new Dream());
				}
			});
//			t.setDaemon(true); // Doesn't seem to force the shutdown of the app - expected only deamon threads would result in shutdown
			executor.execute(t);
			try {
				synchronized(s) {
					sleeper.wait();
				}
			} catch (InterruptedException e) {}
		}
		else {
			s.notify();
			try {
				sleeper.wait(100);
				// Not sure any of the following guarantee that that finally block doesn't execute
//				Thread.currentThread().interrupt();
//				Thread.currentThread().stop();
//				System.exit(0);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}

	}
}

Java Puzzle 2: Dreams – Solution

Solution

And the winner is…

Conclusion

151 comments to “Java Puzzle 2: Dreams – Solution”

Leave a comment

Menu

Recent Posts

Archives

Search