/* 

  Rosalind problem Mortal Fibonacci Rabbits in Picat.

  https://rosalind.info/problems/fibd/
  """
  Problem

  [ 
    Figure 4. A figure illustrating the propagation of Fibonacci's rabbits 
    if they die after three months. 
  ]

  Recall the definition of the Fibonacci numbers from “Rabbits and Recurrence Relations”, which followed 
  the recurrence relation Fn=Fn−1+Fn−2 and assumed that each pair of rabbits reaches maturity in one month 
  and produces a single pair of offspring (one male, one female) each subsequent month.

  Our aim is to somehow modify this recurrence relation to achieve a dynamic programming solution in the 
  case that all rabbits die out after a fixed number of months. See Figure 4 for a depiction of a rabbit 
  tree in which rabbits live for three months (meaning that they reproduce only twice before dying).

  Given: Positive integers n≤100 and m≤20.

  Return: The total number of pairs of rabbits that will remain after the n-th month if all rabbits live for m months.

  Sample Dataset
    6 3
  Sample Output
    4
  """

  The picture

  Months   1    2    3    4    5    6
             
                x
             /
            /
       o  x
           \ 
            \  o  

  Pairs   1    1     2    2   3    4  


  This model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.


main => go.

go ?=>
  N = 6, % 92,
  M = 3, % 17,
  F = fibd(N,M),
  println(F),
  println(F.last),
  nl.
go => true.

% Port of a Python program.
fibd(N, L)  = Fib =>
    M = 1,
    Fib1 = [],
    % Note: Loop is 0 based and then adjusted array access with + 1
    foreach(I in 0..N-1)
        if I < L then
            if I == 0; I == 1 then
                Fib1 := Fib1 ++ [1]
            else
                Fib1 := Fib1 ++ [Fib1[Fib1.len] + Fib1[Fib1.len-1]]
            end
        else
            Rabbits = 0,
            foreach(J in I-L..I-M-1)
                Rabbits := Rabbits + Fib1[J+1]
            end,
            Fib1 := Fib1 ++ [Rabbits]
        end
    end,
    Fib = Fib1.