Mischief with Christmas block permutations

My wife put up a Christmas decoration which is 4 blocks, each side with a different letter, that is supposed to spell, 'NOEL', 'LOVE', 'HOPE' and 'WISH'. Of course this quickly became a challenge to find more interesting combinations of these letters, but since I'm not great at Scrabble I'll be using a script to help.

First I'll represent each block as a list of letters, and add them to a list of blocks. Extra letters are included for placing the blocks upside down, so 'M' for 'W', 'A' for 'V' and 'd' for 'P'.

  val LETTERS = List(
      List("N", "H", "L", "W", "M"),
      List("O", "I"),
      List("E", "P", "V", "S", "d", "A"),
      List("L", "E", "H"))

To find the combinations of letters is easy enough, find every permutation for ordering of the blocks, and for each ordering take the cartesian product of the block lists.

  def permutations(letters: List[List[String]]): Seq[String] = {
    letters.permutations.flatMap(combine[String](_ + _) _)
    .toSeq.sortWith(_.toLowerCase < _.toLowerCase)
  }
  def combine[A](f: (A, A) => A)(xs:Iterable[Iterable[A]]) =
   xs reduceLeft { (x, y) => for (a <- x.view; b <- y) yield f(a, b) }

It's worth allowing for some incorrect spelling where it would still be readble, like leaving an 'e' off the end of a word or using 'oo' instead of 'u', for this we'll introduce a set of transformations defined as regex.

  val TRANSFORMATIONS = List(
      "(?i)l$" -> "le",
      "(?i)l$" -> "el",
      "(?i)^l" -> "el",
      "(?i)oo" -> "u",
      "(?i)i" -> "y")

  def withAlternates(s: String): List[String] = {
    val word = s.toLowerCase()
    val words = for ((x, y) <- TRANSFORMATIONS if word.matches(x)) yield (word.replaceAll(x, y))
    word +: words
  }

Now we have all combinations, but it's too many to look at by hand. We'll use a dictionary word list (the aspell one) to filter.

  def readDictionary(location: String): Set[String] = {
    Source.fromFile(location).getLines.map(a => a.toLowerCase()).toSet
  }

  def inDictionary(dictionary: Set[String]): String => Boolean = {
    dictionary.contains(_)
  }

And the main method to pull it all together

  def main(args: Array[String]) = args match {
    case Array(path) => {
      val dictionary = readDictionary(path)
      print(permutations(LETTERS).filter(withAlternates(_).exists(inDictionary(dictionary))))
    }
    case _ => {
      System.out.println("requires wordlist argument")
      System.exit(1)
    }
  }
  
  def print(it: Iterable[String]) {
    for (x <- it) System.out.println(x);
  }

There is still a lot of output but now that it's manageable we can pick out some of the more interesting words:

• EVIL
• IdLE
• ELMO
• NIPL
• MOES

Immutable domain and lenses in Java 8 part 2 - experimentation

In the previous post lenses were used to make deep updates to the immutable domain of Monkey, Hat, Feather and Colour.

As an experiment lets remove the getters from the previous post and instead replace them with lenses; that way we have getters and setters on immutable objects that support deep nesting.

Something like this:

Monkey newMonkey = monkey.hat.feather.colour.set(new Colour("white"));

To make this work we'll use a class called Property that is basically an object and a Lens, with get/set/mod methods that simply apply lens methods.

The code

This lens class is the same as the last post:

public class Lens<A, B> {

 public Function<A, B> fget;
 public BiFunction<A, B, A> fset;

 public Lens(Function<A, B> fget, BiFunction<A, B, A> fset) {
  this.fget = fget;
  this.fset = fset;
 }

 public B get(A a) {
  return fget.apply(a);
 }

 public A set(A a, B b) {
  return fset.apply(a, b);
 }

 public A mod(A a, Function<B, B> f) {
  return set(a, f.apply(get(a)));
 }

 public <C> Lens<C, B> compose(final Lens<C, A> that) {
  return new Lens<C, B>(
    (c) -> get(that.get(c)),
    (c, b) -> that.mod(c, (a) -> set(a, b)));
 }

 public <C> Lens<A, C> andThen(Lens<B, C> that) {
  return that.compose(this);
 }

}

Property is used to bind a lens to an instance of an object:

public class Property<A, B> {

 protected A a;
 protected Lens<A, B> lens;

 public Property(Lens<A, B> lens, A a) {
  this.lens = lens;
  this.a = a;
 }
    
 protected A getA() {
  return a;
 }

 protected Lens<A, B> getLens() {
  return lens;
 }
    
 public B get() {
  return lens.get(a);
 }

 public A set(B b) {
  return lens.set(a, b);
 }

 public A mod(Function<B, B> f) {
  return set(f.apply(get()));
 }

 public <C> Property<A, C> andThen(Lens<B, C> that) {
  return new Property<A, C>(that.compose(this.lens), a);
 }

}

In this version of Monkey.java a MonkeyBuilder is introduced, not entirely necessary in this example but useful for larger classes.

public class Monkey {
 
 public static Lens<Monkey, Hat> Hat = new Lens<>((monkey) -> monkey._hat, (
   monkey, hat) -> MonkeyBuilder.from(monkey).hat(hat).build());

 public static Lens<Monkey, Colour> Colour = new Lens<>((monkey) -> monkey._colour, (
   monkey, colour) -> MonkeyBuilder.from(monkey).colour(colour).build());
 
 public final HatProperty<Monkey> hat = new HatProperty<>(Hat, this);
 public final ColourProperty<Monkey> colour = new ColourProperty<>(Colour, this);

 private final String _name;
 private final Colour _colour;
 private final Hat _hat;

 public Monkey(String name, Colour colour, Hat hat) {
  this._name = name;
  this._colour = colour;
  this._hat = hat;
 }

 @Override
 public String toString() {
  return "Monkey [name=" + _name + ", colour=" + _colour + ", hat="
    + _hat + "]";
 }

 public static class MonkeyBuilder {

  private String name;
  private Colour colour;
  private Hat hat;

  public static MonkeyBuilder from(Monkey monkey) {
   return new MonkeyBuilder().name(monkey._name)
     .colour(monkey._colour).hat(monkey._hat);
  }

  public MonkeyBuilder name(String name) {
   this.name = name;
   return this;
  }

  public MonkeyBuilder colour(Colour colour) {
   this.colour = colour;
   return this;
  }

  public MonkeyBuilder hat(Hat hat) {
   this.hat = hat;
   return this;
  }

  public Monkey build() {
   return new Monkey(name, colour, hat);
  }

 }

}

The HatProperty class defined here is used to provide quick access to properties in Hat, this is used in Monkey.java. The same pattern is used in each class.

public class Hat {

 public static Lens<Hat, Feather> Feather = new Lens<>(
   (hat) -> hat._feather,
   (hat, feather) -> new Hat(hat._colour, feather));

 public static Lens<Hat, Colour> Colour = new Lens<>((hat) -> hat._colour,
   (hat, colour) -> new Hat(colour, hat._feather));
 
 public final FeatherProperty<Hat> feather = new FeatherProperty<>(Feather, this);
 public final ColourProperty<Hat> colour = new ColourProperty<>(Colour, this);
  
 private final Colour _colour;
 private final Feather _feather;
 
 public Hat(Colour colour, Feather feather) {
  this._colour = colour;
  this._feather = feather;
 }

 @Override
 public String toString() {
  return "Hat [colour=" + _colour + ", feather=" + _feather + "]";
 }
 
 public static class HatProperty<T> extends Property<T, Hat> {
  
  public HatProperty(Lens<T, Hat> lens, T a) {
   super(lens, a);
  }

  public FeatherProperty<T> feather = new FeatherProperty<T>(getLens().andThen(Hat.Feather), getA());

  public Property<T, Colour> colour = this.andThen(Hat.Colour);

 };

}

public class Feather {
 
 public static Lens<Feather, Colour> Colour = new Lens<>(
   (feather) -> feather._colour,
   (feather, colour) -> new Feather(colour));
 
 public final ColourProperty<Feather> colour = new ColourProperty<Feather>(Colour, this);

 private final Colour _colour;

 public Feather(Colour colour) {
  this._colour = colour;
 }

 @Override
 public String toString() {
  return "Feather [colour=" + _colour + "]";
 }
 
 public static class FeatherProperty<T> extends Property<T, Feather> {
  
  public FeatherProperty(Lens<T, Feather> lens, T a) {
   super(lens, a);
  }

  public Property<T, Colour> colour = this.andThen(Feather.Colour);
  
 };
 
}

public class Colour {
 
 public static Lens<Colour, String> Name = new Lens<>(
   (colour) -> colour._name,
   (colour, name) -> new Colour(name));
 
 public final Property<Colour, String> name = new Property<Colour, String>(Name, this);

 private final String _name;

 public Colour(String name) {
  this._name = name;
 }

 @Override
 public String toString() {
  return "Colour [colour=" + _name + "]";
 }
 
 public static class ColourProperty<T> extends Property<T, Colour> {

  public ColourProperty(Lens<T, Colour> lens, T a) {
   super(lens, a);
  }
  
  public Property<T, String> name = this.andThen(Name);
  
 }

}

Example of how this all works:

Monkey monkey = new Monkey("Bob", new Colour("brown"), new Hat(new Colour("yellow"), new Feather(new Colour("blue"))));
System.out.println(monkey);
System.out.println(Monkey.Hat.andThen(Hat.Feather).andThen(Feather.Colour).get(monkey));
monkey = monkey.hat.feather.colour.set(new Colour("white"));
System.out.println(monkey);
monkey = monkey.hat.colour.set(new Colour("red"));
System.out.println(monkey);

The output:

Monkey [name=Bob, colour=Colour [colour=brown], hat=Hat [colour=Colour [colour=yellow], feather=Feather [colour=Colour [colour=blue]]]]
Colour [colour=blue]
Monkey [name=Bob, colour=Colour [colour=brown], hat=Hat [colour=Colour [colour=yellow], feather=Feather [colour=Colour [colour=white]]]]
Monkey [name=Bob, colour=Colour [colour=brown], hat=Hat [colour=Colour [colour=red], feather=Feather [colour=Colour [colour=white]]]]

Immutable domain and lenses in Java 8

The domain used in this post consists of a Monkey, Hat, Feather and Colour. It will be entirely immutable and use lenses to make changes (that is copies with changes) of the data.

The difficulty with an immutable domain is that to change the colour of the feather in the monkey's hat, we need to create a new instance of Monkey, Hat and Feather; this is where lenses come in. A lense is basically a getter/setter that can be used for deep updates of immutable data.

For this example the following lenses are defined, the full classes are given further down.

Monkey:

 public static Lens<Monkey, Hat> Hat = new Lens<>(
   (monkey) -> monkey.hat,
   (monkey, hat) -> new Monkey(monkey.name, hat));

Hat:

 public static Lens<Hat, Feather> Feather = new Lens<>(
   (hat) -> hat.feather,
   (hat, feather) -> new Hat(hat.colour, feather));

Feather:

 public static Lens<Feather, Colour> Colour = new Lens<>(
   (feather) -> feather.colour,
   (feather, colour) -> new Feather(colour));

These lenses can be used to update the colour of the feather in the monkey's hat like this:

Monkey newMonkey = Monkey.Hat.andThen(Hat.Feather).andThen(Feather.Colour).set(monkey, new Colour("white"));

Now for all the code

This lens definition is a modified version of https://github.com/remeniuk/java-lenses for Java 8.

public class Lens<A, B> {

 public Function<A, B> fget;
 public BiFunction<A, B, A> fset;

 public Lens(Function<A, B> fget, BiFunction<A, B, A> fset) {
  this.fget = fget;
  this.fset = fset;
 }

 public B get(A a) {
  return fget.apply(a);
 }

 public A set(A a, B b) {
  return fset.apply(a, b);
 }

 public A mod(A a, Function<B, B> f) {
  return set(a, f.apply(get(a)));
 }

 public <C> Lens<C, B> compose(final Lens<C, A> that) {
  return new Lens<C, B>(
    (c) -> get(that.get(c)),
    (c, b) -> that.mod(c, (a) -> set(a, b)));
 }

 public <C> Lens<A, C> andThen(Lens<B, C> that) {
  return that.compose(this);
 }

}

These are the classes that make up the domain model.

public class Monkey {
 
 public static Lens<Monkey, Hat> Hat = new Lens<>(
   (monkey) -> monkey.hat,
   (monkey, hat) -> new Monkey(monkey.name, hat));

 private final String name;
 private final Hat hat;

 public Monkey(String name, Hat hat) {
  this.name = name;
  this.hat = hat;
 }

 public String getName() {
  return name;
 }

 public Hat getHat() {
  return hat;
 }

 @Override
 public String toString() {
  return "Monkey [name=" + name + ", hat="
    + hat + "]";
 }

}

public class Hat {

 public static Lens<Hat, Feather> Feather = new Lens<>(
   (hat) -> hat.feather,
   (hat, feather) -> new Hat(hat.colour, feather));

 public static Lens<Hat, Colour> Colour = new Lens<>((hat) -> hat.colour,
   (hat, colour) -> new Hat(colour, hat.feather));
  
 private final Colour colour;
 private final Feather feather;
 
 public Hat(Colour colour, Feather feather) {
  this.colour = colour;
  this.feather = feather;
 }

 public Colour getColour() {
  return colour;
 }

 public Feather getFeather() {
  return feather;
 }

 @Override
 public String toString() {
  return "Hat [colour=" + colour + ", feather=" + feather + "]";
 }

}

public class Feather {
 
 public static Lens<Feather, Colour> Colour = new Lens<>(
   (feather) -> feather.colour,
   (feather, colour) -> new Feather(colour));

 private final Colour colour;

 public Feather(Colour colour) {
  this.colour = colour;
 }

 public Colour getColour() {
  return colour;
 };
 
 @Override
 public String toString() {
  return "Feather [colour=" + colour + "]";
 }
 
}

public class Colour {
 
 public static Lens<Colour, String> Name = new Lens<>(
   (colour) -> colour.name,
   (colour, name) -> new Colour(name));
 
 private final String name;

 public Colour(String name) {
  this.name = name;
 }

 public String getName() {
  return name;
 }

 @Override
 public String toString() {
  return "Colour [colour=" + name + "]";
 }

}

Now for a slightly more complete example of usage:

Monkey monkey = new Monkey("Ham", new Hat(new Colour("yellow"), new Feather(new Colour("blue"))));
System.out.println(monkey);
System.out.println(Monkey.Hat.andThen(Hat.Colour).get(monkey));
monkey = Monkey.Hat.andThen(Hat.Feather).andThen(Feather.Colour).set(monkey, new Colour("white"));
System.out.println(monkey);

Output:

Monkey [name=Ham, hat=Hat [colour=Colour [colour=yellow], feather=Feather [colour=Colour [colour=blue]]]]
Colour [colour=yellow]
Monkey [name=Ham, hat=Hat [colour=Colour [colour=yellow], feather=Feather [colour=Colour [colour=white]]]]