Reputation: 2436
What the program should do is take steps and a number and than output you how many unique sequences there are with exactly x steps
to create number
.
Does someone know how I can save some memory - as I should make this work for pretty huge numbers within a 4 second limit.
def IsaacRule(steps, number):
if number in IsaacRule.numbers:
return 0
else:
IsaacRule.numbers.add(number)
if steps == 0:
return 1
counter = 0
if ((number - 1) / 3) % 2 == 1:
counter += IsaacRule(steps-1, (number - 1) / 3)
if (number * 2) % 2 == 0:
counter += IsaacRule(steps-1, number*2)
return counter
IsaacRule.numbers = set()
print(IsaacRule(6, 2))
If someone knows a version with memoization I would be thankful, right now it works, but there is still room for improvement.
Upvotes: 3
Views: 745
Reputation: 2497
Baseline: IsaacRule(50, 2)
takes 6.96s
This made the code take longer, and gave a different final result
(number * 2) % 2 == 0
to True
IsaacRule(50, 2)
takes 0.679s. Thanks Pm2Ring for this one.
((number - 1) / 3) % 2 == 1
to number % 6 == 4
and use floor division where possible:IsaacRule(50, 2)
takes 0.499s
Truth table:
| n | n-1 | (n-1)/3 | (n-1)/3 % 2 | ((n-1)/3)%2 == 1 |
|---|-----|---------|-------------|------------------|
| 1 | 0 | 0.00 | 0.00 | FALSE |
| 2 | 1 | 0.33 | 0.33 | FALSE |
| 3 | 2 | 0.67 | 0.67 | FALSE |
| 4 | 3 | 1.00 | 1.00 | TRUE |
| 5 | 4 | 1.33 | 1.33 | FALSE |
| 6 | 5 | 1.67 | 1.67 | FALSE |
| 7 | 6 | 2.00 | 0.00 | FALSE |
Code:
def IsaacRule(steps, number):
if number in IsaacRule.numbers:
return 0
else:
IsaacRule.numbers.add(number)
if steps == 0:
return 1
counter = 0
if number % 6 == 4:
counter += IsaacRule(steps-1, (number - 1) // 3)
counter += IsaacRule(steps-1, number*2)
return counter
IsaacRule(50, 2)
takes 0.381s
This lets us take advantage of any optimizations made for sets. Basically I do a breadth first search here.
IsaacRule(50, 2)
takes 0.256s
We just need to add a check that number != 1
to break the only known cycle. This gives a speed up, but you need to add a special case if you start from 1. Thanks Paul for suggesting this!
START = 2
STEPS = 50
# Special case since we broke the cycle
if START == 1:
START = 2
STEPS -= 1
current_candidates = {START} # set of states that can be reached in `step` steps
for step in range(STEPS):
# Get all states that can be reached from current_candidates
next_candidates = set(number * 2 for number in current_candidates if number != 1) | set((number - 1) // 3 for number in current_candidates if number % 6 == 4)
# Next step of BFS
current_candidates = next_candidates
print(len(next_candidates))
Upvotes: 1