Talk:Weird numbers: Difference between revisions
→A faster and less ambitious algorithm ?: Added a Haskell version of an anySum (for testing)
m (→A faster and less ambitious algorithm ?: (Tests to show advantage of search thru descending numbers)) |
(→A faster and less ambitious algorithm ?: Added a Haskell version of an anySum (for testing)) |
||
Line 55:
print(anySum(7, [6, 3]))
# -> []</lang>
or similarly, rewriting '''hasSum''' to '''anySum''' (with comments) in a Haskell idiom:
:<lang haskell>module AnySum where
hasSum :: Int -> [Int] -> Bool
hasSum _ [] = False
hasSum n (x:xs)
| n < x = hasSum n xs
| otherwise = (n == x) || hasSum (n - x) xs || hasSum n xs
-- Or, enriching the return type from Bool to [Int]
-- with [] for False and a populated list (first sum found) for True
anySum :: Int -> [Int] -> [Int]
anySum _ [] = []
anySum n (x:xs)
| n < x = anySum n xs -- x too large for a sum to n
| n == x = [x] -- We have a sum
| otherwise =
let ys = anySum (n - x) xs -- Any sum for (n - x) in the tail ?
in if null ys
then anySum n xs -- Any sum (not involving x) in the tail ?
else x : ys -- x and the rest of the sum that was found.
main :: IO ()
main = do
-- xs ascending - the test is less efficient
print $ anySum 196 [1 .. 100]
-- -> [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,25]
-- xs descending - the test is more efficent
print $ anySum 196 [100,99 ..]
-- -> [100,96]</lang>
| |||