So, I've seen a few solutions for this problem or similar problems, but I really want to know why mine isn't working. It is much easier to read than a lot of solutions I've found, so I'd love to make it work!
Starting with 1 pair of rabbits, which will begin to reproduce after 2 months. Run for n months, where rabbits die after they have lived for m months. Input of '6 3' should return 4, but it returns 3.
#run for n months, rabbits die after m months.
n, m = input("Enter months to run, and how many months rabbits live, separated by a space ").split()
n, m = int(n), int(m)
generations = [1, 1, 2] #Seed the sequence with the 1 pair, then in their reproductive month.
def fib(i, j):
count = 3 #we start at the 3rd generation.
while (count < i):
if (count < j):
generations.append(generations[count-2] + generations[count-1]) #recurrence relation before rabbits start dying
else: #is just the fib seq (Fn = Fn-2 + Fn-1)
generations.append((generations[count-2] + generations[count-1]) - generations[(count-j)]) #Our recurrence relation when rabbits die every month
count += 1 #is (Fn = Fn-2 + Fn-1 - Fn-j)
return (generations[count-1])
print (fib(n, m))
print ("Here's how the total population looks by generation: \n" + str(generations))
Thanks =]
This is copied from the answer in SpaceCadets question to help rbump it out of the "unanswered" list of questions.
The two keys here were drawing out the tree to a large number, AND making sure to include a base case check for the first and second generations of deaths (It's -1 in both cases, and then it's something that depends on input).
So 3 potential cases. The regular fib sequence when we don't need to account for deaths, the first and second generations of deaths to initialize our final sequence with the recurrence relation Fn-2 + Fn-1 - Fn-(monthsAlive+1)
I'm certain there's a way to merge 1 or 2 of these checks and make the algorithm more efficient, but as of now it solved a large test case (90, 17) instantly and correctly. So I'm happy.
Lesson learned: Use the entire white-board.
#run for n months, rabbits die after m months.
n, m = input("Enter months to run, and how many months rabbits live, separated by a space ").split()
n, m = int(n), int(m)
generations = [1, 1] #Seed the sequence with the 1 pair, then in their reproductive month.
def fib(i, j):
count = 2
while (count < i):
if (count < j):
generations.append(generations[-2] + generations[-1]) #recurrence relation before rabbits start dying (simply fib seq Fn = Fn-2 + Fn-1)
elif (count == j or count == j+1):
print ("in base cases for newborns (1st+2nd gen. deaths)") #Base cases for subtracting rabbit deaths (1 death in first 2 death gens)
generations.append((generations[-2] + generations[-1]) - 1)#Fn = Fn-2 + Fn-1 - 1
else:
generations.append((generations[-2] + generations[-1]) - (generations[-(j+1)])) #Our recurrence relation here is Fn-2 + Fn-1 - Fn-(j+1)
count += 1
return (generations[-1])
print (fib(n, m))
print ("Here's how the total population looks by generation: \n" + str(generations))