OPiMedia

cats_problem.py

Jul 1st, 2015
287
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×