/* 

  Climbing stairs problem in Picat.

  http://plus.maths.org/content/its-long-way-top
  """
  Every time I come home I have to climb a flight of stairs. 
  When I'm feeling energetic I sometimes take two steps at a time. 
  This gives me a number of ways to climb the stairs. 
  For example, if there are ten steps, I could climb them taking 
  five leaps of two, giving the pattern
  
  2, 2, 2, 2, 2.
  
  Or I could only use a leap of two at the beginning and the end, giving the pattern
  
  2, 1, 1, 1, 1, 1, 1, 2.
  
  How many ways are there all together of climbing the ten steps?
  """

  For m=2
  n    #sols    #sols w/o symmetry breaking
  -----------------------------------------
   1    1          1
   2    2          3
   3    3          7
   4    5         19
   5    8         51 
   6   13        141        
   7   21        393
   8   34       1107
   9   55       3139
  10   89       8953

  With symmetry breaking: it's a familiar sequence...
  
  W/o symmetry breaking: 1,3,7,19,51,141,393,1107,3139,8953
  http://oeis.org/A002426: Central trinomial coefficients: largest coefficient of (1+x+x^2)^n.

  For m=3
   n  #sols
   --------
   1     1
   2     2
   3     4
   4     7
   5    13
   6    24
   7    44
   8    81
   9   149
  10   274
  
  1,2,4,7,13,24,44,81,149,274
  http://oeis.org/A000073: Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3)

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

*/

import cp.

main => go.

go ?=>
  Map = get_global_map(),
  Map.put(count,0),
  N = 10, % steps of the stairs
  M = 2, % max number of steps to take
  Symmetry = true,
  stairs(N,M,Symmetry, X,_Z),
  println(x=X),
  % println(z=Z),
  Map.put(count,Map.get(count)+1),
  fail,
  
  nl.

go => println(total=get_global_map().get(count)).

%
% M=2
%
go2 =>
  M = 2,
  Tot = 10,
  check(M,Tot),
  nl.

%
% M=3
%
go3 =>
  M = 3,
  Tot = 10,
  check(M,Tot),
  nl.

%
% Generalized
%
go4 =>
  Tot = 10,
  foreach(M in 1..10)
    println(m=M),
    check(M,Tot)
  end,
  nl.


check(M,Tot) =>
  println([m=M,tot=Tot]),
  println("With Symmetry breaking:"),
  foreach(N in 1..Tot)
    Count=count_all(stairs(N,M,true, _X,_Z)),
    println(N=Count)
  end,
  nl,
  println("Without Symmetry breaking:"),
  foreach(N in 1..Tot)
    Count=count_all(stairs(N,M,false, _X,_Z)),
    println(N=Count)
  end,
  nl.


stairs(N,M,Symmetry, X,Z) =>
  X = new_list(N),
  X :: 0..M,

  Z #= sum([ X[I]#>0 : I in 1..N ]),

  sum(X) #= N,
  % symmetry breaking (all 0 last)
  if Symmetry then
    foreach(I in 2..N)
      X[I-1] #= 0 #=> sum([X[J] #> 0 : J in I..N]) #= 0
    end
  end,

  Vars = X ++ [Z],
  solve($[],Vars).