Занятная задачка с хабра иллюстрирующая монады списка.

Send More Money.md

Паззл Send More Money

Занятная задачка с хабра иллюстрирующая монады списка.

Оригинал http://habrahabr.ru/company/infopulse/blog/260809

Ну и вот вам задачка, которая может попасться на собеседовании. Она не совсем тривиальна, возможно несколько подходов к решению и лучший из них не сразу очевиден — как-раз то, над чем стоит подумать. Вам предлагается следующий пазл:

  s e n d
+ m o r e
---------
m o n e y

Каждая буква соответствует цифре от 0 до 9. Нужно написать программу, которая подберёт такие соответствия, чтобы написанная операция сложения была верной.

Решение на прологе от одного из хабровчан:

to_int(D5,D4,D3,D2,D1, R):- R is D5*10000+D4*1000+D3*100+D2*10+D1.
solve(_, S:E:N:D:M:O:R:Y:r):- !,
    S=\=0, M=\=0, to_int(0,S,E,N,D, Send), to_int(0,M,O,R,E, More), to_int(M,O,N,E,Y, Money),
    Money is Send+More, write(Send), write(', '), write(More), write(', '), write(Money).
solve(L, R):- member(N, L), delete(L, N, L1), solve(L1, N:R).
solve:- numlist(0, 9, L), solve(L, r).

Мое решение на лиспе:

(defn as-num [& digits] (apply + (map * (reverse digits) (iterate (partial * 10) 1))))
(some (fn [[s e n d m o r y]]
        (and (pos? s) (pos? m) 
          (let [send (as-num s e n d) more (as-num m o r e) money (as-num m o n e y)]
            (when (= (+ send more) money) (prn [send more money])))))
      (clojure.math.combinatorics/permutations [0 1 2 3 4 5 6 7 8 9]))

Решение на хаскелле от Justin Le :

http://blog.jle.im/entry/unique-sample-drawing-searches-with-list-and-statet

select :: [a] -> [(a, [a])]
select []     = []
select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]

StateT select :: StateT [a] [] a

import Control.Monad             (guard, mfilter)
import Control.Monad.Trans.State
import Data.List                 (foldl')

asNumber :: [Int] -> Int
asNumber = foldl' (\t o -> t*10 + o) 0

main :: IO ()
main = print . flip evalStateT [0..9] $ do
    s <- StateT select
    e <- StateT select
    n <- StateT select
    d <- StateT select
    m <- StateT select
    o <- StateT select
    r <- StateT select
    y <- StateT select
    guard $ s /= 0 && m /= 0
    let send  = asNumber [s,e,n,d]
        more  = asNumber [m,o,r,e]
        money = asNumber [m,o,n,e,y]
    guard $ send + more == money
    return (send, more, money)

Решение на C++ и Scala от BartoszMilewski:

https://github.com/BartoszMilewski/MoreMoney