Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// 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)
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment