OddThinking

Eight years ago, I posted a description of an Alphametics Helper. I wasn’t much interested in the answers (as was evidenced by the fact it gave wrong answers, and I only just noticed) so much as the architecture – I wanted to implement a new Puzzle Solving Framework that later proved to be very versatile.

Today, I revisit Alphametics solvers, but not using the Framework – instead doing a relatively straight forward brute-force search for the answers.

This is in response to an article by Mark Dominus in the Universe of Discourse blog.

Mark demonstrates that the Alphametics search for SEND + MORE = MONEY (a classic example, that I also used in 2008) can be implemented fairly simple in Haskell:

import Control.Monad (guard)

digits = [0..9]

to_number = foldl (\a -> \b -> a*10 + b) 0
remove rs ls = foldl (\a -> \b -> remove' a b) ls rs
  where remove' ls x = filter (/= x) ls

--     S E N D
--   + M O R E
--   ---------
--   M O N E Y
    solutions = do
      s < - remove [0] digits
      e <- remove [s] digits
      n <- remove [s,e] digits
      d <- remove [s,e,n] digits
      let send = to_number [s,e,n,d]
      m <- remove [0,s,e,n,d] digits
      o <- remove [s,e,n,d,m] digits
      r <- remove [s,e,n,d,m,o] digits
      let more = to_number [m,o,r,e]
      y <- remove [s,e,n,d,m,o,r] digits
      let money = to_number [m,o,n,e,y]
      guard $ send + more == money
      return (send, more, money)

I emphasize that this code is copyright Mark Dominus, not me. I recommend reading his article to understand how it works.

Mark concludes his article:

It would be an interesting and pleasant exercise to try to implement the same underlying machinery in another language. I tried this in Perl once, and I found that although it worked perfectly well, between the lack of the do-notation’s syntactic sugar and Perl’s clumsy notation for lambda functions (sub { my ($s) = @_; … } instead of \s -> …) the result was completely unreadable and therefore unusable. However, I suspect it would be even worse in Python because of semantic limitations of that language. I would be interested to hear about this if anyone tries it.

This post is my response to that claim. I hope to show that there is a line-for-line equivalent piece of Python code that is not hampered by the semantic limitations of the language, and is of a similar aesthetic.

I am somewhat hampered in that I haven’t programmed in Haskell, so there is a risk I have missed some element of the aesthetic (although I have experience in Miranda, so functional languages and type-inference are familiar to me.)

Here we go. I have tried to stick as close as possible to the Haskell implementation:

digits = set(range(10))

def to_number(list_of_digits):
    return reduce(
        lambda x, y: 10*x+y, list_of_digits)

def remove(banned_list, source_set):
    return source_set - set(banned_list)

def solution():
    for s in remove([0], digits):
        for e in remove([s], digits):
            for n in remove([s, e], digits):
                for d in remove([s, e, n], digits):
                    send = to_number([s, e, n, d])
                    for m in remove([0, s, e, n, d], digits):
                        for o in remove([s, e, n, d, m], digits):
                            for r in remove([s, e, n, d, m, o], digits):
                                more = to_number([m, o, r, e])
                                for y in remove([s, e, n, d, m, o, r], digits):
                                    money = to_number([m, o, n, e, y])
                                    if send + more == money:
                                        return (send, more, money)

print solution()

Unlike the Haskell version, this version requires indenting for each nested loop which may displease some people. I think I am used to it, because I welcome it. It required some extra line-breaks for the definitions, which meant it couldn’t be exactly line-by-line. There are probably more characters in the Python version, but that has always been a poor metric to optimise for.

I concern myself with types in a couple of places – the remove function deals with lists and sets and it is necessary to convert between them.

Because of my choice of iterating over sets rather than lists, this does not guarantee to search in increasing order for the digits – the order it searches is arbitrary, but that better satisfies the functional programmer in me. I am saying “go and check every possible value” rather than the imperative “here is how you look, one by one, through the digits”.

Despite this limitations, I believe this Python code to be of equivalent complexity and aesthetic to the original in Haskell. If you like one, I think you should like the other.