Programming Praxis – SEND + MORE = MONEY, Part 1

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
About these ads

Tags: , , , , , , , , ,

2 Responses to “Programming Praxis – SEND + MORE = MONEY, Part 1”

  1. Lemming Says:

    I have solved the problem using my set-cover package. The compiled program runs in half a second:

    http://code.haskell.org/~thielema/set-cover/example/Alphametics.hs

  2. Lemming Says:

    In send2 you test every assignment twice, because you ignore the last two digits in “(s:e:n:d:m:o:r:y:_) <- permutations [0..9]".

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: