[Haskell-cafe] Re: Function to detect duplicates

[Rafael Gustavo da Cunha Pereira Pinto]

Just to clarify the issue, I will propose the puzzle:

There is a single 10 digit number that:

1) uses all ten digits [0..9], with no repetitions
2) the number formed by the first digit (right to left, most significant) is
divisible by one
3) the number formed by the first 2 digits (again right to left) is
divisible by two
4) the number formed by the first 3 digits is divisible by three
 and so on, until:
11) the number formed by the first 10 digits (all!) is by 10

Actually this can be solved by a little logic, but I wanted to give a try on
brute force search using haskell.

I am not looking very large lists, but I was expecting a handful of small
lists.

My algorithm follow these steps:

1) start with an list of empty list ([[]]), call it ds
2) I cons each member of [0..9] to ds
3) filter using:
      a) noneRepeated
      b) (listToNum d) `mod` l == 0, where l is the length of each sublist d
(not computed, it is an accumulator that is incremented each time I cons)
4) repeat steps 2-3 until l==10


So, I represent each possible number as a reversed list of its digits... It
ran REALLY fast (sub-second).

So, bragging about Haskell with a Smalltalk-lover friend, by showing him how
clean was the code and how easy was to profile, I figured out that I spent
99% on noneRepeated.

After changing to the merge sort version, I have 30% on noneRepeated, 30% on
listToNum and 30% on putStrLn. Pretty good!

Besides, I could brag a little more about Hakell to that specific friend!!
;-)


Best regards to you all!!

Rafael


PS: Here is the original search code, with the bad noneRepeated and still
using length



import Data.List

digits=[0..9]

noneRepeated::[Integer]->Bool
noneRepeated=null.(filter (>1)).(map length).group.sort

listToNum::[Integer]->Integer
listToNum = (foldl (\a x->10*a+x) 0).reverse

check::[Integer]->Bool
check ds= and [noneRepeated ds, (listToNum ds) `mod` l==0]
    where l=fromIntegral $ length ds

nextlevel::[[Integer]]->[[Integer]]
nextlevel dss=filter (check) [d:ds | ds<-dss,d<-digits]

main=do
    dss<-runlevel 10 0 [[]]
    print $ map (listToNum) dss

runlevel 0 b dds=return dds
runlevel a b dds=do
    let dds'=nextlevel dds
    putStrLn $ "Level "++(show (b+1))++": "++(show $ length dds')++"
matches"
    print $ map (listToNum) dds'
    runlevel (a-1) (b+1) dds'
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100225/db2e72c8/attachment-0001.html