Java Puzzle 2: Dreams - Solution

Feb 26, 2012

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.

136 comments

Frank Meulenaar wrote on 2012-02-23 14:19

At work now so I can’t try, but you can just start a large amount of dreams so level will overflow. After that each Dream exits its dream() method.

David Shay wrote on 2012-02-23 14:52

Here is my solution: two Dreams combining their forces…

package dream;

import sleep.Sleeper;

public class Dream {
    public void dream(Sleeper sleeper) {
        new NicerDream().run(sleeper);

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

    class NicerDream extends Dream {

        @Override
        public void dream(final Sleeper sleeper) {
            sleeper.notify();
            try {
                sleeper.wait();
            }
            catch (InterruptedException e) {
            }
        }

        public void run(final Sleeper sleeper) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    sleeper.enter(NicerDream.this);
                }
            }).start();
        }

    }
}

Ankur Shah wrote on 2012-03-04 13:38

This is more cleaner version.

Yury Vasyutinskiy wrote on 2012-02-23 14:58

Here is mine solution, it took me about 10-15 minutes to solve:

public void dream(Sleeper s) {
        System.out.println("sleeping");
        final Sleeper sleeper = s;
        new Thread(new Runnable() {
            @Override
            public void run() {
                sleeper.enter(new Dream() {
                    @Override
                    public void dream(Sleeper s) {
                        s.notify();
                        try {
                            s.wait();
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }
                });
            }
        }).start();
        try {
            s.wait();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

Pieter Laeremans wrote on 2012-02-23 15:00

Hi Wouter, here is my solution. Nice puzzle!

package dream;

import sleep.Sleeper;

public class Dream {
    private boolean firstVisit = true;

    public void dream(final Sleeper s) {
        try {

        if (firstVisit){
        firstVisit = false;
        Thread t = new Thread(new Runnable(){
            public void run(){
                s.enter(Dream.this);
            }
            });
            t.start();
        s.wait();
        s.notifyAll();
        } else {
        s.notifyAll();
        s.wait();
        }
    } catch (Exception e) {
    }
    // TODO implement me
    }
}

Paul Etherington wrote on 2012-02-23 15:16

This seems to work – the flaw in the reasoning being the guarantees of the synchronized blocks don’t hold if you use wait().

public class Dream {

    private static class WaitDream extends Dream {
        public void dream(Sleeper s) {
            try {
                s.wait();
            } catch (InterruptedException e) {
            }
        }
    }

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

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

        s.enter(new WaitDream());
    }

}

xtof wrote on 2012-02-23 15:28

Here is my solution. It consists in using a wait on the sleeper to allow the first dream to finish before the second one. This is an illustration of why it is better to use a private monitor rather than “this”.

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

import sleep.Sleeper;

public class Dream {
    private final boolean forkDream;

    public Dream() {
        forkDream = true;
    }

    public Dream(boolean fork) {
        forkDream = fork;
    }

    public void dream(final Sleeper s) {

        if (forkDream) {
            final Thread dreamThread = new Thread(new Runnable() {

                @Override
                public void run() {
                    s.enter(new Dream(false));
                }
            }, "Sleeper thread");
            dreamThread.setDaemon(true);
            dreamThread.start();
        }

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

Chris G wrote on 2012-02-23 15:28

Start a thread which calls sleeper.dream(this) then call sleeper.wait(100) to release the synchronization lock temporarily.

Carsten Lenz wrote on 2012-02-23 15:37

I came up with something like this:

package dream;

import sleep.Sleeper;

public class Dream {

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

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

Gabriel wrote on 2012-02-23 15:42

Solution for the dream puzzle:

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


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

Barry Smith wrote on 2012-02-23 15:47

Not too bad - it’s all down to wait()/notify() - here is a (slightly untidy) solution.

package dream;

import sleep.*;

public class Dream {
    private static boolean first = true;

    public void dream(Sleeper s) {
        if(first) {
            final Sleeper s2 = s;
            Runnable r = new Runnable() {
                @Override
                public void run() {
                    s2.enter(new Dream());
                }
            };
            first = false;
            new Thread(r).start();
            try {
                s.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            s.notify();
        } else {
            s.notify();
            try {
                s.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

Andreas Skoog wrote on 2012-02-23 15:51

//
// Start a new thread that does another dream call on the same sleeper.
// Use wait and notify to assure threads
//

class Dream {

    public void dream(final Sleeper s) {
        Thread t = new Thread() {
            public void run() {
                s.enter(new Dream() {
                    @Override
                    public void dream(Sleeper s) {
                        // Notify original caller
                        s.notifyAll();
                        try {

                            s.wait(100);
                        } catch (InterruptedException e) {
                        }
                    }
                });
            }
        };

        t.start();
        try {
            // Release synchronized lock causing the dream thread to run
            s.wait();
        } catch (InterruptedException e1) {
        }
    }
}

Ben Ripkens wrote on 2012-02-23 16:28

Very nice puzzle! Here is the source for my solution: http://pastebin.com/d2Sa2yKG

Jarl Petter Kvalsvik wrote on 2012-02-23 17:15

A bit trickier this puzzle, but the provided Sleeper parameter makes it possible to release the monitor and give access to it for another thread.

package dream;

import sleep.Sleeper;

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

    public void dream(final Sleeper s)
    {
        Thread t = new Thread() {
            public void run()
            {
                s.enter(new DayDream());
            }
        };
        t.setDaemon(true);
        t.start();

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

}

Mirko Rzehak wrote on 2012-02-23 17:27

// What about that Dream:
public class Dream {

    private boolean firstCall = true;

    public void dream(final Sleeper s) {
        if (firstCall) {
            firstCall = false;
            Thread dreamThread = new Thread() {

                public void run() {
                    synchronized (s) {
                        s.notify();
                        s.enter(Dream.this);
                    }
                }
            };
            // make sure prog ends while dreamThread is still waiting
            dreamThread.setDaemon(true);
            dreamThread.start();
        }
        try {
            synchronized (s) {
                s.wait();
            }
        } catch (InterruptedException ex) {
        }
    }
}

Mohamed wrote on 2012-02-23 17:29

public class Dream {

    private boolean blocked = false;

    public void dream(final Sleeper s) {
        synchronized (s) {
            try {
                final Thread th = new Thread() {
                    @Override
                    public void run() {
                        synchronized (s) {
                            if (!blocked) {
                                blocked = true;
                                s.enter(Dream.this);
                            }
                            s.notify();
                            s.notify();
                        }
                    }
                };
                th.start();
                s.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

Julien Foulon wrote on 2012-02-23 17:32

public class Dream {

    public static class BadDream extends Dream {

        @Override
        public void dream(final Sleeper s) {
            s.notify();
            try {
                s.wait();
            }
            catch (InterruptedException e) {
            }
        }
    }

    public void dream(final Sleeper s) {
        new Thread() {

            public void run() {
                s.enter(new BadDream());
            };
        }.start();
        try {
            s.wait();
        }
        catch (InterruptedException e) {
        }
        s.notify();
    }
}

Bernd Olleck wrote on 2012-02-23 17:32

Oh, I love this. Can’t wait for the next riddle!

package dream;

import sleep.Sleeper;

public class Dream {
    static boolean calledOnce;
    public void dream(final Sleeper s) {
        if (calledOnce) {
            s.notifyAll();
            try {
                s.wait();
            } catch (InterruptedException e) {}
        } else {
            calledOnce = true;
            new Thread() {
                public void run() {
                    s.enter(Dream.this);
                };
            }.start();
            try {
                s.wait();
            } catch (InterruptedException e) {}
        }
    }
}

Dominik wrote on 2012-02-23 18:15

The Java Specialists’ Newsletter brought my attention to this puzzles. The idea of my solution is to start another thread within Dream.dream which calls enter on the sleeper. The first thread is suspended within a wait and released, after the new thread has incremented the dream value and is suspended itself.

public class Dream {
   boolean called = false;

   public void dream(final Sleeper s) {
      if (!called) {
         called = true;
         Thread t = new Thread() {
            { setDaemon(true); }
            public void run() {
               s.enter(Dream.this);
            }
         };
         t.start();
         try {
            s.wait();
         } catch (InterruptedException e) {
         }
      } else {
         s.notify();
         try {
            s.wait();
         } catch (InterruptedException e) {
         }
      }
   }
}

Jawher wrote on 2012-02-23 18:16

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

Marc Fortin wrote on 2012-02-23 18:17

That was not easy, but I got it ;)

package dream;

import sleep.Sleeper;

public class Dream {
    public static Sleeper s;

    public static Dream d;
    private static boolean stop = false;
    private static boolean ok = false;

    public void dream(Sleeper s0) {

        if(s0!=null) {
            s = s0;

            try {
                s.wait();
            } catch (Exception e1) {
            }

        }
        else  {

                while(!stop) {
                    if(s!=null) {

                        s.enter(new TDream());
                        stop=true;
                    }
                }
            }

    }

    public Dream() {
        if(ok) {
            return;
        }

        ok = true;
        d = this;

        new Thread(new Runnable() {

            @Override
            public void run() {
                d.dream(null);
            }
        }).start();


    }

    private class TDream extends Dream {

        public void dream(Sleeper s0) {

            s0.notifyAll();
            try {
                s0.wait();
            } catch (InterruptedException e) {
            }

        }

        public TDream() {
        }
    }


}

David Kurtz wrote on 2012-02-23 18:17

Quick and dirty solution:

package dream;

import sleep.Sleeper;

public class Dream  {
    int counter = 0;

    public void dream(final Sleeper s) {
        if (++counter < 3) {
            final Dream aDream = this;
            Sleepholder holder = new Sleepholder(s);
            Thread thread = new Thread(new Runnable() {

                @Override
                public void run() {
                    s.enter(aDream);
                }
            });
            thread.start();
            holder.inception();
        } else {
            synchronized (s) {
                s.notify();
            }
        }
    }

    static class Sleepholder {
        private Sleeper sleeper;

        Sleepholder(Sleeper s) {
            sleeper = s;
        }

        void inception() {
            synchronized (sleeper) {
                try {
                    sleeper.wait();
                } catch (Exception e) {
                }
            }
        }
    }
}

Aksel Schmidt wrote on 2012-02-23 18:18

There, did it :) (but not in 15 minutes)

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) {
            }
        }
    }
}

Christoph Hennes wrote on 2012-02-23 18:27

package dream;

import sleep.Sleeper;

public class Dream {

    public void dream(Sleeper s) {
        final Sleeper sf = s;

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

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

deadalnix wrote on 2012-02-23 18:35

package dream;

import sleep.Sleeper;

public class Dream {
    public void dream(Sleeper s) {
        new NotifierDream(s);

        try {
            s.wait();
        } catch(InterruptedException e) {
            throw new RuntimeException("Unhandled Exception", e);
        }
    }

    static class NotifierDream extends Dream implements Runnable {
        Sleeper    s;

        NotifierDream(Sleeper s) {
            this.s = s;

            new Thread(this).start();
        }

        @Override
        public void dream(Sleeper s) {
            s.notify();

            try {
                s.wait();
            } catch(InterruptedException e) {
                // TODO Auto-generated catch block
                throw new RuntimeException("Unhandled Exception", e);
            }
        }

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

And the sleeper dreams forever ;)

Marc Fortin wrote on 2012-02-23 18:35

Ok I’ve clean-ed up my source a bit, there were a lot of useless lines due to some experimentations ;) Here is a simpler version :

package dream;

import sleep.Sleeper;

public class Dream {
    public static Sleeper s;

    public void dream(Sleeper sleeper) {

            s = sleeper;

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

    }

    public Dream() {

        new Thread(new Runnable() {

            @Override
            public void run() {
                while(true) {
                    if(s!=null) {
                        s.enter(new TDream());
                        break;
                    }
                }
            }
        }).start();

    }

    private class TDream extends Dream {

        public void dream(Sleeper sleeper) {

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

        }

        public TDream() {
        }
    }

}

deadalnix wrote on 2012-02-23 18:36

Ho god, Your comment system did break all indentation :/

Alex Snaps wrote on 2012-02-23 18:37

Here’s my solution to this:

public class Dream {

    public void dream(final Sleeper s) {
        Thread t = new Thread() {
            @Override
            public void run() {
                s.enter(new ParallelDream());
            }
        };
        t.start();
        waitForSleeper(s);
    }

    private static void waitForSleeper(final Sleeper s) {
        try {
            s.wait(TimeUnit.SECONDS.toMillis(1));
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    private static class ParallelDream extends Dream {
        @Override
        public void dream(final Sleeper sleeper) {
            sleeper.notify();
            Dream.waitForSleeper(sleeper);
        }
    }
}

Ignat wrote on 2012-02-23 18:48

Hi, please find a working version below.

Not the best formatted code, but works :)

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

import sleep.*;

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

    synchronized (s) {
        Thread t = new Thread(new Runnable() {
          public void run() {
             System.out.println("Inrun");
             synchronized(s) {
             System.out.println("On wait");
//             synchronized (s) {
                     System.out.println("Inside lock");
                     s.enter(new Dream() {
                       public void dream (Sleeper sl) {
                          s.notify();

                          System.out.println("Before long sleep");
                          wait(s);
                       }
                     });
             }
          }
        });
        t.setDaemon(true);
        t.start();
        System.out.println("Started thread");
        sleep(100);
        wait(s);
        System.out.println("Received lock");
    }
  }
  static void wait (Object o) {
     try{
       o.wait();
     } catch (Throwable e) {
       throw new RuntimeException(e);
     }
  }

  static void sleep (long num) {
     try{
       Thread.sleep(num);
     } catch (InterruptedException e) {}
  }
}

Gaël Renoux wrote on 2012-02-23 19:16

package dream;

import sleep.Sleeper;

public class Dream {

    private static boolean todo = true;

    public void dream(final Sleeper s) {

        if (todo) {
            todo = false;
            new Thread() {
                @Override
                public void run() { s.enter(new Dream()); }
            }.start();
        }

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

Jon Bodner wrote on 2012-02-23 19:22

You can relinquish the synchronization lock with wait(). Just use two threads:

package dream;

import sleep.Sleeper;

public class Dream {

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

    public void dream(final Sleeper s) {
        final ForeverDream dream = new ForeverDream();
        Thread thread = new Thread(new Runnable() {
            public void run() {
                s.enter(dream);
            }
        });
        thread.start();
        try {
            s.wait(500);
        } catch (InterruptedException e) {
        }
    }
}

Philip Pearson wrote on 2012-02-23 19:26

Not the neatest of code, but should suffice:

public class Dream {
        public void dream(Sleeper s) {
            final Sleeper fs = s;
            new Thread () {
                public void run () {
                    fs.enter(new Dream (){
                        public void dream(Sleeper s) {
                            s.notify();
                            swait (s);
                        }
                    });
                }
            }.start ();
            swait (s);
        }

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

Daniel Schwarz wrote on 2012-02-23 19:26

package dream;

import sleep.*;

public class Dream {
    public boolean firstCall = true;

    public void dream(final Sleeper s) {
        try {
            if (firstCall) {
                firstCall = false;
                new Thread() {
                    public void run() {
                        s.enter(Dream.this);
                    }
                }.start();
                s.wait(100);
            } else {
                s.wait(200);
            }
        } catch (InterruptedException e) {
        }
    }
}

Loic Taloc wrote on 2012-02-23 19:33

Nice puzzle. Here is my solution.

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

import sleep.Sleeper;

public class Dream {
    private static int count = 0;

    public void dream(Sleeper s) {
        try {
            if (++count == 1) {
                final Sleeper finalS = s;
                new Thread(new Runnable() {
                    public void run() {
                        finalS.enter(Dream.this);
                    }}).start();
                s.wait();
                s.notify();
            } else {
                s.notify();
                s.wait();
            }
        } catch (InterruptedException e) {}
    }
}

mihi wrote on 2012-02-23 20:17

Make ‘em harder. :-)

My version (not the most readable one, but short):

package dream;
import sleep.Sleeper;
public class Dream implements Runnable {
  Sleeper ss = null;
  public void run() { ss.enter(Dream.this); }
  public void dream(Sleeper s) {
    if (ss != null ) s.notifyAll();
    else {ss = s; new Thread(this).start();}
    try { s.wait();} catch (InterruptedException e) {}
  }
}

Rohan Dhapodkar wrote on 2012-02-23 20:59

Yes, it’s possible using another thread.

Once user increases level counter inside Dream.dream() method,
Trigger another thread
Release the synchronize lock (using object.wait() with timeout)
meanwhile another thread will acquire synchronize lock and will also increase level.
Now, inovke object.wait() from second thread, with some sufficient long timeout.
Main thread will come out of wait(), will reaquire the lock, decrement the level.

Here we go. Now level is 1 (since second thread has not yet finished it’s synchronized block. [code] Timeline T1 T2 level sleeper.enter 0 level++ 1 start T2 1 sleeper.wait(100) 1 sleeper.enter 1 level++ 2 sleeper.wait(1000) level– 1 return level = 1 1 enter into if level– 0 [/code]

public class Dream {
    public void dream(Sleeper s) {
        final Sleeper s1 = s;
        //another imaginary thread which breaks user Dream.
        Thread t = new Thread() {
            public void run() {
                class ImagDream extends Dream {
                    public void dream(Sleeper s1) {
                        try {
                            s1.wait(1000);
                        } catch (InterruptedException e) {
                        }
                    }
                };
                s1.enter(new ImagDream());
            }
        };
        t.start();
        try {
            s.wait(100);
        }catch(InterruptedException e){}
    }
}

Ralf wrote on 2012-02-23 21:15

// This is probably not the most elegant solution, but it seems to work.

package dream;

import sleep.Sleeper;

public class Dream {
    boolean first = true;
    public void dream(final Sleeper s) {
        if(!first) {
            // This is the recursive call.
            try {
                // Have to wait for the outer call to return
                s.notifyAll();
                s.wait(100);
            } catch(InterruptedException e) {
                // Ignore
            }
            return;
        }
        first = false;
        Thread t = new Thread() {
            @Override
            public void run() {
                s.enter(Dream.this);
            }
        };


        t.start();
        try {
            // We wait for the inner call to be started.
            s.wait();
        } catch(InterruptedException e) {
            // ignore
        }
    }
}

elek wrote on 2012-02-23 21:18

Very good puzzlers, thx!

class Dream {
    Thread thread;

    public void dream(final Sleeper s) {
        if (thread == null) {

            thread = new Thread(new Runnable() {
                @Override
                public void run() {
                    s.enter(Dream.this);
                }
            });
            thread.start();

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

    }

Joshi wrote on 2012-02-23 21:18

public class Dream {
    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) {
                        synchronized (s) {
                            s.notify();
                        }
                        try {
                            s.wait();
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                    }

                });

            }
        });
//        t.setDaemon(true);
        t.start();

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

Bob Browning wrote on 2012-02-23 21:39

Use wait / notify to break the synchronisation.

package dream;

import sleep.Sleeper;

public class Dream {

    public void dream(final Sleeper s) {
        try {
            Runnable r = new Runnable() {
                public void run() {
                    s.enter(new Dream() {
                        @Override
                        public void dream(Sleeper s) {
                            s.notify();
                            try {
                                s.wait();
                            } catch (InterruptedException ignored) {
                            }
                        }
                    });
                }
            };

            Thread t = new Thread(r);
            t.start();
            s.wait();
        } catch (InterruptedException ignored) {
        }
        s.notify();
    }
}

João Vicente Reis wrote on 2012-02-23 21:50

Here is my solution:

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

import sleep.Sleeper;

public class Dream {
    public void dream(final Sleeper s) {
        s.notifyAll();

        new Thread() {
           public void run() {
              s.enter(new Dream());
           }
        }.start();

        try { s.wait();} catch (Exception ex) {}
    }
}

Stefan wrote on 2012-02-23 22:00

public class Dream {

    boolean run = true;

    public void dream(final Sleeper s) {
        if (run) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    s.enter(Dream.this);
                }
            }).start();
        }
        run = false;
        try {
            s.wait(100);
        } catch (InterruptedException e) {
        }
    }
}

João Vicente Reis wrote on 2012-02-23 22:03

Great puzzle by the way! :)

Paul McGuire wrote on 2012-02-23 22:06

Great puzzles, look forward to seeing more! Heres my solution. Look forward to seeing other peoples.

public class Dream {

    public void dream(Sleeper s) {
        launchDreamThreadToJumpInBlockForever(s);
        waitOnMonitorGivingUpLockBrieflyThenReturn(s);
    }

    // Waits on the monitor - giving it up
    private void waitOnMonitorGivingUpLockBrieflyThenReturn(Sleeper s) {
        synchronized (s) {
            try {
                s.wait(1000);
            } catch (InterruptedException e) {}
        }
    }

    private void launchDreamThreadToJumpInBlockForever(final Sleeper s) {
        Thread t = new Thread() { public void run() {
            Dream d = new WaitForeverDream();
            s.enter(d);
        }};
        t.start();
    }

    class WaitForeverDream extends Dream {

        // When called back will block forever - giving up monitor
        public void dream(final Sleeper s) {
            synchronized (s) {
                try {
                    s.wait();
                } catch (InterruptedException e) {}
            }
        }

    }

}

KI wrote on 2012-02-23 22:25

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

import sleep.*;

public class Dream {
  boolean nest = false;
  public void dream(final Sleeper s) {
        if (!nest) {
              nest = true;
          new Thread() {
              public void run() {
                  s.enter(Dream.this);
              }
          }.start();

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

KI wrote on 2012-02-23 22:47

Thx for interesting puzzle,

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

Gerrit van Brakel wrote on 2012-02-23 22:36

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

import sleep.*;

public class Dream {

    boolean first = true;

    public void dream(final Sleeper s) {
        final Dream d = this;
        if (first) {
            synchronized (s) {
                first = false;
                Thread t = new Thread() {
                    public void run() {
                        s.enter(d);
                    }
                };
                t.start();

                try {
                    s.wait(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        } else {
            s.notify();
            try {
                s.wait(1000);
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
    }
}

Martin wrote on 2012-02-23 22:44

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

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

Jon Kean wrote on 2012-02-23 23:33

public class Dream {
    private static boolean firstCall = true;

    public void dream(final Sleeper s) {
        try {
            if (firstCall) {
                firstCall = false;
                new Thread(new Runnable() {
                    @Override
                    public void run() {
                        System.out.println("starting second dream");
                        s.enter(new Dream());
                    }
                }).start();
                s.wait(); // release synchronized lock, wait for second dream
                s.notify(); // wake up second dream so program closes gracefully
            } else {
                s.notify(); // notify first dream
                s.wait(); // wait until first dream finishes
            }
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
}

Jason Hill wrote on 2012-02-24 00:05

package dream;

import sleep.Sleeper;

public class Dream {
  public void dream(final Sleeper s) {
     final Thread t = new Thread() {
       @Override
       public void run() {
         s.enter(new Dream(){
           @Override
           public void dream(final Sleeper s1) {
             s.notifyAll();

             try {
               s.wait();
             }
             catch(InterruptedException e) {
               throw new RuntimeException(e);
             }
           }
         });
       }
     };

     t.setDaemon(true);
     t.start();

     try {
       s.wait();
     }
     catch(InterruptedException e) {
       throw new RuntimeException(e);
     }
  }
}

Markus Heberling wrote on 2012-02-24 00:25

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

import sleep.Sleeper;

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

        t.setDaemon(true);
        t.start();

        try {
            s.wait();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }


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

per claesson wrote on 2012-02-24 00:51

Hi, mobile and I wont write java using an onscreen kbd, but: I would launch a thread, let main thread wait() on sleeper, let other thread dream a dream which does notify() on sleeper then waits itself. Main thread wakes up and returns with other thread still blocked.

Alexander Filipchik wrote on 2012-02-24 01:05

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 wrote on 2012-02-24 01:20

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 wrote on 2012-02-24 01:40

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 wrote on 2012-02-24 01:44

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 wrote on 2012-02-24 01:48

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 wrote on 2012-02-24 01:52

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 wrote on 2012-02-24 02:56

// 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 wrote on 2012-02-24 02:57

    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 wrote on 2012-02-24 03:02

(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 wrote on 2012-02-24 03:18

Another solution :D 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 wrote on 2012-02-24 04:03

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 wrote on 2012-02-24 05:20

// 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

Wouter wrote on 2012-02-26 18:41

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?

Sam wrote on 2012-02-24 05:21

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 wrote on 2012-02-24 06:20

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 wrote on 2012-02-24 07:33

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.

Wouter wrote on 2012-02-26 18:24

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.

Muel wrote on 2012-02-24 08:06

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 wrote on 2012-02-24 08:13

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 wrote on 2012-02-24 10:03

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 wrote on 2012-02-24 10:09

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 wrote on 2012-02-24 10:24

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 wrote on 2012-02-24 10:24

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 wrote on 2012-02-24 10:35

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 wrote on 2012-02-24 11:05

    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 wrote on 2012-02-24 11:08

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 wrote on 2012-02-24 11:10

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 wrote on 2012-02-24 11:44

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 wrote on 2012-02-24 11:47

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 wrote on 2012-02-24 12:15

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 wrote on 2012-02-24 13:52

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 wrote on 2012-02-24 14:33

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 wrote on 2012-02-24 15:02

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 wrote on 2012-02-24 15:04

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 wrote on 2012-02-24 15:07

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 wrote on 2012-02-24 15:30

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 wrote on 2012-02-24 15:34

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 wrote on 2012-02-24 15:47

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 wrote on 2012-02-24 16:10

// 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 wrote on 2012-02-24 16:10

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 wrote on 2012-02-24 16:51

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();
    }
  }

}

Jan Christoph Thoelken wrote on 2012-02-24 16:52

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.

Silviu Julean wrote on 2012-02-24 16:58

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 wrote on 2012-02-24 17:51

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 wrote on 2012-02-24 18:11

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 wrote on 2012-02-24 18:13

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 wrote on 2012-02-24 18:33

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 wrote on 2012-02-24 18:45

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 wrote on 2012-02-24 18:50

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 wrote on 2012-02-24 19:23

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 wrote on 2012-02-24 21:29

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 wrote on 2012-02-24 21:50

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 wrote on 2012-02-24 21:58

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();
            }
        }

    }
}

Marcel Hanser wrote on 2012-02-24 22:08

package dream;

import sleep.Sleeper;

public class Dream {
    private Thread athread;

    public void dream(final Sleeper sleeper) {
        final Dream current = this;
        if (athread == null) {
            System.out.println("Creating new Thread");
            athread = new Thread(new Runnable() {

                @Override
                public void run() {
                    sleeper.enter(current);
                }
            });
            athread.start();
            try {

                synchronized (sleeper) {
                    System.out.println("set the current on sleep;)");
                    sleeper.wait();
                }
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        } else {
            System.out
                    .println("now we added 1 to the level, notify the first and sleep");
            sleeper.notify();
            synchronized (sleeper) {
                try {
                    sleeper.wait();
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
        }
    }
}

Markus Keller wrote on 2012-02-24 22:38

Thanks for these great puzzles!

Here’s a commented solution. As always with concurrency, I find it hard to prove whether the solution is safe, but I think it is. I’m not sure though, whether “volatile” is necessary.

package dream;

import sleep.Sleeper;

public class Dream {

    private volatile boolean flag;

    public void dream(final Sleeper s) {
        if (!flag) {
            // In first dream, start a thread that will enter a second dream:
            flag= true;
            new Thread() {
                @Override
                public void run() {
                    s.enter(Dream.this);
                }
            }.start();

            // Wait until second dream has started:
            do {
                try {
                    // Release monitor, so that the second dream can start:
                    s.wait(10);
                } catch (InterruptedException e) {
                }
            } while (flag); // Repeat until second dream really started.

            // Now, the first dream can end while the second is still ongoing.

            // Notify the second dream that it can end. This is safe since
            // the first dream still holds the sleeper's monitor.
            s.notify();

        } else {
            // In 2nd dream, set flag to false and then wait for termination:
            flag= false;
            try {
                s.wait();
            } catch (InterruptedException e) {
            }
        }
    }
}

Paul Martin wrote on 2012-02-24 22:54

That was fun - hadn’t really thought of the relationship between synchronized methods and wait and notify before!

// this is the only file you're allowed to edit
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 DreamForever());
            }
        }).start();    // Start a new inner dream, will be blocked on Sleeper
        try {
            s.wait();    // Relinquish control of Sleeper to inner dream, and wait to be notified once inner has started
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
}

class DreamForever extends Dream {

    @Override
    public void dream(Sleeper s) {
        s.notifyAll();        // Notify (the parent dream)
        try {
            s.wait(5000L);    // And then relinquish control and wait for a notification (that will never come).
                            // 5 seconds should be enough time for the parent thread to finish (could wait forever though)
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
}

Daniel Simoes wrote on 2012-02-24 23:00

My version.

http://pastebin.com/7E5Prbgd

Great puzzle!! Thanks.

Paul Martin wrote on 2012-02-24 23:12

Oh, I guess that you don’t really need separate Dream classes (especially if you don’t mind infinite loops & threads, though you could implement a static counter to limit them)

// this is the only file you're allowed to edit
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 Dream());
            }
        }).start();
        s.notifyAll();
        try {
            s.wait();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
}

Tomasz Biedka wrote on 2012-02-24 23:13

package dream;

import sleep.Sleeper;

public class Dream {

    private static Sleeper sleeper;

    public void dream(final Sleeper s) {
        try {
            dreamInternal(s);
        } catch (InterruptedException ignore) {
        }
    }

    private void dreamInternal(Sleeper s) throws InterruptedException {
        if (sleeper == null) {
            sleeper = s;
            mainThreadDream(s);
        } else {
            additionalThreadDream(s);
        }
    }

    private void mainThreadDream(Sleeper s) throws InterruptedException {
        Thread additionalThread = createAdditionalThread(s);
        additionalThread.start();
        s.wait(); // wait for notify() from additionalThread
        additionalThread.interrupt();
    }

    private Thread createAdditionalThread(Sleeper s) {
        final Dream dream = this;
        return new Thread(new Runnable() {
            public void run() {
                sleeper.enter(dream);
            }
        });
    }

    private void additionalThreadDream(Sleeper s) throws InterruptedException {
        s.notify();
        s.wait();  // wait for interrupt() from mainThread
    }
}

sico wrote on 2012-02-24 23:21

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

import sleep.Sleeper;

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

        try {
            s.wait();
        } catch (Exception e1) {
            e1.printStackTrace();
        }
    }
}

class NeverEndingDream extends Dream {
    public void dream(Sleeper s) {
        try {
            s.notifyAll();
            s.wait();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Thomas wrote on 2012-02-24 23:38

Hi,

I’m a bit late with my entry but here it comes: it’s a dream that spawns another dream and waits for the second dream to start which will then cause the first dream to finish and then the night is over before the second dream came to its end. Don’t we all know this strange feeling when waking up and having some unfinished matters still on our minds?

Actually I found this puzzle a lot easier than the one with the clowns. Maybe because it is closer to what I have to deal with (i.e. debug) during my daily work.

BTW, I love this kind of puzzles, thank you!

Kind regards, Thomas

package dream;

import java.util.*;
import sleep.Sleeper;

public class Dream extends TimerTask {

  Sleeper sleeper;

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

  public void dream(final Sleeper s) {
    if (sleeper == null) {
      sleeper = s;
      new Timer(true).schedule(this, 100);
    } else {
      s.notify();
    }
    try {
      s.wait();
    } catch (InterruptedException ex) {}
  }
}

eyrieowl wrote on 2012-02-24 23:59

public class Dream {
   public void dream(final Sleeper s) {
      Thread t = new Thread() {
            @Override
            public void run() {
               s.enter(new Dream() {
                     @Override
                     public void dream(Sleeper s) {
                        try {
                           synchronized (s) {
                              s.notify();
                              s.wait();
                           }
                        }
                        catch (InterruptedException e) {
                           throw new RuntimeException(e);
                        }
                     }
                  });
            }
         };
      t.start();

      try {
         synchronized (s) {
            s.wait();
         }
      }
      catch (InterruptedException e) {
         throw new RuntimeException(e);
      }
   }
}

catac wrote on 2012-02-25 00:20

You can fool the Sleeper by doing a ping-pong with another thread, stealing Sleeper’s lock to insert an extra dream:

package sleep;

import java.util.concurrent.atomic.AtomicBoolean;

public class Dream {
    private AtomicBoolean firstTime = new AtomicBoolean(true);

    public void dream(final Sleeper s) {
        try {
            if (firstTime.getAndSet(false)) {
                new Thread() {
                    @Override
                    public void run() {
                        s.enter(Dream.this);
                    }
                }.start();
                synchronized (s) {
                    s.wait();
                    s.notify();
                }
            } else {
                synchronized (s) {
                    s.notify();
                    s.wait();
                }
            }
        } catch (InterruptedException e) {
            // don't care
        }
    }
}

finnw wrote on 2012-02-25 00:23

package dream;

import sleep.Sleeper;

public class Dream {

    private static class StrangeDream extends Dream implements Runnable {
        public void dream(Sleeper s) {
            s.notify();
            try {
                s.wait();
            } catch (InterruptedException ex) {
            }
        }
        public void run() {
            s.enter(this);
        }
        StrangeDream(Sleeper s) {
            this.s = s;
        }
        private Sleeper s;
    }

    public void dream(Sleeper s) {
        new Thread(new StrangeDream(s)).start();
        try {
            s.wait();
        } catch (InterruptedException ex) {
        }
        s.notify();
    }

}

finnw wrote on 2012-02-25 01:00

I should probably add a Thread.sleep() after the wait in StrangeDream.dream(Sleeper) - I think there’s a race as it stands.

slavarosin wrote on 2012-02-25 00:49

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

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

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

mentallurg wrote on 2012-02-25 02:02

Dream of unlimited depth can be created. The limit depends on your resources only, i.e. on how many threads can your JVM create under you OS with its default RAM. In this example it is set to 100. You can see the level, if you add one logging line to the Main class.

package dream;

import sleep.Sleeper;

public class Dream {

    private int count = 0;

    private static final int DREAM_DEPTH = 100;

    public void dream(final Sleeper s) {
        if (count++ <= DREAM_DEPTH) {
            new Thread() {
                public void run() {
                    s.enter(Dream.this);
                };
            }.start();
        } else {
            s.notify();
            return;
        }

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

        s.enter(this);
        s.notify();
    }
}

mentallurg wrote on 2012-02-25 02:07

If smb wants to check the real level, logging can be added as follows:

package sleep;

import dream.Dream;

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

mentallurg wrote on 2012-02-25 02:09

… and to get the better feeling about what is going on, a single logging line can be added to the Sleeper:

package sleep;

import dream.Dream;

public class Sleeper {
    private int level;

    public synchronized int enter(Dream dream) {
        level++;
        try {
            dream.dream(this);
        } finally {
            level--;
        }
        System.out.println("level=" + level);
        return level;
    }
}

Paul Michael Bauer wrote on 2012-02-25 05:15

package dream;
import sleep.Sleeper;

public class Dream {
    public void dream(final Sleeper s) {
        Thread t = new Thread(new Runnable() {
            public void run() {
                s.enter(new Dream() {
                    public void dream(Sleeper s) {
                        s.notify();
                        wait(s);
                    }
                });
            }
        });
        t.setDaemon(true);
        t.start();
        wait(s);
    }

    protected static void wait(Sleeper s) {
        try {
            s.wait();
        } catch (InterruptedException ignored) {
        }
    }
}

Erik Kuefler wrote on 2012-02-25 05:23

synchronized does indeed keep multiple threads from running at once inside a given method - but it doesn’t stop one thread from running while others are waiting. This code works on my machine:

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

Dmitriy Likhten wrote on 2012-02-25 06:29

https://github.com/dlikhten/dreams

That contains the solution. You can’t use the security manager via intellij (it’s all set to go) but you can see that it is unnecessary as I don’t need the features of setAccessible. And it runs from command line :) Pretty simple actually, especially when you use drugs when you go sleep.

lexa wrote on 2012-02-25 08:59

package dream;

import sleep.Sleeper;

public class Dream {

    boolean firstEnter = true;

    public void dream(Sleeper s) {
       if (firstEnter) {
            System.out.println("first dream ...");
            firstEnter = false;
            // create one more thread with recursion call
            final Sleeper sleeper = s;
            final Dream dream = this;
            new Thread(
                new Runnable() {
                    public void run() {
                        System.out.println("start another sleeper dream ...");
                        sleeper.enter(dream);
                    }
                }
            ).start();

            // another critical section by sleeper
            // even though we are inside
            synchronized (s) {
                try {
                    System.out.println("first dream is put on wait ...");
                    // pause execution and release monitor
                    s.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            // we get out of waiting
            System.out.println("first dream goes further ...");
            // wake other dreams
            s.notifyAll();
        } else {
            System.out.println("another dream ...");
            System.out.println("wake first one ...");
            // wake other dreams
            s.notifyAll();
            // another critical section by sleeper
            // even though we are inside
            synchronized (s) {
                try {
                    System.out.println("another dream is put on wait ...");
                    // pause execution and release monitor
                    s.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            //some pause, just for proper order of outs
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            // we get out of waiting
            System.out.println("another dream goes further ...");
        }

    }
}

Chris wrote on 2012-02-25 10:32

This seems to work.

    public void dream(final Sleeper s) {

        synchronized (s) {
            new Thread() {
                public void run() {
                    s.enter(new Dream());
                }
            }.start();
            try {
                s.notify();
                s.wait();
            } catch (Exception e) {

            }

        }
    }

Martin Hilton wrote on 2012-02-25 17:10

// 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 Runner(s));
        t.setDaemon(true);
        t.start();

        wait(s);
    }

    protected void wait(Sleeper s) {
        synchronized (s) {
            try {
                s.wait();
            } catch (InterruptedException e) { }
        }
    }

    private static class Runner implements Runnable {
        private Sleeper s;

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

        public void run() {
            s.enter(new Dream2());
        }
    }

    private static class Dream2 extends Dream {
        public void dream(Sleeper s) {
            synchronized (s) {
                s.notify();
            }

            wait(s);
        }
    }
}

Algirdas wrote on 2012-02-25 19:20

package dream;

import sleep.Sleeper;

/**
 * Endlessly parallel dream.
 */
public class Dream {

  public void dream(Sleeper sleeper) {
    fallAsleepInParallelUniverse(sleeper);
    wakeUpInParallelUniverse(sleeper);
    sleepTillWakenUp(sleeper);
  }

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

  private void wakeUpInParallelUniverse(Sleeper sleeper) {
    sleeper.notify();
  }

  private void sleepTillWakenUp(Sleeper sleeper) {
    try {
      sleeper.wait();
    } catch (InterruptedException e) {
    }
  }

}

Filip wrote on 2012-02-25 20:35

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

import sleep.Sleeper;

public class Dream {
    public void dream(final Sleeper s1) {
        new Thread() {
            public void run() {
                synchronized (s1) {
                    s1.enter(new Dream(){
                        @Override
                        public void dream(Sleeper s1) {
                            s1.notify();
                            try {
                                s1.wait();
                            } catch (InterruptedException e) {
                                e.printStackTrace();
                            }
                        }
                    });
                }
            }
        }.start();

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

}

Jan Schäfer wrote on 2012-02-25 20:51

package dream;

import sleep.Sleeper;

public class Dream {
    public void dream (final Sleeper s) {
        // call enter in a different thread
        new Thread() {
            @Override
            public void run () {
                s.enter(new SpecialDream());
            };
        }.start();

        try {
            // give SpecialDream possibility to enter monitor
            s.wait();
            // terminate SpecialDream
            s.notifyAll();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    static class SpecialDream extends Dream {

        @Override
        public void dream (Sleeper s) {
            try {
                // in monitor now, wake up Dream
                s.notifyAll();
                // give Dream possibility to enter monitor
                s.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

Alessandro Abbruzzetti wrote on 2012-02-26 00:16

Hi, I used a supplementary thread in order to increment the level counter and wait 2 seconds meanwhile the primary calling thread is waiting only 1 second. In this way the check on the level variable will be done while the supplementary thread is still waiting on a wait condition: A a result we will have the level counter with a value of 2.

public class Dream {
int state = 0;
public void dream(Sleeper s) {
if (state == 1) synchronized (s) {
try { s.wait(2000); } catch (Exception e) {}
return;
}
final Sleeper s1 = s;
new Thread() {
public void run() { state =1; s1.enter(Dream.this);}
}.start();
try { synchronized { s.wait(1000); } } catch (Exception e) {}
}
}

Yann Massard wrote on 2012-02-26 00:37

package dream;

import sleep.Sleeper;

public class Dream {

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

Yann Massard wrote on 2012-02-26 00:39

actually lower synchronized block is not needed…

Ludovic Claude wrote on 2012-02-26 01:15

Sleeping other this problem was a good idea. I found a solution:

package dream;

import sleep.Sleeper;

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.Executor;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

public class Dream {

    private static Executor executor = Executors.newFixedThreadPool(128);
    private static CountDownLatch dreamsLatch = new CountDownLatch(128);
    private static AtomicInteger wakingUp = new AtomicInteger(128);

    public void dream(Sleeper s) {

        for (int i = 0; i < 128; i++) {
            executor.execute(new WaitingDream(s));
        }
        try {
            synchronized(s) {
                System.out.println("Gathering sheeps...");
                dreamsLatch.await();
                System.out.println("Counting sheeps...");
                s.wait(10000);
                System.out.println("Wake up!");
                s.notifyAll();
                System.out.println("Grumble grumble...");
                while (wakingUp.get() > 10) {
                    s.notifyAll();
                }
                System.out.println("I'm awake");
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

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

    static Dream inner = new SimpleDream();

    static class WaitingDream extends Dream implements Runnable {
        private final Sleeper sleeper;

        public WaitingDream(Sleeper s) {
            sleeper = s;
        }

        public void dream(Sleeper s) {
            s.enter(inner);
        }

        public void run() {
            try {
                dreamsLatch.countDown();
                sleeper.enter(this);
            } catch (Exception e) {
                e.printStackTrace();
            }
            wakingUp.decrementAndGet();
            System.out.print(".");
        }
    }
}

Nicolas Pirard wrote on 2012-02-26 23:21

@Ludo : t’es un grand malade!

@Wouter : thank you for sharing thoses puzzles! Had a nice time burning some neurons on them, will have another nice time bashing some colleagues and friends tomorrow :-)

Alex Dvinsky wrote on 2012-02-26 11:27

public void dream(final Sleeper s)
{
    Thread t = new Thread()
    {
        public void run()
        {
            try { Thread.sleep(1000); } catch (InterruptedException e) {}
            s.enter(new LongDream());
            synchronized (s) { Dream.this.notifyAll(); }
    };

    t.setDaemon(true);
    t.start();
    try { s.wait(); } catch (InterruptedException e) {}
}

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

Wouter wrote on 2012-02-26 18:11

======================================================= Any comments above these line were made before the solution came out. Anything below comes after. If there is anything between the lines, clean your monitor.

finnw wrote on 2012-02-26 18:43

If you make this change to the Sleeper class, none of the posted solutions will work anymore…

package sleep;

import dream.Dream;

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

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

I wonder if it is still possible to break it like this?

Wouter wrote on 2012-02-26 18:57

I don’t expect it’s possible to break that. But I’d love to be surprised.

Roel Spilker wrote on 2012-02-27 10:55

If you use Project Lombok, you can write:

@Synchronized public int enter(Dream dream) {
    // original implementation
}

The @Synchronized will create the lock field for you and wraps the entire method content in a synchronized block.

See http://projectlombok.org/features/Synchronized.html for more information.

Disclaimer, I’m one of the Project Lombok developers.

Jonathan Fisher wrote on 2012-02-26 21:11

Simply awesome! I wish we could do this daily not weekly!!!

Markus Keller wrote on 2012-02-26 23:18

Concurrency devils are disturbing your dreams ;-)

The “official” solution is not guaranteed to reach the goal line. Just set a breakpoint on line 16 at s.enter(new Dream() { and debug.

You’ll always wake up in the cold reality.

If you remove the timeout from s.wait(200); and insert s.notify(); before doWait(s); in the inner dream and after doWait(s); in Dream#dream(..), then you get the sweet dream in many more cases.

But to be completely safe, every invocation of wait(..) needs to be performed inside a loop (see the Javadoc).

Wouter wrote on 2012-02-26 23:25

You’re right.

I was being lazy, and something that works 99.99% of the time unless you intentionally make it not work (by setting a breakpoint) seems good enough for this puzzle. I also didn’t want to make the sequence diagram any more complicated than it already is.

It needs an extra “Kids, don’t write code like this for real” disclaimer.

Tim Lammens wrote on 2012-02-27 01:26

I can only agree with this comment ;P

Yakov wrote on 2012-02-27 21:15

Guys,

It seems that almost all of you forget to wrap wait calls in a cycle. It seems to be wrong.

Wouter wrote on 2012-02-27 22:30

It has many more things wrong with it. It relies on an implementation detail of the locking of the Sleeper; it does a frick’n .wait() on someone else’s lock. It also does complicated things without commenting why, it’s lacking javadoc and unit tests. Solutions to previous and next puzzles have done and will do things that make my wrongness-meter go much more into the red then any of that.

The whole point of these puzzles is to break the conventional rules. The usual wrong or correct don’t apply here. All that matters is that it’s fun, it seems to work when you run it, and that others can understand why it works. And in my opinion, it also leads to a whole different kind of code beauty.

nothize wrote on 2012-02-29 13:39

Thanks for the exercise for concurrency programming in Java.

Hanson Char wrote on 2012-03-01 06:55

package dream;

import sleep.Sleeper;

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

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

Christoph wrote on 2012-03-07 18:12

I think the original task is a bit confusing because of the “// TODO implement me” in the dream method. I thought this is the only location you may modify but in your solution you added a method to the class.

Wouter wrote on 2012-03-07 20:48

It doesn’t really change anything to the puzzle; you can just as easily do it without that extra method.

drieu wrote on 2012-09-05 18:23

I’m happy ! I found the solution ! Not easy but It was interesting. Thanks.