Programming Puzzle 1 Solutions: new naked mole-rats

Here are program solutions to programming puzzle 1.

The first thing to do is work out the pattern that we have to program. What is the pattern behind the series of numbers we have to code.

In this puzzle the numbers of naked-mole rats start at 1 (the queen) then the first male joins. They have 2 pups in the first year, then 3 the next, 5 the next, 8 the next, and so on. The sequence we need goes

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

The pattern behind this sequence is that each new number is the sum of the previous two numbers. It is actually a well-known pattern called the Fibonacci series, and the numbers themselves are called Fibonacci numbers.

This means if we have a method that can calculate any number in the sequence called nakedmolerats say then we can write its specification as

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

This says that the number of naked mole-rats in year, year (whatever number that is) can be calculated by using the method to work out the number in the previous year (year - 1) and the year before that (year - 2).

We need though to also give a starting point. For our sequence, we know what happened in the two years before year 1 when the first pups were born, At the very start in year -1 (two years before the first pups), there was just the Queen so

nakedmolerats (-1) = 1

We also know what happened in the next year, year 0, (one year before the first pups) a single male joined her.

nakedmolerats (0) = 1

Remember the numbers in our sequence are the numbers of new animals in the colony. Writing this algorithm as a python program we get the following.

def nakedMoleRat(year):
	"""Return the number of naked mole-rats added to a colony in a given year"""
	if year == -1 :
		return 1
	elif year == 0 :
		return 1
	else :
		return (nakedMoleRat(year-1) + nakedMoleRat(year-2))

This is called a recursive algorithm. That just means that it is defined in terms of itself. It says to compute the number of naked mole-rats, you must be able already be able to compute the number of naked mole-rats (though in an earlier year). We have converted the problem in to ones that are identical problems apart from being smaller. It is the smaller in the sense of taking you closer to a trivial case where you just know the answer - here for year -1 and year 0.

We need our program to tell us the total number, in any year not just the new arrivals. Each year the new total is just the number of new naked mole-rats this year added to the total from the previous year. We can an algorithm for this as:

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

Turning this into code we get:

def totalNakedMoleRats (year):
	"""Return the TOTAL number of naked mole-rats in the colony in the given year"""
	if year == -1 :
		return 1
	else :
	    return totalNakedMoleRats(year - 1) + nakedMoleRat (year)

By spotting the pattern and then thinking recursively, we get a really elegant specification of the algorithm and way to code it. However, it is a really slow algorithm as we are working out the whole sequence of naked mole rats numbers for each year over and over again. Perhaps there is a better, more efficient way ...If you haven't already see if you can work out a way to calculate the total really, really quickly (i.e with as few calculations as possible) given a way of working out the number of new animals in each year.

Find out how...