cats_problem.py

#!/usr/bin/env python
# -*- coding: latin-1 -*-

"""
cats_problem.py

Olivier Pirson --- http://www.opimedia.be/
July 1st, 2015


Solve this cats problem:
2 chats, une femelle et un mâle tout juste à l'age de procréer !

Une femelle fait 2 portées par an
mais seulement à partir de son premier anniversaire !
Systématiquement elle fait 3 mâles et une femelle !

Un mâle est fertile 5 ans à partir de sa première année, une femelle à vie !

Aucun chat ou chatte ne meure d'accident
ou de maladie et aucun n'est opéré ou stérilisé !
Combien seront-ils au bout de 8 ans ?


Result:
HY: Females     Males     Total
 0:       1 +       1 =       2
 1:       2 +       4 =       6
 2:       3 +       7 =      10
 3:       5 +      13 =      18
 4:       8 +      22 =      30
 5:      13 +      37 =      50
 6:      21 +      61 =      82
 7:      34 +     100 =     134
 8:      55 +     163 =     218
 9:      89 +     265 =     354
10:     144 +     430 =     574
11:     233 +     697 =     930
12:     377 +    1129 =    1506
13:     610 +    1828 =    2438
14:     987 +    2959 =    3946
15:    1597 +    4789 =    6386
16:    2584 +    7750 =   10334
"""


def fibonacci(n):
    """
    Fibonacci number F_n

    https://oeis.org/A000045
    """
    assert isinstance(n, int), type(n)
    assert n >= 0, n

    return fibonacci_pair(n)[1]


def fibonacci_pair(n):
    assert isinstance(n, int), type(n)
    assert n >= 0, n

    if n != 0:
        f_n_2, f_n_1 = fibonacci_pair(n - 1)  # F_{n-2}, F_{n-1}

        return (f_n_1, f_n_1 + f_n_2)
    else:
        return (1, 0)


def nb_female(n):
    """
    Shifted Fibonacci number F_{n+2}
    """
    assert isinstance(n, int), type(n)
    assert n >= 0, n

    return fibonacci(n + 2)


def nb_male(n):
    """
    = 1                          if n = 0
      nb_male(n - 1) + 3 F_{n-2} else
    = 3 F_{n+2} - 2

    https://oeis.org/A111314
    """
    assert isinstance(n, int), type(n)
    assert n >= 0, n

    return fibonacci(n + 2)*3 - 2


def nb_total(n):
    """
    = 4 F_{n+2} - 2
    """
    assert isinstance(n, int), type(n)
    assert n >= 0, n

    return fibonacci(n + 2)*4 - 2


def step(females, males):
    assert isinstance(females, tuple), type(females)
    assert isinstance(males, tuple), type(males)

    # Add half year
    fs = []

    for female in females:
        fs.append(female + 1)

    ms = []

    for male in males:
        if 0 <= male < 5*2:  # <= 5 years
            ms.append(male + 1)
        else:                # become sterile
            ms.append(-1)

    ms.sort(reverse=True)

    # New generation
    for i in range(min(len(fs), len(ms))):
        if fs[i] < 2:  # < 1 year
            break

        assert ms[i] >= 0

        fs.append(0)
        ms.extend([0]*3)

    return (tuple(fs), tuple(ms))


def steps(nb):
    assert isinstance(nb, int), type(nb)
    assert nb >= 0, nb

    print('HY: Females     Males     Total')

    females = (1, )
    males = (0, )

    for i in range(nb*2 + 1):
        if i != 0:
            females, males = step(females, males)

        assert len(females) == nb_female(i), i
        assert len(males) == nb_male(i), i
        assert len(females) + len(males) == nb_total(i), i

        # print(females, males)
        print('{:2}: {:7} + {:7} = {:7}'.format(i,
                                                len(females), len(males),
                                                len(females) + len(males)))


if __name__ == '__main__':
    import sys

    NB_YEAR = (8 if len(sys.argv) < 2
               else max(0, int(sys.argv[1])))

    steps(NB_YEAR)