Source code in the scala programming language

/* Note to the rules:
 * 
 * It can further concluded that:
 * 5a: The green house cannot be at the h1 position
 * 5b: The white house cannot be at the h5 position
 * 
 * 16: This rule is redundant.
 */

object Einstein extends App {
  val possibleMembers = for { // pair clues results in 78 members
    nationality <- List("Norwegian", "German", "Dane", "Englishman", "Swede")
    color <- List("Red", "Green", "Yellow", "White", "Blue")
    beverage <- List("Milk", "Coffee", "Tea", "Beer", "Water")
    animal <- List("Dog", "Horse", "Birds", "Cats", "Zebra")
    brand <- List("Blend", "Pall Mall", "Prince", "Blue Master", "Dunhill")
    if (color == "Red") == (nationality == "Englishman") // #2
    if (nationality == "Swede") == (animal == "Dog") // #3
    if (nationality == "Dane") == (beverage == "Tea") // #4
    if (color == "Green") == (beverage == "Coffee") // #6
    if (brand == "Pall Mall") == (animal == "Birds") // #7
    if (brand == "Dunhill") == (color == "Yellow") // #8
    if (brand == "Blue Master") == (beverage == "Beer") // #13
    if (brand == "Prince") == (nationality == "German") // #14
  } yield new House(nationality, color, beverage, animal, brand)
  val members = for { // Neighborhood clues
    h1 <- housesLeftOver().filter(p => (p.nationality == "Norwegian" /* #10 */) && (p.color != "Green") /* #5a */) // 28
    h3 <- housesLeftOver(h1).filter(p => p.beverage == "Milk") // #9 // 24
    h2 <- housesLeftOver(h1, h3).filter(_.color == "Blue") // #15
    if matchMiddleBrandAnimal(h1, h2, h3, "Blend", "Cats") // #11
    if matchCornerBrandAnimal(h1, h2, "Horse", "Dunhill") // #12
    h4 <- housesLeftOver(h1, h2, h3).filter(_.checkAdjacentWhite(h3) /* #5 */)
    h5 <- housesLeftOver(h1, h2, h3, h4)

    //  Redundant tests
    if h2.checkAdjacentWhite(h1)
    if h3.checkAdjacentWhite(h2)
    if matchCornerBrandAnimal(h5, h4, "Horse", "Dunhill")
    if matchMiddleBrandAnimal(h2, h3, h4, "Blend", "Cats")
    if matchMiddleBrandAnimal(h3, h4, h5, "Blend", "Cats")
  } yield Seq(h1, h2, h3, h4, h5)

  def matchMiddleBrandAnimal(home1: House, home2: House, home3: House, brand: String, animal: String) =
    (home1.animal == animal || home2.brand != brand || home3.animal == animal) &&
      (home1.brand == brand || home2.animal != animal || home3.brand == brand)

  def matchCornerBrandAnimal(corner: House, inner: House, animal: String, brand: String) =
    (corner.brand != brand || inner.animal == animal) && (corner.animal == animal || inner.brand != brand)

  def housesLeftOver(pickedHouses: House*): List[House] = {
    possibleMembers.filter(house => pickedHouses.forall(_.totalUnEqual(house)))
  }

  class House(val nationality: String, val color: String, val beverage: String, val animal: String, val brand: String) {
    override def toString = {
      f"$nationality%10s, ${color + ", "}%-8s$beverage,\t$animal,\t$brand."
    }

    def totalUnEqual(home2: House) =
      this.animal != home2.animal &&
        this.beverage != home2.beverage &&
        this.brand != home2.brand &&
        this.color != home2.color &&
        this.nationality != home2.nationality

    //** Checks if the this green house is next to the other white house*/
    def checkAdjacentWhite(home2: House) = (this.color == "Green") == (home2.color == "White") // #5
  }

  { // Main program
    val beest = "Zebra"
    members.flatMap(p => p.filter(p => p.animal == beest)).
      foreach(s => println(s"The ${s.nationality} is the owner of the ${beest.toLowerCase}."))

    println(s"The ${members.size} solution(s) are:")
    members.foreach(solution => solution.zipWithIndex.foreach(h => println(s"House ${h._2 + 1} ${h._1}")))
  }
} // loc 58


import scala.util.Try

object Einstein extends App {

  // The strategy here is to mount a brute-force attack on the solution space, pruning very aggressively.
  // The scala standard `permutations` method is extremely helpful here. It turns out that by pruning
  // quickly and smartly we can solve this very quickly (45ms on my machine) compared to days or weeks
  // required to fully enumerate the solution space.

  // We set up a for comprehension with an enumerator for each of the 5 variables, with if clauses to
  // prune. The hard part is the pruning logic, which is basically just translating the rules to code
  // and the data model. The data model is basically Seq[Seq[String]]

  // Rules are encoded as for comprehension filters. There is a natural cascade of rules from
  // depending on more or less criteria. The rules about smokes are the most complex and depend
  // on the most other factors

  // 4. The green house is just to the left of the white one.
  def colorRules(colors: Seq[String]) = Try(colors(colors.indexOf("White") - 1) == "Green").getOrElse(false)

  // 1. The Englishman lives in the red house.
  // 9. The Norwegian lives in the first house.
  // 14. The Norwegian lives next to the blue house.
  def natRules(colors: Seq[String], nats: Seq[String]) =
    nats.head == "Norwegian" && colors(nats.indexOf("Brit")) == "Red" &&
      (Try(colors(nats.indexOf("Norwegian") - 1) == "Blue").getOrElse(false) ||
        Try(colors(nats.indexOf("Norwegian") + 1) == "Blue").getOrElse(false))

  // 3. The Dane drinks tea.
  // 5. The owner of the green house drinks coffee.
  // 8. The man in the center house drinks milk.
  def drinkRules(colors: Seq[String], nats: Seq[String], drinks: Seq[String]) =
    drinks(nats.indexOf("Dane")) == "Tea" &&
      drinks(colors.indexOf("Green")) == "Coffee" &&
      drinks(2) == "Milk"

  // 2. The Swede keeps dogs.
  def petRules(nats: Seq[String], pets: Seq[String]) = pets(nats.indexOf("Swede")) == "Dogs"

  // 6. The Pall Mall smoker keeps birds.
  // 7. The owner of the yellow house smokes Dunhills.
  // 10. The Blend smoker has a neighbor who keeps cats.
  // 11. The man who smokes Blue Masters drinks bier.
  // 12. The man who keeps horses lives next to the Dunhill smoker.
  // 13. The German smokes Prince.
  // 15. The Blend smoker has a neighbor who drinks water.
  def smokeRules(colors: Seq[String], nats: Seq[String], drinks: Seq[String], pets: Seq[String], smokes: Seq[String]) =
    pets(smokes.indexOf("Pall Mall")) == "Birds" &&
      smokes(colors.indexOf("Yellow")) == "Dunhill" &&
      (Try(pets(smokes.indexOf("Blend") - 1) == "Cats").getOrElse(false) ||
        Try(pets(smokes.indexOf("Blend") + 1) == "Cats").getOrElse(false)) &&
      drinks(smokes.indexOf("BlueMaster")) == "Beer" &&
      (Try(smokes(pets.indexOf("Horses") - 1) == "Dunhill").getOrElse(false) ||
        Try(pets(pets.indexOf("Horses") + 1) == "Dunhill").getOrElse(false)) &&
      smokes(nats.indexOf("German")) == "Prince" &&
      (Try(drinks(smokes.indexOf("Blend") - 1) == "Water").getOrElse(false) ||
        Try(drinks(smokes.indexOf("Blend") + 1) == "Water").getOrElse(false))

  // once the rules are created it, the actual solution is simple: iterate brute force, pruning early.
  val solutions = for {
    colors <- Seq("Red", "Blue", "White", "Green", "Yellow").permutations if colorRules(colors)
    nats <- Seq("Brit", "Swede", "Dane", "Norwegian", "German").permutations if natRules(colors, nats)
    drinks <- Seq("Tea", "Coffee", "Milk", "Beer", "Water").permutations if drinkRules(colors, nats, drinks)
    pets <- Seq("Dogs", "Birds", "Cats", "Horses", "Fish").permutations if petRules(nats, pets)
    smokes <- Seq("BlueMaster", "Blend", "Pall Mall", "Dunhill", "Prince").permutations if smokeRules(colors, nats, drinks, pets, smokes)
  } yield Seq(colors, nats, drinks, pets, smokes)

  // There *should* be just one solution...
  solutions.foreach { solution =>
    // so we can pretty-print, find out the maximum string length of all cells
    val maxLen = solution.flatten.map(_.length).max

    def pretty(str: String): String = str + (" " * (maxLen - str.length + 1))

    // a labels column
    val labels = ("" +: Seq("Color", "Nation", "Drink", "Pet", "Smoke").map(_ + ":")).toIterator

    // print each row including a column header
    ((1 to 5).map(n => s"House $n") +: solution).map(_.map(pretty)).map(x => (pretty(labels.next) +: x).mkString(" ")).foreach(println)

    println(s"\nThe ${solution(1)(solution(3).indexOf("Fish"))} owns the Fish")
  }

}// loc 38