SHARE
TWEET

cats_problem.py

OPiMedia Jul 1st, 2015 (edited) 193 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python
  2. # -*- coding: latin-1 -*-
  3.  
  4. """
  5. cats_problem.py
  6.  
  7. Olivier Pirson --- http://www.opimedia.be/
  8. July 1st, 2015
  9.  
  10.  
  11. Solve this cats problem:
  12. 2 chats, une femelle et un mâle tout juste à l'age de procréer !
  13.  
  14. Une femelle fait 2 portées par an
  15. mais seulement à partir de son premier anniversaire !
  16. Systématiquement elle fait 3 mâles et une femelle !
  17.  
  18. Un mâle est fertile 5 ans à partir de sa première année, une femelle à vie !
  19.  
  20. Aucun chat ou chatte ne meure d'accident
  21. ou de maladie et aucun n'est opéré ou stérilisé !
  22. Combien seront-ils au bout de 8 ans ?
  23.  
  24.  
  25. Result:
  26. HY: Females     Males     Total
  27. 0:       1 +       1 =       2
  28. 1:       2 +       4 =       6
  29. 2:       3 +       7 =      10
  30. 3:       5 +      13 =      18
  31. 4:       8 +      22 =      30
  32. 5:      13 +      37 =      50
  33. 6:      21 +      61 =      82
  34. 7:      34 +     100 =     134
  35. 8:      55 +     163 =     218
  36. 9:      89 +     265 =     354
  37. 10:     144 +     430 =     574
  38. 11:     233 +     697 =     930
  39. 12:     377 +    1129 =    1506
  40. 13:     610 +    1828 =    2438
  41. 14:     987 +    2959 =    3946
  42. 15:    1597 +    4789 =    6386
  43. 16:    2584 +    7750 =   10334
  44. """
  45.  
  46.  
  47. def fibonacci(n):
  48.     """
  49.    Fibonacci number F_n
  50.  
  51.    https://oeis.org/A000045
  52.    """
  53.     assert isinstance(n, int), type(n)
  54.     assert n >= 0, n
  55.  
  56.     return fibonacci_pair(n)[1]
  57.  
  58.  
  59. def fibonacci_pair(n):
  60.     assert isinstance(n, int), type(n)
  61.     assert n >= 0, n
  62.  
  63.     if n != 0:
  64.         f_n_2, f_n_1 = fibonacci_pair(n - 1)  # F_{n-2}, F_{n-1}
  65.  
  66.         return (f_n_1, f_n_1 + f_n_2)
  67.     else:
  68.         return (1, 0)
  69.  
  70.  
  71. def nb_female(n):
  72.     """
  73.    Shifted Fibonacci number F_{n+2}
  74.    """
  75.     assert isinstance(n, int), type(n)
  76.     assert n >= 0, n
  77.  
  78.     return fibonacci(n + 2)
  79.  
  80.  
  81. def nb_male(n):
  82.     """
  83.    = 1                          if n = 0
  84.      nb_male(n - 1) + 3 F_{n-2} else
  85.    = 3 F_{n+2} - 2
  86.  
  87.    https://oeis.org/A111314
  88.    """
  89.     assert isinstance(n, int), type(n)
  90.     assert n >= 0, n
  91.  
  92.     return fibonacci(n + 2)*3 - 2
  93.  
  94.  
  95. def nb_total(n):
  96.     """
  97.    = 4 F_{n+2} - 2
  98.    """
  99.     assert isinstance(n, int), type(n)
  100.     assert n >= 0, n
  101.  
  102.     return fibonacci(n + 2)*4 - 2
  103.  
  104.  
  105. def step(females, males):
  106.     assert isinstance(females, tuple), type(females)
  107.     assert isinstance(males, tuple), type(males)
  108.  
  109.     # Add half year
  110.     fs = []
  111.  
  112.     for female in females:
  113.         fs.append(female + 1)
  114.  
  115.     ms = []
  116.  
  117.     for male in males:
  118.         if 0 <= male < 5*2:  # <= 5 years
  119.             ms.append(male + 1)
  120.         else:                # become sterile
  121.             ms.append(-1)
  122.  
  123.     ms.sort(reverse=True)
  124.  
  125.     # New generation
  126.     for i in range(min(len(fs), len(ms))):
  127.         if fs[i] < 2:  # < 1 year
  128.             break
  129.  
  130.         assert ms[i] >= 0
  131.  
  132.         fs.append(0)
  133.         ms.extend([0]*3)
  134.  
  135.     return (tuple(fs), tuple(ms))
  136.  
  137.  
  138. def steps(nb):
  139.     assert isinstance(nb, int), type(nb)
  140.     assert nb >= 0, nb
  141.  
  142.     print('HY: Females     Males     Total')
  143.  
  144.     females = (1, )
  145.     males = (0, )
  146.  
  147.     for i in range(nb*2 + 1):
  148.         if i != 0:
  149.             females, males = step(females, males)
  150.  
  151.         assert len(females) == nb_female(i), i
  152.         assert len(males) == nb_male(i), i
  153.         assert len(females) + len(males) == nb_total(i), i
  154.  
  155.         # print(females, males)
  156.         print('{:2}: {:7} + {:7} = {:7}'.format(i,
  157.                                                 len(females), len(males),
  158.                                                 len(females) + len(males)))
  159.  
  160.  
  161. if __name__ == '__main__':
  162.     import sys
  163.  
  164.     NB_YEAR = (8 if len(sys.argv) < 2
  165.                else max(0, int(sys.argv[1])))
  166.  
  167.     steps(NB_YEAR)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top