Re: Cryptarithm solver - Haskell vs. C++

```Mark Engelberg  <mark.engelberg@bigfoot.com>

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

>            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  <h.graeber@dokom.net>.
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
mechvel@botik.ru

-------------------------------------------------------------------
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

ao []     = [[j]]
ao (k:ks) = (j:k:ks):(map (k:) \$ ao ks)

```