Posts Tagged ‘send’

Programming Praxis – SEND + MORE = MONEY, Part 1

July 31, 2012

In today’s Programming Praxis exercise, our goal is to provide two different solutions for the well known SEND + MORE = MONEY sum, in which each letter must be replaced by a valid digit to yield a correct sum. Let’s get started, shall we?

A quick import:

import Data.List

I’ll be honest, the only reason I wrote this first solution this way is because the exercise explicitly called for checking all possible solutions using nested loops. It’s so horribly inefficient! Take the test whether all digits are unique for example: normally you’d remove each chosen digit from the list of options for all subsequent ones, but we’re not allowed to do that. I normally also wouldn’t do the multiplications this explicitly, but to avoid overlap with the second solution I left it like this. Unsurprisingly, it takes almost a minute and a half to run.

send1 :: ([Integer], [Integer], [Integer])
send1 = head [([s,e,n,d], [m,o,r,e], [m,o,n,e,y])
             | s <- [1..9], e <- [0..9], n <- [0..9], d <- [0..9]
             , m <- [1..9], o <- [0..9], r <- [0..9], y <- [0..9]
             , length (group $ sort [s,e,n,d,m,o,r,y]) == 8
             , 1000*(s+m) + 100*(e+o) + 10*(n+r) + d+e ==
               10000*m + 1000*o + 100*n + 10*e + y]

This is actually the solution I started with: since all digits need to be unique, you can simply generate the permutations of the numbers 0 through 9, backtracking when s or m are zero or when the numbers don’t add up correctly. By writing a function to do the multiplication and assinging some variables we not only make things more readable, but we also get to use the problem statement directly in the code, which I find conceptually satisfying. I do have the distinct impression that this is what we’re supposed to make in part 2 of this exercise though, since it runs in about a second, which is significantly faster than the two provided solutions.

send2 :: (Integer, Integer, Integer)
send2 = head [ (send, more, money) | (s:e:n:d:m:o:r:y:_) <- permutations [0..9]
             , s /= 0, m /= 0, let fill = foldl ((+) . (* 10)) 0
             , let send = fill [s,e,n,d], let more = fill [m,o,r,e]
             , let money = fill [m,o,n,e,y], send + more == money]

A quick test shows that both algorithms produce the correct solution.

main :: IO ()
main = do print send1
          print send2