1

Input

sum_possible(2017, [4, 2, 10]) # -> False

Usage of any which causes the solution to hang / take a long time

def sum_possible(amount, numbers, cache = None):
  if cache is None:
    cache = {}
  if amount in cache:
    return cache[amount]
  if amount == 0:
    return True
  if amount < 0:
    return False
  cache[amount] = any([sum_possible(amount - number, numbers, cache) for number in numbers])
  return cache[amount]

Usage of a for loop which solves the solution in a reasonable time

def sum_possible(amount, numbers, cache = None):
  if cache is None:
    cache = {}
  if amount in cache:
    return cache[amount]
  if amount == 0:
    return True
  if amount < 0:
    return False
  
  for number in numbers:
    if sum_possible(amount - number, numbers, cache):
      cache[amount] = True
      return True
  
  cache[amount] = False
  return False

I thought that any would short-circuit? Effectively return Trueing early if it encountered a True?

HeyZoos
  • 57
  • 1
  • 5
  • 1
    https://stackoverflow.com/a/53600865/6273251 TL;DR list comprehension fully evaluates before `any()` does. It's the list comprehension that's taking a long time I think. – Random Davis Oct 29 '21 at 19:04
  • Just remove the square brackets `[ ]`, which look innocuous but effectively prevent `any( )` from short-circuiting. – Stef Oct 29 '21 at 21:25

1 Answers1

2

any() would short-circuit, but you're building a list to pass to any first.

cache[amount] = any([sum_possible(amount - number, numbers, cache) for number in numbers])

The list comprehension is evaluated first - and it's eager:

[sum_possible(amount - number, numbers, cache) for number in numbers]

Replace it with a generator expression - that should work (lazy eval):

cache[amount] = any(sum_possible(amount - number, numbers, cache) for number in numbers)
rdas
  • 20,604
  • 6
  • 33
  • 46
  • Thanks, that was a thing I was definitely missing. Interestingly however, using the generator expression still causes `RecursionError: maximum recursion depth exceeded` for me, whereas using the `for` loop doesn't. Is there anything more that could possibly be amiss? – HeyZoos Oct 29 '21 at 19:10
  • The early exit is missing from the `any` version - that may be the issue. – rdas Oct 29 '21 at 19:12
  • I think that might be worth a separate question, I'm going to mark this as resolved since the first issue was definitely the eager list comprehension evaluation as you pointed out. – HeyZoos Oct 29 '21 at 19:14
  • Can you add a link to the new question in the comments here, if you do post a new question? – Stef Oct 29 '21 at 21:40
  • 1
    https://stackoverflow.com/q/69803975/5196424 – HeyZoos Nov 01 '21 at 23:56