I was led from here to here to here, and got intrigued by the 9-digit problem. Here is the description, copied verbatim from here :
Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:
- The number should be divisible by 9.
- If the rightmost digit is removed, the remaining number should be divisible by 8.
- If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
- And so on, until there’s only one digit (which will necessarily be divisible by 1).
There are solutions in many languages in those webpages, but I wanted to write my own in Haskell, just for kicks. Here it is :
thelist = [1..9]
check [] = False
check xs = (foldl (\x -> \y -> 10*x+y) 0 xs) `mod` (length xs) == 0
onemore [] = [[x] | x <- thelist]
onemore list = [list ++ [l] | l<-thelist,elem l list == False, check (list ++ [l]) == True]
testmore [] = []
testmore (x:xs) = (onemore x) ++ (testmore xs)
result = foldl (.) id (replicate 8 testmore) (onemore [])
check [] = False
check xs = (foldl (\x -> \y -> 10*x+y) 0 xs) `mod` (length xs) == 0
onemore [] = [[x] | x <- thelist]
onemore list = [list ++ [l] | l<-thelist,elem l list == False, check (list ++ [l]) == True]
testmore [] = []
testmore (x:xs) = (onemore x) ++ (testmore xs)
result = foldl (.) id (replicate 8 testmore) (onemore [])
Here is another version in Haskell, just for comparison.
That’s so complicated! Here’s mine.
a `divides` b = (b `mod` a) == 0
step iter (avail, prev) =
let options = [(delete x avail, prev*10 + x) | x concatMap $ step i)
[([1..9], 0)] $
reverse [1..psize]
concatMap is from Data.List and is simply
concatMap f a = concat $ map f a
At each step, generate the list of results for the possible choices. A result consists of the new complete number as well as the digits remaining. Then simply repeat this for the steps 1 through problem size, generating lists of results for every possible starting point and concatenating them.
Haskell being lazy, when you do a head $ solve 9, it should effectively do a linear search, cutting off the search whenever an early condition is not met.
I am a little slow on the uptake, but can you please show the complete working example?