sendmoremoney.scala

// This brute force solution can be sped up if permutations took an extra argument
//     to limit the number of elements in a permutation.

// problem: the last element is the sum of all preceding elements
// base: a little bit of extra abstraction - not necessary, but trivial to add anyway
type Solution = Seq[Int]
def solveSendMoreMoney(problem: Vector[String] = Vector("send", "more", "money"),
                       base: Int = 10): Stream[(Solution, Map[Char, Int])] = {
  val inputChars = problem.flatten.toSet
  val digits = 0 until base
  
  val allMappings: Iterator[Map[Char,Int]] = digits.permutations.map(inputChars.zip(_).toMap)
  
  // Seq(2, 3, 5) => 235
  def sumDigits(d: Seq[Int]): Int = {
    // = Seq(200, 30, 5)
    val weightedDigits = for {
      pos <- 0 until d.length
      val digit = d(d.length - 1 - pos)
    } yield digit * Math.pow(base, pos).toInt
    weightedDigits.sum
  }
  
  def checkSolution(s: Solution): Boolean = {
    val summands :+ result = s
    summands.sum == result
  }
  
  val allSolutionMappings = allMappings.filter((mapping) => {
    val solutionDigits: Seq[Seq[Int]] = problem.map(_.map(mapping(_)))
    val solution: Solution = solutionDigits map sumDigits
    checkSolution(solution)
  }).toStream.distinct

  for {
    mapping <- allSolutionMappings
    val solutionDigits = problem.map(_.map(mapping(_)))
    val solution = solutionDigits map sumDigits
  } yield (solution, mapping)
}

// usage with default arguments
val solutionMappings = solveSendMoreMoney().toVector
solutionMappings.foreach((s) => {
 println("Solution: " + s._1.toString + ", mapping: " + s._2.toString)
})

/*

Solution: Vector(7316, 823, 8139), mapping: Map(e -> 3, s -> 7, n -> 1, y -> 9, m -> 0, r -> 2, o -> 8, d -> 6)
Solution: Vector(8324, 913, 9237), mapping: Map(e -> 3, s -> 8, n -> 2, y -> 7, m -> 0, r -> 1, o -> 9, d -> 4)
Solution: Vector(6419, 724, 7143), mapping: Map(e -> 4, s -> 6, n -> 1, y -> 3, m -> 0, r -> 2, o -> 7, d -> 9)
Solution: Vector(6415, 734, 7149), mapping: Map(e -> 4, s -> 6, n -> 1, y -> 9, m -> 0, r -> 3, o -> 7, d -> 5)
Solution: Vector(7429, 814, 8243), mapping: Map(e -> 4, s -> 7, n -> 2, y -> 3, m -> 0, r -> 1, o -> 8, d -> 9)
Solution: Vector(8432, 914, 9346), mapping: Map(e -> 4, s -> 8, n -> 3, y -> 6, m -> 0, r -> 1, o -> 9, d -> 2)
Solution: Vector(6524, 735, 7259), mapping: Map(e -> 5, s -> 6, n -> 2, y -> 9, m -> 0, r -> 3, o -> 7, d -> 4)
Solution: Vector(7539, 815, 8354), mapping: Map(e -> 5, s -> 7, n -> 3, y -> 4, m -> 0, r -> 1, o -> 8, d -> 9)
Solution: Vector(7531, 825, 8356), mapping: Map(e -> 5, s -> 7, n -> 3, y -> 6, m -> 0, r -> 2, o -> 8, d -> 1)
Solution: Vector(7534, 825, 8359), mapping: Map(e -> 5, s -> 7, n -> 3, y -> 9, m -> 0, r -> 2, o -> 8, d -> 4)
Solution: Vector(8542, 915, 9457), mapping: Map(e -> 5, s -> 8, n -> 4, y -> 7, m -> 0, r -> 1, o -> 9, d -> 2)
Solution: Vector(9567, 1085, 10652), mapping: Map(e -> 5, s -> 9, n -> 6, y -> 2, m -> 1, r -> 8, o -> 0, d -> 7)
Solution: Vector(7649, 816, 8465), mapping: Map(e -> 6, s -> 7, n -> 4, y -> 5, m -> 0, r -> 1, o -> 8, d -> 9)
Solution: Vector(7643, 826, 8469), mapping: Map(e -> 6, s -> 7, n -> 4, y -> 9, m -> 0, r -> 2, o -> 8, d -> 3)
Solution: Vector(3719, 457, 4176), mapping: Map(e -> 7, s -> 3, n -> 1, y -> 6, m -> 0, r -> 5, o -> 4, d -> 9)
Solution: Vector(3712, 467, 4179), mapping: Map(e -> 7, s -> 3, n -> 1, y -> 9, m -> 0, r -> 6, o -> 4, d -> 2)
Solution: Vector(5731, 647, 6378), mapping: Map(e -> 7, s -> 5, n -> 3, y -> 8, m -> 0, r -> 4, o -> 6, d -> 1)
Solution: Vector(5732, 647, 6379), mapping: Map(e -> 7, s -> 5, n -> 3, y -> 9, m -> 0, r -> 4, o -> 6, d -> 2)
Solution: Vector(2817, 368, 3185), mapping: Map(e -> 8, s -> 2, n -> 1, y -> 5, m -> 0, r -> 6, o -> 3, d -> 7)
Solution: Vector(2819, 368, 3187), mapping: Map(e -> 8, s -> 2, n -> 1, y -> 7, m -> 0, r -> 6, o -> 3, d -> 9)
Solution: Vector(3829, 458, 4287), mapping: Map(e -> 8, s -> 3, n -> 2, y -> 7, m -> 0, r -> 5, o -> 4, d -> 9)
Solution: Vector(3821, 468, 4289), mapping: Map(e -> 8, s -> 3, n -> 2, y -> 9, m -> 0, r -> 6, o -> 4, d -> 1)
Solution: Vector(5849, 638, 6487), mapping: Map(e -> 8, s -> 5, n -> 4, y -> 7, m -> 0, r -> 3, o -> 6, d -> 9)
Solution: Vector(6853, 728, 7581), mapping: Map(e -> 8, s -> 6, n -> 5, y -> 1, m -> 0, r -> 2, o -> 7, d -> 3)
Solution: Vector(6851, 738, 7589), mapping: Map(e -> 8, s -> 6, n -> 5, y -> 9, m -> 0, r -> 3, o -> 7, d -> 1)

*/