Mar

2012

Java Puzzle 6: Chicken or the Egg – Solution

Here’s the solution to the Chicken or the Egg puzzle.

The constructor of Egg throws a NullPointerException if it’s not given a (non-null) Chicken, and vice versa for the Chicken constructor. So how can you get a reference to either of them?

A common flaw that makes this possible (and even happen by accident) is calling a method that can be overridden in a subclass from a constructor. But that’s not the case here. There’s one method you can override that the constructor doesn’t call, but Java calls eventually: finalize(). That method is called before an object is garbage collected, to give it a chance to clean up its resources. It is called even if the constructor threw an exception, so by overriding it we can get a reference to an egg that wasn’t fully created.

package creator;

import chicken.Chicken;
import chicken.Egg;

public class Creator {
    static class FirstEgg extends Egg {
        FirstEgg() {
            super(null);
        }

        @Override
        protected void finalize() {
            new Chicken(this).ask();
        }
    }

    public static void main(String[] args) throws Exception {
        try {
            new FirstEgg();
        } catch (NullPointerException e) {
        }
        
        // there are ways to force garbage collection harder,
        // but this works good enough for me 
        System.gc();
        System.runFinalization();
        Thread.sleep(1000);
    }
}

It’s well known that the finalization mechanism has several problems, and there are better alternatives. There are multiple ways to defend against this listed on the this secure coding standard for Java. Another way is to throw the exception before calling the constructor from the Object class. That means doing the work before calling super() (or another constructor with this()). Since Java 6, this guarantees that finalize() won’t be called. For example here we dereference mom.first before calling this(Object) to ensure you cannot create an egg without a mommy:

public class Egg {
    final Object first;
    
    public Egg(Chicken mom) {
        this(mom.first);
    }
    
    private Egg(Object first) {
        this.first = first;
    }
}

Congrats to the 17 people who found it. Matt Nathan was the first but it’s still a mystery if he’s a chicken, an egg or a null.

P.S.: The puzzles are taking a short vacation. They’ll continue in a few weeks.

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

18 comments to “Java Puzzle 6: Chicken or the Egg – Solution”

Matt Nathan says:

March 22, 2012 at 2:00 pm

package creator;

import chicken.Chicken;

public class Creator {
  private static Chicken reference;

  public static void main(String[] args) {
    try {
      new Chicken(null) {
        @Override
        protected void finalize() throws Throwable {
          reference = this;
        }
      };
    } catch (NullPointerException ignore) {}

    while (reference == null) {
      System.gc();
    }
    reference.ask();
  }
}

Chris says:

March 22, 2012 at 9:16 pm

Nice one. Finally i figured out one

package creator;

import chicken.Chicken;
import chicken.Egg;

public class Creator {

	public static Egg brokenEgg;

	public static void main(String[] args) {
		try {
			new BrokenEgg();
		} catch (Exception e) {
			//Empty catch blocks are usually a bad idea...
		}
		
		System.gc();
		System.runFinalization();
		
		Chicken macFly = new Chicken(brokenEgg);
		macFly.ask();
	}

	static class BrokenEgg extends Egg {
		public BrokenEgg() {
			super(null);
		}

		@Override
		protected void finalize() throws Throwable {
			brokenEgg = this;
		}
	}
}

Pawel says:

March 22, 2012 at 9:53 pm

package creator;
 
import chicken.Chicken;
import chicken.Egg;
 
public class Creator {
	static volatile MyEgg egg;
	
	public static class MyEgg extends Egg {
		public MyEgg(Chicken chicken) {
			super(chicken);
		}

		@Override
		protected void finalize() throws Throwable {
			egg = this;
		}
	}
	
    public static void main(String[] args) {
    	try {
    		new MyEgg(null);
    	}
    	catch (Exception e) {
    		System.gc();
    		while (egg == null);
    		new Chicken(new Egg(new Chicken(egg))).ask();
    	}
    }
}

Keith Amling says:

March 22, 2012 at 10:20 pm

import java.util.concurrent.atomic.AtomicBoolean;

import chicken.Chicken;

public class Main {
    private static final AtomicBoolean done = new AtomicBoolean(false);

    public static void main(String[] args) {
        try {
            new BadChicken();
        }
        catch(NullPointerException e) {
            // that's fine
        }
        while(!done.get()) {
            System.gc();
        }
    }

    public static class BadChicken extends Chicken {
        public BadChicken() {
            // bewm
            super(null);
        }

        @Override
        protected void finalize() {
            ask();
            done.set(true);
        }
    }
}

mihi says:

March 22, 2012 at 11:03 pm

“First there was the null”

Reason (and description how it works): https://www.securecoding.cert.org/confluence/display/java/OBJ11-J.+Be+wary+of+letting+constructors+throw+exceptions

My solution
```
package creator;

import chicken.Chicken;

public class Creator {
	public static void main(String[] args) {
		try {
			new Chicken(null) {
				protected void finalize() {
					ask();
				}
			};
		} catch (NullPointerException ex) {
			System.gc();
			System.runFinalization();
		}
	}
}
```
BTW I’m really curious how Java8 (in case the standard annotations from the Checker framework will make it into javac this time…) will handle the case if you declare first to be @NonNull and perform such a stunt. Probably the nullness checks will only be performed at compilation time, just like Generics.

Reply

Heinz Kabutz says:

March 23, 2012 at 7:02 am

Easy peasy

package creator;

import chicken.*;

public class Creator {
  public static void main(String[] args) {
    final Egg[] specialEgg = {null};
    try {
      new Egg(null) {
        protected void finalize() throws Throwable {
          specialEgg[0] = this;
        }
      };
    } catch (NullPointerException ignore) {
    }

    while (specialEgg[0] == null) {
      System.gc();
    }
    new Chicken(specialEgg[0]).ask();
  }
}

David Shay says:

March 23, 2012 at 9:35 am

The first Chicken was a Zombie…

package creator;

import chicken.Chicken;
import chicken.Egg;

public class Creator {
    private static Chicken theFirstChicken;

    public static void main(String[] args) {
        Creator Him = new Creator();
        Him.createFristChicken();
        Chicken chicken = new Chicken(new Egg(theFirstChicken));
        chicken.ask();
    }

    private void createFristChicken() {
        try {
            new ZombieChicken();
        }
        catch (NullPointerException e) {
            //My chicken just died
        }

        for (int i = 0; i < 10; i++) {
            System.gc();
            System.runFinalization();
        }

        synchronized (this) {
            while (theFirstChicken == null) {
                try {
                    wait();
                }
                catch (InterruptedException e) {
                }
            }
        }
    }

    class ZombieChicken extends Chicken {
        public ZombieChicken() {
            super(null);
        }

        @Override
        protected void finalize() throws Throwable {
            synchronized (Creator.this) {
                theFirstChicken = this;
                Creator.this.notify();
            }
        }
    }
}

Jean-Baptiste Perriot says:

March 23, 2012 at 4:46 pm

Resurection is mainstream

    public static void main(String[] args) throws InterruptedException {
        Chicken1 c = null;
        try {
            c = new Chicken1(null);
        } catch (Exception e) {
        }
        System.gc();
        while (c.instance == null) {
            Thread.sleep(100);
        }
        new Chicken(new Egg(c.instance)).ask();
    }

    public static class Chicken1 extends Chicken {
        public static Chicken1 instance;

        public Chicken1(Egg egg) {
            super(egg);
        }

        @Override
        public void finalize() {
            instance = this;
        }
    }

Bas de Bakker says:

March 23, 2012 at 6:01 pm

As the creator, we can create the chicken without the egg. But what was first remains unclear…

public class Creator {
	public static void main(String[] args) {
		try {
			new Chicken(null) {
				protected void finalize() {
					ask();
					System.exit(1);
				}
			};
		} catch (NullPointerException e) {
		}
		for (;;) {
			byte[] garbage = new byte[1024];
		}
	}
}

Oleg Šelajev says:

March 23, 2012 at 6:53 pm

Cool puzzle

package creator;

import chicken.Chicken;
import chicken.Egg;

public class Creator {
  public static void main(String[] args) throws Throwable {
    try {
      new SuperEgg();
    }
    catch (NullPointerException e) {
    }
    for (int i = 0; i < 1<<10; i++) {
      Runtime.getRuntime().gc();
    }
  }

  private static class SuperEgg extends Egg {
    public SuperEgg() {
      super(null);
    }

    protected void finalize() throws Throwable {
      new Chicken(this).ask();
    }
  }
}

Alexander Filipchik says:

March 23, 2012 at 7:25 pm

public class Creator {
    public static void main(String[] args) {
        Chicken chicken = MyChicken.get();
        chicken.ask();
    }

    public static class MyChicken extends Chicken {

        public MyChicken() {
            super(null);
        }

        private static Chicken stealInstance = null;

        public static Chicken get() {
            try {
                new MyChicken();
            } catch (Exception ex) {/* ignore exception */}
            try {
                synchronized (Chicken.class) {
                    while (stealInstance == null) {
                        System.gc();
                        Chicken.class.wait(10);
                    }
                }
            } catch (InterruptedException ex) {
                return null;
            }
            return stealInstance;
        }

        public void finalize() {
            synchronized (Chicken.class) {
                stealInstance = this;
                Chicken.class.notify();
            }
        }
    }
}

Aminur Rashid says:

March 23, 2012 at 7:43 pm

Thanks for this. Was aware of this from a banking project.


package creator;

import chicken.Chicken;
import chicken.Egg;

public class Creator extends Egg {
    private static Creator badEgg = null;

    Creator(Chicken e) {
        super(e);
    }

    public static Creator get() {
        try {
            new Creator(null);
        } catch (Exception ex) { 
            //Who cares. It is expected.
        }
        try {
            synchronized (Creator.class) {
                while (badEgg == null) {
                    System.gc();
                    Creator.class.wait(10);
                }
            }
        } catch (InterruptedException ex) {
            return null;
        }
        return badEgg;
    }

    public void finalize() {
        synchronized (Creator.class) {
            badEgg = this;
            Creator.class.notify();
        }
    }

    public static void main(String[] args) {
        Creator creator = Creator.get();
        Chicken goodChicken = new Chicken(creator);
        goodChicken.ask();
    }
}

lauri says:

March 23, 2012 at 10:32 pm

package creator;
 
import chicken.Chicken;
 
public class Creator {
  static volatile Chicken c;
  
  public static void main(String[] args) {
    try {
      new Chicken(null) {
        public void finalize() {
          c = this;
        };
      };
    }
    catch (Exception e) {
    }

    StringBuilder sb = new StringBuilder();
    while (c == null) {
      sb.append("aaaaaaaaaaa");
    }

    c.ask();
  }

}

Juan Tamayo says:

March 24, 2012 at 4:34 am

Here’s the code for a Creator class that does the job:

public class Creator {
	static Egg seed;
	public static void main(String[] args) throws InterruptedException {
		try {
			new Egg(null) {
				@Override
				protected void finalize() throws Throwable {
					seed = this;
					super.finalize();
				}
			};
		} catch (Exception e) {
			System.gc(); // sort of make sure finalize is invoked
			Thread.sleep(200);
			new Chicken(seed).ask();
		}
	}
}

polygenelubricants says:

March 26, 2012 at 8:47 am

package creator;

import java.util.concurrent.Semaphore;

import chicken.Chicken;
 
public class Creator {
	
	public static void main(String[] args) throws InterruptedException {
		final Semaphore done = new Semaphore(0);
		try {
			new Chicken(null) {
				@Override
				protected void finalize() {
					this.ask();
					done.release();
				}
			};
		} catch (NullPointerException e) {
			System.gc();
			done.acquire();
		}
    }
}

polygenelubricants says:

March 26, 2012 at 8:47 am

package creator;

import java.util.concurrent.Semaphore;

import chicken.Chicken;
 
public class Creator {
	
	public static void main(String[] args) throws InterruptedException {
		final Semaphore done = new Semaphore(0);
		try {
			new Chicken(null) {
				@Override
				protected void finalize() {
					this.ask();
					done.release();
				}
			};
		} catch (NullPointerException e) {
			System.gc();
			done.acquire();
		}
    }
}

Marc Fortin says:

March 26, 2012 at 4:19 pm

Easy:

package creator;

import chicken.Chicken;
import chicken.Egg;
 
public class Creator {
	public static Chicken c = null;
	
    public static void main(String[] args) {
		try {
		    new BadChicken(null);	
		}
		catch (Exception e) {
		}
		
		while(c==null) {
			System.gc();			
		}
		
		c.ask();
        
    }

    public static class BadChicken extends Chicken {
    	
		public BadChicken(Egg egg) {
			super(egg);
		}

		public void finalize() {
			c = this;
		}
    }
}

Rik says:

May 13, 2012 at 6:14 am

Please dont take vacation. Publish more puzzles. They are awesome

Reply

Java Puzzle 6: Chicken or the Egg – Solution

18 comments to “Java Puzzle 6: Chicken or the Egg – Solution”

Leave a comment

Menu

Recent Posts

Archives

Search