Mark Engelberg <[EMAIL PROTECTED]>
wrote on 17 Sep 1999
> I decided to test out Haskell by writing a program to solve a cryptarithm
> [..]
> The algorithm is pretty straightforward - you just need to consider all
> possible mappings of letters to digits, and test the equation ...
> [..]
----------------------
> import List
> expand a b c d e f = f + e*10 + d*100 + c*1000 + b*10000 + a*100000
> xs = [0,1..9] -- all the digits
> answer = head [ [t,h,i,r,y,w,e,l,v,n] | t<-xs, e<-xs\\[t], h<-xs\\[t,e],
> i<-xs\\[t,e,h],
> [..]
There followed the C++ program to compare with the Haskell one, that
calls the next_permutation
library function.
Then, people wrote much on possible Haskell program modification and
measurements.
First who declared the in-correctness of such comparison was
Herbert Graeber <[EMAIL PROTECTED]>.
He wrote
> [..]
> Second, the C++ algorithm presented uses a permutation generator from the
> C++ standard library. The times can only be compared, if both programs - the
> C++ version and the Haskell version - use the same algorithm. It is easy to
> speed up the Haskell version simply by using a permutation generator, that
> starts with the solution. In general even this may be not sufficient,
> because imperative and pure functional lazy evaluation of the same algorithm
> may give very different results.
>
> A fair comparison should include the best algorithm suitable for each
> language and much more different inputs for the programs, including very
> large ones.
This is the very point.
If this next_permutation, - who's algorithm is not known to us, -
starts occasionally right with the needed permutation, then the whole
program `answer' may run in C++, say, 0.00000000001 sec.
Another example: replacing in the initial program xs = [0..9]
with reverse [0..9] may change the time many times - for the same
reason.
If, studying the algorithm for next_permutation we discover that
there exists a good Haskell analog, - which also generates the
permutation in the same order, - then with this analog, we could
really compare the performance.
Otherwise, more subtle reasoning and list of examples are required.
Still, i also tried to program this thing: the program is enclosed.
Again, changing [0..9] to reverse [0..9]
speeds up the program 3 times, but this is only the specific of the
given equation and the used permutation generator.
`++' takes here 10 steps to evaluate. But it does not effect the
performace any essentially - this can be tested easily.
Compilation: ghc-4.04 -c -O2 -O2-for-C ...
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
-------------------------------------------------------------------
main = putStr $ shows answer "\n"
expand a b c d e f = f + e*10 + d*100 + c*1000 + b*10000 + a*100000
:: Int
answer = find (\ [t,h,i,r,y,w,e,l,v,n] ->
expand t h i r t y + 5 * expand t w e l v e ==
expand n i n e t y
) $ permutations $ [0..9]
permutations :: [Int] -> [[Int]]
permutations [] = [[]]
permutations (j:js) = addOne $ permutations js
where
addOne [] = []
addOne (ks:pms) = (ao ks)++(addOne pms)
ao [] = [[j]]
ao (k:ks) = (j:k:ks):(map (k:) $ ao ks)
