Java Puzzle 6: Chicken or the Egg - Solution

Mar 26, 2012

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

Matt Nathan wrote on 2012-03-22 15:00

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 wrote on 2012-03-22 22:16

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 wrote on 2012-03-22 22:53

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 wrote on 2012-03-22 23:20

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 wrote on 2012-03-23 00:03

“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.

Heinz Kabutz wrote on 2012-03-23 08:02

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 wrote on 2012-03-23 10:35

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 wrote on 2012-03-23 17:46

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 wrote on 2012-03-23 19:01

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 wrote on 2012-03-23 19:53

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 wrote on 2012-03-23 20:25

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 wrote on 2012-03-23 20:43

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 wrote on 2012-03-23 23:32

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

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 wrote on 2012-03-26 10:47

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 wrote on 2012-03-26 10:47

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 wrote on 2012-03-26 18:19

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 wrote on 2012-05-13 08:14

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