| Am Freitag 26 Februar 2010 00:57:48 schrieb Rafael Gustavo da Cunha Pereira | Pinto: | |> 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 Since Ishaaq Chandy just posted about how to generalize nested list comprehensions, I thought this was an interesting way to approach this. First a couple of simple helper functions:
val = foldl (\x y -> x*10+y) 0 divides d n = n `mod` d == 0
So you could solve it using a set of list comprehensions:
solutions = [[x1,x2,x3,x4,x5,x6,x7,x8,x9,x10] | x1 <- [0..9] , x2 <- [0..9], divides 2 $ val [x1,x2] , x3 <- [0..9], divides 3 $ val [x1,x2,x3] , x4 <- [0..9], divides 4 $ val [x1,x2,x3,x4] , x5 <- [0..9], divides 5 $ val [x1,x2,x3,x4,x5] , x6 <- [0..9], divides 6 $ val [x1,x2,x3,x4,x5,x6] , x7 <- [0..9], divides 7 $ val [x1,x2,x3,x4,x5,x6,x7] , x8 <- [0..9], divides 8 $ val [x1,x2,x3,x4,x5,x6,x7,x8] , x9 <- [0..9], divides 9 $ val [x1,x2,x3,x4,x5,x6,x7,x8,x9] , x10 <- [0] , length (nub [x1,x2,x3,x4,x5,x6,x7,x8,x9,x10]) == 10 ]
This is a nicely declarative way to do it, and a pretty clear way to formulate the original problem statement. But it's a bit tedious with all the repetitions, so you would rather recurse to make it more general. Since list comprehensions are just a different way to work in the list monad (where | becomes 'guard'), I managed to come up with this:
solve :: [Int] -> [[Int]] solve prefix = do let l = length prefix if l == 10 then return prefix else do x <- [0..9] let r = prefix++[x] guard (divides (l+1) (val r) && nub r == r) solve r
-k (PS: I'm happy to hear any comments regarding style or other issues) -- If I haven't seen further, it is by standing in the footprints of giants