Programming Puzzle 1 Solutions: new naked mole-rats

We've seen an elegant recursive answer. Can we now work out a quicker way?

Rather than diving in and starting to code the pattern, perhpas we can see a pattern in the sequence of totals we are really trying to work out.

Our original series of numbers of animals added each year (the Fibonacci series) is

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The corresponding running totals are:

1, 2, 4, 7, 12, 20, 33, ...

Look carefully at these two sequences and you may see a direct link... See if you can spot it!

Each total is actually one less than a number in the original sequence. For example, the number 7 in the totals list is one less than 8 in the original list. The number 12 is one less than 13 in the original list. In fact every number is just one less than the number two later in the Fibonacci series!

We can write this as a new algorithm for working out the totals that only calculates the number of new animals for a single year, rather than over and over again.

Total (year) = nakedmolerats(year+2) - 1

Turning this in to a program we get:

def totalNakedMoleRats2 (year):
       """An efficient way to compute the TOTAL number of naked mole-rats in the colony in the given year"""
        return  nakedMoleRat(year+2) - 1

Where did that come from???

Does that pattern really hold for ever though. We can check more and more numbers, but a better way is to use some logical thinking. We can do a little bit of clever algebra to see why this pattern is there. It says to work out the total we need to know the number of naked mole rats added in year, year+2. Now we know:

nakedmolerats (n) = nakedmolerats (n-1) + nakedmolerats (n-2)

Substituting in year+2, our year of interest in to this we get

nakedmolerats (year+2) = nakedmolerats (year+2-1) + nakedmolerats (year+2-2)

which simplifies to

nakedmolerats (year+2) = nakedmolerats (year+1) + nakedmolerats (year)

Turning this round and subtracting nakedmolerats (year+1) from both sides gives a different way to calculate any number in the series:

nakedmolerats (year) = nakedmolerats (year+2) - nakedmolerats (year+1)

Now to work that out we will need to add all the numbers from that point down. If we use this same equation to work out what each is we get:

nakedmolerats (year)   = nakedmolerats (year+2) - nakedmolerats (year+1)
nakedmolerats (year-1) = nakedmolerats (year+1) - nakedmolerats (year)
nakedmolerats (year-2) = nakedmolerats (year)   - nakedmolerats (year-1)
       .                       .                       .
       .                       .                       .
       .                       .                       .
nakedmolerats (-1)     = nakedmolerats (1)      - nakedmolerats (0)

If we now add all the equations, one side gives us the total we are after. Most of the other side's terms actually just cancel each other out as on each line we add a term and then on the next subtract it...so virtually everything miraculously disappears leaving:

Total (year)      =    nakedmolerats (year+2)    -    nakedmolerats (0) 

Now we know what nakedmolerats (0) is. It is just 1 so this simplifies to

Total (year)  = nakedmolerats (year+2) - 1 

and that was exactly the pattern we had spotted!

Some pattern matching, a bit of logical thinking (using algebra) leading to some algorithmic thinking based on a suitable recursive decomposition has led us to a more efficient program. Computational thinking makes a difference!

So now we can work out the totals efficiently, but our way of working out the original sequence still repeats the same work over and over.

Perhaps there is a better, more efficient way to do that too...If you haven't already see if you can work out a way.

Find out how...