[Haskell-cafe] Re: Function to detect duplicates
Rafael Gustavo da Cunha Pereira Pinto
RafaelGCPP.Linux at gmail.com
Thu Feb 25 18:57:48 EST 2010
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
More information about the Haskell-Cafe
mailing list