Feb

2012

Java Puzzle 2: Dreams – Solution

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

package sleep;

import dream.Dream;

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

package sleep;

import dream.Dream;

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

Solution

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

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

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

package dream;

import sleep.Sleeper;

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

And the winner is…

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

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

Conclusion

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

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

public class Sleeper {
	private final Object lock = new Object();
	
	public int dream(Dream dream) {
		synchronized(lock) {
			...
		}
	}
}

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

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

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

Frank Meulenaar says:

February 23, 2012 at 1:19 pm

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.

Reply

David Shay says:

February 23, 2012 at 1:52 pm

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 says:

March 4, 2012 at 12:38 pm

This is more cleaner version.

Reply

Yury Vasyutinskiy says:

February 23, 2012 at 1:58 pm

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 says:

February 23, 2012 at 2:00 pm

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 says:

February 23, 2012 at 2:16 pm

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 says:

February 23, 2012 at 2:28 pm

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 says:

February 23, 2012 at 2:28 pm

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

Reply

Carsten Lenz says:

February 23, 2012 at 2:37 pm

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 says:

February 23, 2012 at 2:42 pm

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 says:

February 23, 2012 at 2:47 pm

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 says:

February 23, 2012 at 2:51 pm

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

February 23, 2012 at 3:28 pm

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

Reply

Jarl Petter Kvalsvik says:

February 23, 2012 at 4:15 pm

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 says:

February 23, 2012 at 4:27 pm

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

February 23, 2012 at 4:29 pm

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 says:

February 23, 2012 at 4:32 pm

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 says:

February 23, 2012 at 4:32 pm

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 says:

February 23, 2012 at 5:15 pm

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 says:

February 23, 2012 at 5:16 pm

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 says:

February 23, 2012 at 5:17 pm

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 says:

February 23, 2012 at 5:17 pm

Quick and dirty solution:

package dream;

import sleep.Sleeper;

public class Dream  {
	int counter = 0;

	public void dream(final Sleeper s) {
		if (++counter &lt; 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 says:

February 23, 2012 at 5:18 pm

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 says:

February 23, 2012 at 5:27 pm

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 says:

February 23, 2012 at 5:35 pm

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 says:

February 23, 2012 at 5:35 pm

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 says:

February 23, 2012 at 5:36 pm

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

Reply

Alex Snaps says:

February 23, 2012 at 5:37 pm

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 says:

February 23, 2012 at 5:48 pm

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 says:

February 23, 2012 at 6:16 pm

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 says:

February 23, 2012 at 6:22 pm

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 says:

February 23, 2012 at 6:26 pm

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 says:

February 23, 2012 at 6:26 pm

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 says:

February 23, 2012 at 6:33 pm

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 says:

February 23, 2012 at 7:17 pm

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 says:

February 23, 2012 at 7:59 pm

Yes, it’s possible using another thread.
1. Once user increases level counter inside Dream.dream() method,
2. Trigger another thread
3. Release the synchronize lock (using object.wait() with timeout)
4. meanwhile another thread will acquire synchronize lock and will also increase level.
5. Now, inovke object.wait() from second thread, with some sufficient long timeout.
6. 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.

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

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 says:

February 23, 2012 at 8:15 pm

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

February 23, 2012 at 8:18 pm

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 says:

February 23, 2012 at 8:18 pm

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 says:

February 23, 2012 at 8:39 pm

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 says:

February 23, 2012 at 8:50 pm

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 says:

February 23, 2012 at 9:00 pm

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 says:

February 23, 2012 at 9:03 pm

Great puzzle by the way!

Reply

Paul McGuire says:

February 23, 2012 at 9:06 pm

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 says:

February 23, 2012 at 9:25 pm

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

February 23, 2012 at 9:47 pm

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 says:

February 23, 2012 at 9:36 pm

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

February 23, 2012 at 9:44 pm

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 says:

February 23, 2012 at 10:33 pm

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 says:

February 23, 2012 at 11:05 pm

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 says:

February 23, 2012 at 11:25 pm

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

February 23, 2012 at 11:51 pm

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.

Reply

Java Puzzle 2: Dreams – Solution

Solution

And the winner is…

Conclusion

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

Leave a comment

Menu

Recent Posts

Archives

Search