/* 

  Anti-Pascal pyramid in Picat.

  From https://russelllim22.medium.com/what-is-so-hard-about-this-imo-problem-e3200fcca4fb
  """
  Over 90% of International Mathematical Olympiad (IMO) participants scored zero marks 
  for this question. But the solution is beautifully simple.

  '''
  An anti-Pascal pyramid is a finite set of numbers, placed in a triangle-shaped array so 
  that the first row of the array contains one number, the second row contains two numbers, 
  the third row contains three numbers and so on; and, except for the numbers in the bottom 
  row, each number equals the absolute value of the difference of the two numbers below it. 
  For instance, the triangle below is an anti-Pascal pyramid with four rows, in which every 
  integer from 1 to 1 + 2 + 3 + 4 = 10 occurs exactly once:

          4 
        2  6
      5  7  1
    8  3  10  9

  Is it possible to form an anti-Pascal pyramid with 2018 rows, using every integer from 1 to 
  (1 + 2 + 3 + … + 2018) exactly once?
  """

  Solving the stated problem is little too large...
  Picat> X = sum([I : I in 1..2008])
  X = 2017036



  Positions:
       1
      2 3
    4  5  6
  7  8  9  10

  The constraints are then that
    abs(X[2]-X[3]) == X[1]
    abs(X[4]-X[5]) == X[2]
    abs(X[5]-X[6]) == X[3]
    ...


  Here are some solutions for smaller N. 
  Note that we have the symmetry breaking that the two entries
  in the second row should be increasing (i.e. X[2] < X[3]).

  n = 3

   1 
  2  3 

   2 
  1  3 

  n = 6
    1 
   3  4 
  5  2  6 

    2 
   3  5 
  4  1  6 

    3 
   1  4 
  5  6  2 

    3 
   2  5 
  4  6  1 

  n = 10

     3 
    2  5 
   7  9  4 
  8  1 10  6 

     3 
    4  7 
   5  9  2 
  6  1 10  8 

     4 
    1  5 
   6  7  2 
  9  3 10  8 

     4 
    2  6 
   5  7  1 
  8  3 10  9 

  n = 15

      5 
     4  9 
    7 11  2 
   8  1 12 10 
  6 14 15  3 13 



  Number of solutions (with symmetry breaking):
  N   #sols
  ---------
   3   2
   6   4
  10   4
  15   1

  There are no solutions for n = 21,28,36,45,55.

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

*/

import cp.
% import sat.


main => go.

%
% Test anti-Pascal pyramids
% for some small triangle numbers
% Tri = [1,3,6,10,15,21,28,36,45,55,66,78,91,105]
%
go ?=>
  nolog,
  Tris = [I*(I+1) div 2 : I in 1..20],
  println(tris=Tris),
  member(N,Tris),
  N > 1,
  println(n=N),
  
  anti_pascal_pyramid(N,Ts,X),
  println(ts=Ts),
  % println(x=X),
  C = Ts.len,
  foreach(Row in Ts)
    print([' ' : _ in 1..C]),
    foreach(R in Row)
      printf("%2d ",X[R])
    end,
    nl,
    C := C - 1
  end,
  nl,
  fail,
  nl.
go => true.

%
% How many solutions for each anti-Pascal pyramid (i.e. triangular numbers)
%
go2 ?=>
  nolog,
  Tris = [I*(I+1) div 2 : I in 2..20],
  println(tris=Tris),
  foreach(N in Tris)
    time(Count = count_all(anti_pascal_pyramid(N,_Ts,_X))),
    println(n=N=Count)
  end,
  nl.
go2 => true.

%
% We assume that N is a triangle number so that 1..N
% fit in an anti-Pascal pyramid.
%
anti_pascal_pyramid(N,Ts,X) => 

  X = new_list(N),
  X :: 1..N,

  all_different(X),
  
  % The triangle numbers for 1..N
  Tri = [I*(I+1) div 2 : I in 1..N, (I*(I+1) div 2)<= N],

  % Create the Triangle structure
  T = [[1]],
  foreach(I in 2..Tri.len)
    T := T ++ [Tri[I-1]+1..Tri[I]]
  end,
  % And add the constraints
  % The absolute difference of the neighbours is the entry in the previous line  
  foreach(R in 2..T.len)
    foreach(I in 1..T[R].len-1)
      abs(X[T[R,I]] - X[T[R,I+1]]) #=  X[T[R-1,I]]
    end
  end,
  % Symmetry breaking, the first entry in the second line (X[2])
  % should be less than the second entry (X[3])
  X[2] #< X[3],
  
  Ts = T,
  solve($[ff,split],X).