{"id":1832,"date":"2015-04-24T20:24:32","date_gmt":"2015-04-24T10:24:32","guid":{"rendered":"http:\/\/www.somethinkodd.com\/oddthinking\/?p=1832"},"modified":"2015-04-24T20:24:32","modified_gmt":"2015-04-24T10:24:32","slug":"haskell-versus-python-at-solving-alphametics","status":"publish","type":"post","link":"https:\/\/www.somethinkodd.com\/oddthinking\/2015\/04\/24\/haskell-versus-python-at-solving-alphametics\/","title":{"rendered":"Haskell versus Python at solving Alphametics"},"content":{"rendered":"

Eight years ago, I posted a description<\/a> of an Alphametics Helper<\/a>. 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<\/a> that later proved to be very versatile.<\/p>\n

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

This is in response to an article by Mark Dominus in the Universe of Discourse blog<\/a>.<\/p>\n

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:<\/p>\n

<\/p>\n

\r\nimport Control.Monad (guard)\r\n\r\ndigits = [0..9]\r\n\r\nto_number = foldl (\\a -> \\b -> a*10 + b) 0\r\nremove rs ls = foldl (\\a -> \\b -> remove' a b) ls rs\r\n  where remove' ls x = filter (\/= x) ls\r\n\r\n--     S E N D\r\n--   + M O R E\r\n--   ---------\r\n--   M O N E Y\r\n    solutions = do\r\n      s < - remove [0] digits\r\n      e <- remove [s] digits\r\n      n <- remove [s,e] digits\r\n      d <- remove [s,e,n] digits\r\n      let send = to_number [s,e,n,d]\r\n      m <- remove [0,s,e,n,d] digits\r\n      o <- remove [s,e,n,d,m] digits\r\n      r <- remove [s,e,n,d,m,o] digits\r\n      let more = to_number [m,o,r,e]\r\n      y <- remove [s,e,n,d,m,o,r] digits\r\n      let money = to_number [m,o,n,e,y]\r\n      guard $ send + more == money\r\n      return (send, more, money)\r\n<\/pre>\n
<\/code><\/p><\/blockquote>\n
I emphasize that this code is copyright Mark Dominus, not me. I recommend reading his article to understand how it works.<\/p>\n
Mark concludes his article:<\/p>\n
\nIt 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) = @_; \u00e2\u20ac\u00a6 } instead of \\s -> \u00e2\u20ac\u00a6) the result was completely unreadable and therefore unusable. However, I suspect it would be even worse<\/em> in Python because of semantic limitations of that language. I would be interested to hear about this if anyone tries it.\n<\/p><\/blockquote>\n
This post is my response to that claim. I hope to show that there is a line-for-line equivalent<\/em> piece of Python code that is not hampered by the semantic limitations of the language, and is of a similar aesthetic.<\/p>\n
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.)<\/p>\n
Here we go. I have tried to stick as close as possible to the Haskell implementation:<\/p>\n
<\/p>\n
\r\ndigits = set(range(10))\r\n\r\ndef to_number(list_of_digits):\r\n    return reduce(\r\n        lambda x, y: 10*x+y, list_of_digits)\r\n\r\ndef remove(banned_list, source_set):\r\n    return source_set - set(banned_list)\r\n\r\ndef solution():\r\n    for s in remove([0], digits):\r\n        for e in remove([s], digits):\r\n            for n in remove([s, e], digits):\r\n                for d in remove([s, e, n], digits):\r\n                    send = to_number([s, e, n, d])\r\n                    for m in remove([0, s, e, n, d], digits):\r\n                        for o in remove([s, e, n, d, m], digits):\r\n                            for r in remove([s, e, n, d, m, o], digits):\r\n                                more = to_number([m, o, r, e])\r\n                                for y in remove([s, e, n, d, m, o, r], digits):\r\n                                    money = to_number([m, o, n, e, y])\r\n                                    if send + more == money:\r\n                                        return (send, more, money)\r\n\r\nprint solution()\r\n<\/pre>\n
<\/code><\/p><\/blockquote>\n
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.<\/p>\n
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. <\/p>\n
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”.<\/p>\n
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.<\/p>\n","protected":false},"excerpt":{"rendered":"
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. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_s2mail":"yes","footnotes":""},"categories":[33,34],"tags":[],"class_list":["post-1832","post","type-post","status-publish","format-standard","hentry","category-puzzle-solving","category-software-development"],"_links":{"self":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/1832","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/comments?post=1832"}],"version-history":[{"count":9,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/1832\/revisions"}],"predecessor-version":[{"id":1841,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/1832\/revisions\/1841"}],"wp:attachment":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/media?parent=1832"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/categories?post=1832"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/tags?post=1832"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}