Software Development

Conway’s Game of Life and the Flyweight Pattern

flyweightConway’s Game of Life is fascinating, both from a functional and from a technical perspective.

This may explain why it’s often used for code retreats. Code retreats are a fun way to learn.

It’s amazing how working with new pairs gives you new insights virtually every time.

 
At the last code retreat that I attended, one of my pairs suggested we use the Flyweight pattern for cells:

A flyweight is a shared object that can be used in multiple contexts simultaneously. The flyweight acts as an independent object in each context — it’s indistinguishable from an instance of the objects that is not shared.

When the Design Patterns book (which contains the above quote) came out, I remember having many aha moments. It was so cool to see all these patterns that I had used before and finally have a name for them so I could discuss them with my peers more efficiently!

I did not have an aha moment when reading about flyweight, however. The example in the book, sharing character objects in a text editor, seemed a bit far fetched at the time. This example is not unlike the cells in a Game of Life grid, however, so I happily went along with my pair’s idea to explore the pattern’s applicability in this context.

After the code retreat was over, I gave this pattern some more thought. (This is usually where the code retreat really starts paying off.)

We actually use a potential flyweight all the time: booleans. A boolean is a class with only two instances, and those instances could easily be shared. In Java they are not: new Boolean(true) != new Boolean(true). However, the Boolean class does provide two constants, TRUE and FALSE, for the instances that you could use for sharing.

That got me thinking about using Enums for flyweights. Most of the time, I use enums for grouping related but mutually exclusive constants, like days of the week. However, Enums in Java can define methods:

public enum Cell {

    ALIVE(true), DEAD(false);

    private final boolean alive;

    private Cell(boolean alive) {
      this.alive = alive;
    }

    public boolean isAlive() {
      return alive;
    }

    public Cell evolve(int numLiveNeighbors) {
      boolean aliveInNextGeneration = alive
          ? 2 <= numLiveNeighbors && numLiveNeighbors <= 3
          : numLiveNeighbors == 3;
      return aliveInNextGeneration ? ALIVE : DEAD;
    }

  }

One of the fun parts of code retreats is that in some sessions, you will have constraints on the way you work. Such constraints force you to be more creative and think beyond the techniques you would normally use.

One constraint that is interesting in this context is to not use any conditionals, like if or switch statements or ternary operators. The idea behind this constraint is to force you to replace conditionals with polymorphism, making your program more object oriented.

The only way that I see to keep the current Cell enum and not use conditionals, is to introduce a map:

public enum Cell {

    ALIVE(true), DEAD(false);

    private final boolean alive;
    private static final Map<Boolean, Map<Integer, Cell>> 
        NEXT = new HashMap<>();

    static {
      Map<Integer, Cell> dead = new HashMap<>();
      dead.put(0, DEAD);
      dead.put(1, DEAD);
      dead.put(2, DEAD);
      dead.put(3, ALIVE);
      dead.put(4, DEAD);
      dead.put(5, DEAD);
      dead.put(6, DEAD);
      dead.put(7, DEAD);
      dead.put(8, DEAD);
      dead.put(9, DEAD);
      NEXT.put(false, dead);
      Map<Integer, Cell> alive = new HashMap<>();
      alive.put(0, DEAD);
      alive.put(1, DEAD);
      alive.put(2, ALIVE);
      alive.put(3, ALIVE);
      alive.put(4, DEAD);
      alive.put(5, DEAD);
      alive.put(6, DEAD);
      alive.put(7, DEAD);
      alive.put(8, DEAD);
      alive.put(9, DEAD);
      NEXT.put(true, alive);
    }

    private Cell(boolean alive) {
      this.alive = alive;
    }

    public boolean isAlive() {
      return alive;
    }

    public Cell evolve(int numLiveNeighbors) {
      return NEXT.get(alive).get(numLiveNeighbors);
    }

  }

This approach works, but is not very elegant and it breaks down when the number of possibilities grows. Clearly, we need a better alternative.

The only way we can get rid of the conditional, is by getting rid of the boolean state of the cell. That means we need to have different classes for the two instances, so that the type implicitly embodies the state. That in turn means we need a factory to hide those classes from the client:

public interface Cell {

    boolean isAlive();
    Cell evolve(int numLiveNeighbors);

  }

  public class CellFactory {

    private static final Map<Boolean, Cell> CELLS 
        = new HashMap<>();

    static {
      CELLS.put(false, new DeadCell());
      CELLS.put(true, new AliveCell());
    }

    public static Cell dead() {
      return cell(false);
    }

    public static Cell alive() {
      return cell(true);
    }

    static Cell cell(boolean alive) {
      return CELLS.get(alive);
    }

  }

  class DeadCell implements Cell {

    @Override
    public boolean isAlive() {
      return false;
    }

    @Override
    public Cell evolve(int numLiveNeighbors) {
      return CellFactory.cell(numLiveNeighbors == 3);
    }

  }

  class AliveCell implements Cell {

    @Override
    public boolean isAlive() {
      return true;
    }

    @Override
    public Cell evolve(int numLiveNeighbors) {
      return CellFactory.cell(numLiveNeighbors == 2 
          || numLiveNeighbors == 3);
    }

  }

Indeed, when you look up the Flyweight pattern, you’ll see that the proposed structure contains a flyweight factory that creates instances of concrete flyweight classes that implement a common flyweight interface.

Thanks to the code retreat and my partner, I now know why.

Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments
Back to top button