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