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 ?: Updated sample function) |
(→A faster and less ambitious algorithm ?: Added a Haskell version of an anySum (for testing)) |
||
| (3 intermediate revisions by the same user not shown) | |||
Line 20:
[[User:Hout|Hout]] ([[User talk:Hout|talk]]) 11:52, 24 March 2019 (UTC)
: 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:
Line 45:
# Search for sum through descending numbers (more efficient)
print(anySum(7, [1,1,1,1,1,6]))▼
print(anySum(196, range(100, 0, -1)))
# -> [
# Search for sum through ascending numbers (less efficient)
# -> [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>
| |||