/* 

  Ordering a list of lists subject to constraints in Picat.

  From Stack Overflow:
  http://stackoverflow.com/questions/18581924/ordering-a-list-of-lists-subject-to-constraints
  "Ordering a list of lists subject to constraints"
  """
  I have encountered a surprisingly challenging problem arranging a matrix-like 
  (List of Lists) of values subject to the following constraints (or deciding it 
  is not possible):
  
  A matrix of m randomly generated rows with up to n distinct values (no repeats within 
  the row) arrange the matrix such that the following holds (if possible):
  
  1) The matrix must be "lower triangular"; the rows must be ordered in ascending lengths 
  so the only "gaps" are in the top right corner
  
  2) If a value appears in more than one row it must be in the same column (i.e. 
  rearranging the order of values in a row is allowed).
  
  Expression of the problem/solution in a functional language (e.g. Scala) 
  is desirable.
  
  Example 1 - which has a solution
  
  A B
  C E D
  C A B
  
  becomes (as one solution)
  
  A B
  E D C
  A B C
  
  since A, B and C all appear in columns 1, 2 and 3, respectively.

  Example 2 - which has no solution
  
  A B C
  A B D
  B C D
  
  has no solution since the constraints require the third row to have the C and D in the 
  third column which is not possible.
  """

  Notes:
    - this is just a proof-of-concept model since I thought it was an interesting
      problem.

    - this is a little simplified version since I assume that the matrix is
      already ordered by size (lower triangular). This should be easy to
      do as a preparsing step where constraint programming is not needed.

    - here we use integers are the letters A..E.
   
    - the shorter lists are filled with 0 (zero) so a matrix can be made.

  For problem A (the first example) this model give 4 different solutions:
  
    B A _
    E D C
    B A C
    ----------
    B A _
    D E C
    B A C
    ----------
    A B _
    E D C
    A B C
    ----------
    A B _
    D E C
    A B C




  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 ?=>
  Rows = 3,
  Cols = 3,

  L = [A,B,C,D,E],
  L = 1..L.len,
  MaxInt = E,

  % string representation of the values 1..max_int
  Str = ["A","B","C","D","E"],

  % problem A (satifiable)
  Matrix = {{A,B,0},
            {E,D,C},
            {A,B,C}},

  % problem B (unsatisfiable)
  % Matrix = {{A,B,C},
  %           {A,B,D},
  %           {B,C,D}},

  % the valid values (we skip 0, zero)
  Values = [ Matrix[I,J] : I in 1..Rows, J in 1..Cols, Matrix[I,J] > 0].sort_remove_dups,

  % identify the rows for a specific value.
  % E.g. for problem A: 
  %     ValueRows: [[1, 3], [1, 3], [2,3], [2], [2]]
  ValueRows = [ [I : I in 1..Rows, J in 1..Cols, Matrix[I,J] == V] : V in Values],

  %
  % decision variables
  %

  % The resulting matrix
  X = new_array(Rows,Cols),
  X :: 0..MaxInt,
               
  % the permutations from matrix to x
  Perms = new_array(Rows,Cols),
  Perms :: 1..MaxInt,

  foreach(I in 1..Rows)
    all_different_except_0([X[I,J] : J in 1..Cols]),
    all_different([Perms[I,J] : J in 1..Cols]),
    permutation3([Matrix[I,J] : J in 1..Cols], 
                 [Perms[I,J] : J in 1..Cols], 
                 [X[I,J] : J in 1..Cols])
  end,
  
  % zeros in X at the same place as in "matrix"
  foreach(I in 1..Rows, J in 1..Cols)
     if Matrix[I,J] == 0 then
        X[I,J] #= 0
     end
  end,
  
  % ensure that same values are in the same column for all rows
  % forall(k in values) (
  %    exists(j in 1..cols) (
  %      forall(i in value_rows[k]) (
  %         x[i,j] = k 
  %      )
  %    )
  % )
  % alternative: using a temp variable instead of exists
  % (might be faster)
  foreach(K in Values)
     J :: 1..Cols,
     foreach(I in ValueRows[K])
       % X[I,J] #= K
       matrix_element(X,I,J,K)
     end
  end,

  % symmetry breaking (experimental!)
  % increasing([X[Rows,J] : J in 1..Cols]),


  Vars = X.vars ++ Perms.vars,
  solve(Vars),

  println("X:"),
  foreach(I in 1..Rows)
    foreach(J in 1..Cols)
      if X[I,J] == 0 then
        printf(" _")
      else
        printf("%2s", Str[X[I,J]])
      end
    end,
    nl
  end,
  nl,
  println("Perms:"),
  foreach(Row in Perms)
    println(Row)
  end,
  nl,

  fail,
  
  nl.

go => true.


% The permutation from A <-> B using the permutation P
permutation3(A,P,B) =>
   foreach(I in 1..A.length)
       %  B[I] #= A[P[I]]
       PI #= P[I], 
       BI #= B[I], 
       element(PI, A, BI)
   end.