Fibonacci Rabbits Dying After Arbitrary # of Months

Question

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 =]

Answer 1

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))

Answer 2

Using recursion.

public static int fibRec(int months, int dieAfter) {
    if(months <= 0) return 0;
    if(months == 1) return 1;
    if(months <= dieAfter)
        return fibRec(months-1, dieAfter) + fibRec(months-2, dieAfter);
    else if (months == dieAfter+1)
        return fibRec(months-1, dieAfter) + fibRec(months-2, dieAfter) - 1;
    else
        return fibRec(months-1, dieAfter) + fibRec(months-2, dieAfter) 
                 - fibRec(months-(dieAfter+1), dieAfter);
}

Answer 3

There are 2 cases for the recurrence relationship here. Considering n is the number of months the sequence is running for, and m is the number of months a pair is going to live for:

1) If the index in the sequence (zero-based) is less than m:
Normal Fibonacci (Current term = previous term + the one before it).

2) If the index is greater than or equal to m:
Current term = sum of (m - 1) previous terms (ignoring the one immediately before).

Here's an example with a sequence named A and m = 5:
A5 = A0 + A1 + A2 + A3 (4 terms, i.e. m - 1, ignoring the one immediately before)
.
If m = 3 then:
A3 = A0 + A1 (only 2 terms, m - 1)

.

The code below (in Python) has an offset by 2 because of the initial [1, 1] at the beginning of the sequence.

def mortal_rabbits(n, m):
    sequence = [1, 1]

    for i in range(n - 2):
        new_num = 0
        if i + 2 < m:
            #Normal fibonacci - No deaths yet
            new_num = sequence[i] + sequence[i + 1]
        else:
            #Different reoccurence relation - Accounting for death
            for j in range(m - 1):
                new_num += sequence[i - j]

        sequence.append(new_num)

    return sequence