Java Puzzle 7: Cookies - Solution

Aug 12, 2012

Here's the solution to the cookies puzzle! As a reminder, the Count class:

package count;

import monster.CookieMonster;

public class Count {
    public static void main(String[] args) {
        String noCookie = CookieMonster.eat("cookie");
        if (noCookie.isEmpty() &amp;&amp; CookieMonster.eat(noCookie).length() < noCookie.length()) {
            // The goal is to reach this line
            System.out.println("Minus one cookie!");
        }
    }
}

At first sight, it looks as if CookieMonster.eat needs to return a String with a negative length. That sounds like anti-matter. Looking closer, there are two separate requirements: the first time eat is called, it needs to return an empty String; and the second time, it needs to return something with a negative length().

The trick is, a generic method's return type can be different depending on the type context in which it is used. To demonstrate that, let's look at an example from java.util.Collections: <T> List<T> emptyList(). In that method signature, <T> says there is type variable T on the method, and List<T> is the return type. You can use this as List<String> strings = Collections.emptyList();. That works because type inference ensures that the T in the return type (List<T>) adjusts to the type of the variable it is assigned to (List<String>). When there is no context (when it is not assigned to anything) then the inferred type will be Object (the implicit upper bound of T). In Collections.emptyList().size() for example emptyList() returns a List<Object>.

Back to our CookieMonster, we can make eat return anything the context expects it to return like this: static <C> C eat(String cookie). That's like a magic cookie. If you think 'chocolate' and put it in our mouth, it's a chocolate cookie. In Count where it is assigned to a String, it turns into a String cookie (I don't want to know what that tastes like). That's a start, but in CookieMonster.eat(noCookie).length(), there is no context, so it turns into Object which doesn't have a length() method, and that doesn't compile.

We fix that by putting a bound on C. For both of the calls to eat to compile, the bound needs to be a supertype of String, and have a length() method. There is one such type: CharSequence. So we replace the type variable <C> by <C extends CharSequence>. In the first call eat("cookie") must return an empty String, and in the second call eat("") must return a CharSequence with negative length:

package monster;

public class CookieMonster {
    public static <C extends CharSequence> C eat(String cookie) {
        return (C) (cookie.length() > 0 ? "" : new CharSequence() {
            public int length() {
                return -1;
            }

            public char charAt(int index) {
                throw new UnsupportedOperationException();
            }

            public CharSequence subSequence(int start, int end) {
                throw new UnsupportedOperationException();
            }
        });
    }
}

Congrats to the 9 Java monsters who found the solution; see the comments below.

9 comments

David Shay wrote on 2012-08-08 11:16

My Cookie Monster:

public class CookieMonster {
    public static  T eat(String cookie) {
        if (cookie.isEmpty()) {
            return (T) new CharSequence() {
                @Override
                public CharSequence subSequence(int start, int end) {
                    return null;
                }

                @Override
                public int length() {
                    return -1;
                }

                @Override
                public char charAt(int index) {
                    return 0;
                }
            };
        }
        return (T) "";
    }
}

Jerome wrote on 2012-08-08 14:27

That was tough, thanks for the challenge!

public class CookieMonster {
    public static <O extends CharSequence> O eat(String cookie) {
        if(cookie.length() != 0) {
            return (O) "";
        } else {
            return (O)new CharSequence() {
                public CharSequence subSequence(int start, int end) {
                    return null;
                }
                public int length() {
                    return -1;
                }
                public char charAt(int index) {
                    return 0;
                }
            };
        }
    }
}

Liel Man wrote on 2012-08-08 18:29

package monster;

public class CookieMonster {
    public static  T eat(String cookie) {
        if (cookie.length() > 0) {
            return (T)cookie.subSequence(0, 0);
        }

        return (T)new MyString();
    }

    private static class MyString implements CharSequence {
        public int length() {
            return -1;
        }

        @Override
        public char charAt(int index) {
            return 0;
        }

        @Override
        public CharSequence subSequence(int start, int end) {
            return null;
        }
    }
}

mihi wrote on 2012-08-08 20:43

As I am pretty sure you cannot get a genuine java.lang.String with negative length, let’s use some unchecked generics magic to have the method return a String in the first (to avoid ClassCastExceptions) and another CharSequence with negative length in the second case.

public class CookieMonster {
    public static <T extends CharSequence> T eat(String cookie) {
        if (cookie.length() > 0) return (T) "";
        else return (T) new javax.swing.text.Segment(new char[0], 0, -1);
    }
}

Using a StringBuilder instead of the Segment would also work (use two threads to get the count negative), or just implement your own implementation of CharSequence. But I think this is the shortest solution :-)

Matt Nathan wrote on 2012-08-09 17:40

package monster;

public class CookieMonster {

  public static class HasLength implements CharSequence {
    public int length() {
      return -1;
    }

    @Override
    public char charAt(int index) {
      return 0;
    }

    @Override
    public CharSequence subSequence(int start, int end) {
      return null;
    }
  }

  public static <T extends CharSequence> T eat(String cookie) {
    return (T) (cookie.length() == 0 ? new HasLength() : "");
  }
}

Jens Voß wrote on 2012-08-10 11:45

Nice one, but not too tricky. The key term here is “type inference”. We make the monster return a String for each “real” cookie and only a (“negative”) CharSequence when given no cookie - that one can be customized to have negative length. Since the “noCookie” variable is declared to be String, the compiler will do the casting.

package monster;

public class CookieMonster

  @SuppressWarnings("unchecked")
  public static <C extends CharSequence> C eat(String cookie) {
    if (!"".equals(cookie)) {
      return (C) "";
    }
    return (C) new CharSequence() {
      @Override
      public CharSequence subSequence(int start, int end) {
        return null;
      }
      @Override
      public int length() {
        return -1;
      }
      @Override
      public char charAt(int index) {
        return 0;
      }
    };
  }

}

Arend v. Reinersdorff wrote on 2012-08-10 22:37

Both casts give unchecked casts warnings:

package monster;

import javax.swing.text.Segment;

public class CookieMonster extends CookieMonsterParent {
    public static <T extends CharSequence> T eat(String cookie) {
        if (cookie.isEmpty()) {
            return (T) new Segment() {
                @Override
                public int length() {
                    return -1;
                }
            };
        }
        return (T) "";
    }
}

Stefan s106mo wrote on 2012-08-11 13:13

package monster;

public class CookieMonster {
    static int count = 0;


    @SuppressWarnings("unchecked")
    public static <T extends CharSequence> T eat(String cookie) {
        if (count == 0) {
            count++;
            return (T) cookie.substring(0, cookie.length() - 6);
        } else {
            return (T) new CharSequence() {

                @Override
                public CharSequence subSequence(int start, int end) {
                    return null;
                }

                @Override
                public int length() {
                    return -1;
                }

                @Override
                public char charAt(int index) {
                    return 0;
                }
            };

        }
    }

}

Bas de Bakker wrote on 2012-08-11 22:31

Another great puzzle. Thanks, keep them coming.

package monster;

public class CookieMonster {
  public static <T extends CharSequence> T eat(String cookie) {
    return (T) (cookie.isEmpty() ? new CharSequence() {
      public int length() {
        return -1;
      }
      public char charAt(int index) {
        return 0;
      }
      public CharSequence subSequence(int start, int end) {
        return null;
      }
    } : "");
  }
}