RE: eve/did=.talktalktalk... - haskell is just as good

RE: http://ozgurakgun.blogspot.com/2010/04/evedidtalktalktalk.html

If you implement a simple algorithm usings haskell's list comprehensions, the performance turns out to be just as good. Of course the tools mentioned in the previous post are a) general purpose tools, b) would be far better in harder problems.

Anyway, the interesting part of the haskell code is the following:

evedidtalk =
    [
        [e,v,d,i,t,a,l,k] |
        e <- [1..9],
        v <- [0..9] \\ [e],
        d <- [1..9] \\ [e,v],
        i <- [0..9] \\ [e,v,d],
        t <- [0..9] \\ [e,v,d,i],
        a <- [0..9] \\ [e,v,d,i,t],
        l <- [0..9] \\ [e,v,d,i,t,a],
        k <- [0..9] \\ [e,v,d,i,t,a,l],
        digitsToInt [e,v,e] * 9999 ==
        digitsToInt [d,i,d] * digitsToInt [t,a,l,k]
    ]

Here, evedidtalk is a list of digits, that satisfy the only constraint we have. The key to performance is limiting the number of alternatives generated using the \\ (list difference) operator.
A poor-in-performance alternative would be generating all possibilities and then checking for the second constraint we had, the alldiff.

Compiled with -O2 using ghc, this finds the two possible solutions in under a second (yet, slightly slower than tailor+minion).

eve/did=.talktalktalk...

I've stumbled across this problem recently: http://www.jimloy.com/puzz/evedid.htm

It is very much like the SEND + MORE = MONEY problem, but I thought it would be more interesting (=harder to solve). Nope, not at all.

OK, the problem is the following:

Find the digits E,V,D,I,T,A,L,K such that this equation holds: EVE/DID=.TALKTALKTALK...
EVE and DID are 2 numbers with 3 digits each, and .TALKTALKTALK... is a floating point number.

After exploiting the following property, the problem gets simpler:

0.TALKTALKTALK... = TALK/9999 (try it with a 4 digit number, if you want to see it in action: http://lmgtfy.com/?q=1234/9999)

Thus, the equation turns into EVE/DID = TALK/9999 and then to EVE*9999 = DID*TALK.

Now it is easy to write this as a constraint model. If we choose to model in Essence Prime, use Tailor[1] to generate a Minion[2] input file from it, and then use Minion to actually solve the problem, it is solved almost instantaneously. Thanks to these two great tools!

The model I used is the following:

ESSENCE' 1.0
    find E : int(1..9)
    find V : int(0..9)
    find D : int(1..9)
    find I : int(0..9)
    find T : int(0..9)
    find A : int(0..9)
    find L : int(0..9)
    find K : int(0..9)
such that
    (E*100 + V*10 + E*1) * 9999 = (D*100 + I*10 + D*1) * (T*1000 + A*100 + L*10 + K*1),   
    alldiff([E,V,D,I,T,A,L,K])

If you have tailor and minion installed, just run the following commands to solve the problem.

java -jar tailor.jar -aux-info -out evedidtalk.minion evedidtalk.eprime

minion evedidtalk.minion -findallsols

It only takes less than 1 sec (both commands together) to find all two possible solutions.

[1] http://www.cs.st-andrews.ac.uk/~andrea/tailor
[2] http://sourceforge.net/projects/minion