Talk:Weird numbers: Difference between revisions
→A faster and less ambitious algorithm ?: Added a Haskell version of an anySum (for testing)
(→A faster and less ambitious algorithm ?: Added a Haskell version of an anySum (for testing)) |
|||
| (7 intermediate revisions by the same user not shown) | |||
Line 18:
If hasSum considers large divisors first, it can soon exclude all those those too big to sum to a smaller target.
: PS I think we may be able to see and test the operation of '''hasSum''' more clearly if we enrich its type from Bool to [Int] (with a return value of the empty list for '''False''', and the integers of the first sum found for '''True'''). Let's call this richer-typed variant '''anySum''', and sketch it in Python 3.
::<lang python># anySum :: Int -> [Int] -> [Int]
def anySum(n, xs):
'''First subset of xs found to sum to n.
(Probably more efficient where xs is sorted in
descending order of magnitude)'''
def go(n, xs):
if xs:
# Assumes Python 3 for list deconstruction
# Otherwise: h, t = xs[0], xs[1:]
h, *t = xs
if n < h:
return go(n, t)
else:
if n == h:
return [h]
else:
ys = go(n - h, t)
return [h] + ys if ys else go(n, t)
else:
return []
return go(n, xs)
# Search for sum through descending numbers (more efficient)
print(anySum(196, range(100, 0, -1)))
# -> [100, 96]
# Search for sum through ascending numbers (less efficient)
print(anySum(196, range(1, 101)))
# -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 25]
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>
| |||