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

Code naively simulating the behaviour in the task, can be faster with touples I guess

def fibm(n,m):
    seq = [[0,0],[0,1],[1,0],[1,1]]
    
    #(old,new)
    for i in range(4,n+1):
        
        new = seq[i-1][0]#new = previous old
        old = seq[i-1][0] + seq[i-1][1] #old = prev old + prev new
        
        if i>m:
            
            old = old - seq[i-m][1] #new from m ago die off
            
        seq.append([old,new])
    return(seq)       
                   
n,m = 95,16

print(sum(fibm(n,m)[-1]))

Answer 2

Ignoring complications, the equation for the number of rabbit pairs in a generation is

If we use a list, this presents a problem because when n == m, we need the value that is at position -1, which is obviously out of bounds.

def rabbit_pairs(n, m):
    sequence = list()
    for i in range(n):
        if i < 2:
            # Normal Fibonacci initialization
            total = 1
            sequence.append(total)
        elif (i < m) or (m == 0):
            # Normal Fibonacci calculation
            total = sequence[i - 1] + sequence[i - 2]
            sequence.append(total)
        elif i == m:
            # Now we need R(n - (m + 1)), but i - (m + 1) < 0, so we have to
            # provide the missing value
            total = sequence[i - 1] + sequence[i - 2] - 1
            sequence.append(total)
        else:
            # i - (m + 1) >= 0, so we can get the value from the sequence
            total = sequence[i - 1] + sequence[i - 2] - sequence[i - (m + 1)]
            sequence.append(total)
    return total

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

Answer 4

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 5

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