/* 

  Odd-even sequences in Picat.

  From MindYourDecisions:
  http://mindyourdecisions.com/blog/2014/04/21/monday-puzzle-how-many-odd-even-sequences-are-there/
  """
  From the numbers 1, 2, … n, start by writing an odd number, and keep writing 
  larger numbers–alternating between even and odd–until you stop at n. Call this an 
  odd-even sequence of n.
  
  For example, if n = 3, then the only odd-even sequences are 123 and 3.
  
  If n = 8, then the sequences 1278 and 58 are odd-even, but other sequences are not, 
  like 278 (starts with even number), 138 (two odd numbers in a row), 1438 
  (going from 4 to 3 is a smaller number).
  
  For an arbitrary n, how many odd-even sequences are there?
  """

  Here are the solutions for N = 7
     [1,2,3,4,5,6,7]
     [1,2,3,4,7,0,0]
     [1,2,3,6,7,0,0]
     [1,2,5,6,7,0,0]
     [1,2,7,0,0,0,0]
     [1,4,5,6,7,0,0]
     [1,4,7,0,0,0,0]
     [1,6,7,0,0,0,0]
     [3,4,5,6,7,0,0]
     [3,4,7,0,0,0,0]
     [3,6,7,0,0,0,0]
     [5,6,7,0,0,0,0]
     [7,0,0,0,0,0,0]


  Number of solutions for N 1..11:

  N  #sols
  =======
   1  1
   2  1
   3  2
   4  3
   5  5
   6  8
   7 13
   8 21
   9 34
  10 55
  11 89
  
  (i.e. the Fibonacci number sequence)
 

  Note: When I first read the problem, I missed the requirement that 
        the last number in the sequence should be n
        ("stop at n" is somewhat ambigous; I read it as "stop when reaching >= n").
        Here's the number of solutions for that problem, also 
        Fibonacci related.
  N  #sols
  ========
   1   1
   2   2
   3   4
   4   7
   5  12
   6  20
   7  33
   8  54
   9  88
  10 143
  11 232
  

  This is: 1,2,4,7,12,20,33,54,88,143,232
  http://oeis.org/A000071: Fibonacci numbers - 1. 


  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 ?=>
  N = 7,

  odd_even_sequence(N,X),
  println(X),
  fail,

  nl.

go => true.

%
% Count the number of solutions.
%
go2 =>
  foreach(N in 1..12)
    Count = count_all(odd_even_sequence(N,_X)),
    printf("%2d %6d\n",N,Count)
  end,
  nl.

odd_even_sequence(N,X) =>
  X = new_list(N),
  X :: 0..N,

  alldifferent_except_0(X),
  
  % start with odd number
  X[1] mod 2 #= 1,
  
  % last number (> 0) is N
  Bs = [],
  foreach(I in 1..N)
     B :: 0..1,
     % N is the last number of followed be 0s
     B #= 1 #<=> (X[I] #= N #/\ sum([X[J] #= 0 : J in I+1..N]) #= N-I),
     Bs := [B|Bs]
  end,
  sum(Bs) #>= 1,
  
  % alternating odd/even or 0
  foreach(I in 2..N)
      (X[I] #= 0)
      #\/ % alternate odd/even numbers
      (X[I] mod 2 #= 0 #<=> X[I-1] mod 2 #= 1)
  end,
  
  % collect 0's last
  collect_0s_last(X),
  
  increasing_except_0_strict(X),

  Vars = X ++ Bs,
  solve(Vars).



increasing_except_0(A) =>
  increasing_except_C(A,0).

increasing_except_0_strict(A) =>
  increasing_except_C_strict(A,0).


increasing_except_C(A,C) =>
  N = A.len,
  foreach(I in 1..N, J in I+1..N)
    (A[I] #!= C #/\ A[J] #!= C) #=> (A[I] #<= A[J])
  end.

increasing_except_C_strict(A,C) =>
  N = A.len,
  foreach(I in 1..N, J in I+1..N)
    (A[I] #!= C #/\ A[J] #!= C) #=> (A[I] #< A[J])
  end.

%
% All 0s must be placed last
%
collect_0s_last(X) =>
  N = X.len,
  foreach(I in 1..N)
    X[I] #= 0 #=> sum([X[J] #> 0 : J in I+1..N]) #= 0
  end.