Thanks Jan-Willem for providing a Haskell program that comes closer to
capturing the same spirit as the algorithm I used to implement the
Cryptarithm solver in C++. There are still differences between the two
approaches: C++'s next_permutation permutes the array in place and provides
an iterative as opposed to recursive solution, which would not really be an
appropriate way to implement the solution in Haskell, but you're certainly
getting closer to a true oranges to oranges comparison. So I tried your
program out in HUGS, and it worked just fine without any modifications.
But...
Although I don't have any precise way to time the program, it appeared to me
that it actually took quite a bit longer than my algorithm that uses list
difference. I don't know why. I'm speculating here, but maybe since your
algorithm scans the permutations in a different order than mine, the correct
solution just comes up much later in the process, even though your overall
approach should be faster. It certainly seems like it _should_ be faster,
since you've eliminated the time-consuming list difference function, but
that's not what I'm seeing.
I also agree with your comments that there should be some sort of permute
function built into Haskell's libraries. The C++ STL implementation of
next_permutation is extremely clever and concise, and I probably would not
have been able to figure it out on my own (at least not without a _lot_ of
thought). I really like it when languages provide me with libraries of
cleverly optimized algorithms and data structures, because I don't want to
have to go look up from my college textbooks the best way to sort/permute a
vector/list/tree/etc. with such-and-such characteristics every time I write
a program.
-----Original Message-----
From: Jan-Willem Maessen <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED] <[EMAIL PROTECTED]>
Date: Friday, September 17, 1999 3:45 PM
Subject: Cryptarithm solver - comparing oranges and oranges
>I couldn't help but notice that the Haskell program to solve the given
>cryptarithm is very different indeed from the C++ or Mercury
>implementations. It selects from a set represented by a list (and
>does repeated list difference using \\) rather than generating and
>testing permutations. Here's a generate-and-test version of the same
>algorithm (which I alas can't run through Hugs at the moment, so
>apologies for any gross errors):
>
>import List
>
>-- All permutations of all elements
>permutations :: [a] -> [[a]]
>permutations [] = [[]]
>permutations (a:as) =
> [ r | p <- permutations as, r <- allins a p]
>
>-- All insertions of a into ps.
>allins :: a -> [a] -> [[a]]
>allins a ps =
> (a:ps):case ps of
> [] -> []
> (p:ps) -> map (p:) (allins a ps)
>
>expand a b c d e f = f + e*10 + d*100 + c*1000 + b*10000 + a*100000
>
>digits = [0,1..9] -- all the digits
>
>answer = head [ [t,h,i,r,y,w,e,l,v,n] |
> [t,h,i,r,y,w,e,l,v,n] <- permutations digits,
> expand t h i r t y + 5 * expand t w e l v e == expand n i n e t y]
>
>
>
>Of course, the big thing to note here is I had to roll my own
>"permutations" function (luckily I happened to have one sitting
>around, but allins is not especially pretty at the cost of being a bit
>more lazy than the obvious definition:
>
>allins a [] = [a]
>allins a ps'@(p:ps) = (a:ps') : map (p:) (allins a ps)
>
>I'm sure there's a better permutations definition, and that a bit of
>thought would turn it up. Which leads to a bigger question---why
>isn't "permutations" or something of the sort in List? It seems
>Mr. Engleberg (and, not coincidentally, students in our multithreading
>class at MIT) would benefit from having such a function in the
>libraries. This is certainly the reason the C++ is so brief.
>
>[My instinct from using Haskell for teaching, by the way, is that most
>uses of (\\), especially in list comprehensions, could be done better
>using some other algorithm! Most frequently, it's turned out to be
>something permutation-like or partitioning-like. But then, I have a
>mental performance model that says "(\\) is n squared", which doesn't
>leap readily to the minds of new haskell users.]
>
>-Jan-Willem Maessen
>
