Advertisement
Guest User

Untitled

a guest
Jun 27th, 2016
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.56 KB | None | 0 0
  1. mem = dict() #global dictionary for memoization
  2.  
  3. def expressible(m,digits,k):
  4. if (m,digits,k) in mem:
  5. return mem[(m,digits,k)]
  6. elif m == 0 and k == 0:
  7. mem[(m,digits,k)] = True
  8. return True
  9. elif len(digits) == 0 or k > len(digits):
  10. mem[(m,digits,k)] = False
  11. return False
  12. else:
  13. for d in set(digits):
  14. i = int(d)
  15. remaining = digits.replace(d,'',1)
  16. if expressible(m + i,remaining, k-1) or expressible(m - i,remaining, k-1):
  17. mem[(m,digits,k)] = True
  18. return True
  19. #if we reach here:
  20. mem[(m,digits,k)] = False
  21. return False
  22.  
  23. def selfContained(a,b):
  24. nums = []
  25. for n in range(a,b+1):
  26. digits = ''.join(sorted(str(n)))
  27. contained = True #until a counter-example found
  28. for d in set(digits):
  29. i = int(d)
  30. remaining = digits.replace(d,'',1)
  31. if not expressible(i,remaining,2):
  32. contained = False
  33. break
  34. if not contained: break
  35. #if we reach here and contained is still true, no counterxamples, so:
  36. if contained: nums.append(n)
  37. mem.clear()
  38. return nums
  39.  
  40. >>> selfContained(1,360)
  41. [101, 110, 112, 121, 123, 132, 134, 143, 145, 154, 156, 165, 167, 176, 178, 187, 189, 198, 202, 211, 213, 220, 224, 231, 235, 242, 246, 253, 257, 264, 268, 275, 279, 286, 297, 303, 312, 314, 321, 325, 330, 336, 341, 347, 352, 358]
  42.  
  43. nums = selfContained(0,1000000)
  44.  
  45. 999909, 999918, 999927, 999936, 999945, 999954, 999963, 999972, 999981, 999990
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement