/* 

  Optimal picking one element from each list problem in MiniZinc. in Picat.

  From Stack Overflow
  Optimally picking one element from each list
  http://stackoverflow.com/questions/5645342/optimally-picking-one-element-from-each-list
  """
  I came across an old problem that you Mathematica/StackOverflow folks will 
  probably like and that seems valuable to have on StackOverflow for posterity.
  
  Suppose you have a list of lists and you want to pick one element from each 
  and put them in a new list so that the number of elements that are identical to 
  their next neighbor is maximized. In other words, for the resulting list l, 
  minimize Length@Split[l]. In yet other words, we want the list with the fewest 
  interruptions of identical contiguous elements.
  
  For example:
  
  pick[{ {1,2,3}, {2,3}, {1}, {1,3,4}, {4,1} }]
   --> {    2,      2,    1,     1,      1   }
  
  (Or {3,3,1,1,1} is equally good.)
  
  Here's a preposterously brute force solution:
  
  pick[x_] := argMax[-Length@Split[#]&, Tuples[x]]
  
  where argMax is as described here:
  posmax: like argmax but gives the position(s) of the element x for which f[x] is maximal
  
  Can you come up with something better? The legendary Carl Woll nailed this for 
  me and I'll reveal his solution in a week.
  """


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

*/

import util.
% import sat.
import cp.
% import mip.

main => go.

%
% First instance
%
go ?=>
  nolog,
  data(1,N,S),
  
  optimimal_picking_elements(N,S, X,SumDiffs),
  
  println(x=X),
  println(sumDiffs=SumDiffs),
  nl,
  fail,

  nl.

go => true.

%
% Check all instances
%
go2 =>
  nolog,
  foreach(P in 1..5)
    println(p=P),
    data(P,N,S),
    if time2(optimimal_picking_elements(N,S, X,SumDiffs)) then
      println(x=X),
      println(sumDiffs=SumDiffs),
      nl
    else
      println(not_solvable)
    end
  end,
  nl.

go2 => true.


%
% Count the number of optimal solutions for each instance.
% [p = 1,opt = 1,count = 2]
% [p = 2,opt = 2,count = 4]
% [p = 3,opt = 5,count = 40]
% [p = 4,opt = 16,count = 14288400]
% [p = 5,opt = 10,count = 80]
%
% Use CP for this.
go3 ?=>
  nolog,
  foreach(P in 1..5)
    data(P,N,S),
    optimimal_picking_elements(N,S, _X,SumDiffs),
    Count = count_all(optimimal_picking_elements(N,S, _X2,SumDiffs)),
    println([p=P,opt=SumDiffs,count=Count]) 
  end,
  nl.

go3 => true.

%
% Random instance.
% SAT is probably faster on this.
%
go4 ?=>
  nolog,
  N = 50,
  S = {{I : I in 1..N*2, random() mod 100 >= 70} : _ in 1..N},
  % println(s=S),
  nl,
  optimimal_picking_elements(N,S, X,SumDiffs),
  println(x=X),
  println(sumDiffs=SumDiffs),
  
  nl.

go4 => true.

optimimal_picking_elements(N,S, X,SumDiffs) =>
  SS = S.array_matrix_to_list_matrix.flatten,
  MinVal = min(SS),
  MaxVal = max(SS),  

  % decision variables
  X = new_list(N),
  X :: MinVal..MaxVal,

  SumDiffs :: 0..MaxVal*N, % to minimize

  % pick one element from each sub list
  foreach(I in 1..N)
    X[I] :: S[I].to_list
  end,

  % sum the number of differences between the selected elements
  % (to be minimized)
  SumDiffs #= sum([X[I] #!= X[I-1] : I in 2..N]),
  if var(SumDiffs) then
    solve($[min(SumDiffs),degree,split],X)
  else
    solve($[degree,split],X)  
  end.

%
% Problem instances
%

%
% Original problem
%
data(1,N,S) => 
 N = 5,
 S = {
     {1,2,3}, 
     {2,3}, 
     {1},
     {1,3,4}, 
     {4,1}
     }.

% other problem instances (from the comments)

%
% There are 4 optimal solutions (sum_diffs = 2)
%
data(2,N,S) => 
  N = 8,
  S = {
     {3, 10, 6}, 
     {8, 2, 10, 5, 9, 3, 6}, 
     {3, 7, 10, 2, 8, 5, 9}, 
     {6, 9, 1, 8, 3, 10}, 
     {1}, 
     {2, 9, 4}, 
     {9, 5, 2, 6, 8, 7}, 
     {6, 9, 4, 5}
    }.

%
% There are 40 optimal solutions with sum_diffs = 5
%
data(3,N,S) =>
  N = 8,
  S  = {{2, 8}, 
      {4, 2}, 
      {3}, 
      {9, 4, 6, 8, 2}, 
      {5}, 
      {8, 10, 6, 2, 3}, 
      {9, 4, 6, 3, 10, 1}, 
      {9}}.

%
% There are many many optimal solutions with sum_diffs = 16.
% "many many" = 14288400 solutions.
%
data(4,N,S) => 
  N = 30,
  S = {
    {4, 6, 18, 15}, 
    {1, 20, 16, 7, 14, 2, 9}, 
    {12, 3, 15}, 
    {17, 6, 13, 10, 3, 19}, 
    {1, 15, 2, 19}, 
    {5, 17, 3, 6, 14}, 
    {5, 17, 9}, 
    {15, 9, 19, 13, 8, 20}, 
    {18, 13, 5}, 
    {11, 5, 1, 12, 2}, 
    {10, 4, 7}, 
    {1, 2, 14, 9, 12, 3}, 
    {9, 5, 19, 8}, 
    {14, 1, 3, 4, 9}, 
    {11, 13, 5, 1}, 
    {16, 3, 7, 12, 14, 9}, 
    {7, 4, 17, 18, 6}, 
    {17, 19, 9}, 
    {7, 15, 3, 12}, 
    {19, 12, 5, 14, 8}, 
    {1, 10, 12, 8}, 
    {18, 16, 14, 19}, 
    {2, 7, 10}, 
    {19, 2, 5, 3}, 
    {16, 17, 3}, 
    {16, 2, 6, 20, 1, 3}, 
    {12, 18, 11, 19, 17}, 
    {12, 16, 9, 20, 4}, 
    {19, 20,10, 12, 9, 11}, 
    {10, 12, 6, 19, 17, 5}}.

%
% There are 80 solutions to this problem (sum_diffs = 10)
%
data(5,N,S) => 
  N = 30,
  S = {{4, 2, 7, 5, 1, 9, 10}, 
     {10, 1, 8, 3, 2, 7}, 
     {9, 2, 7, 3, 6, 4,  5}, 
     {10, 3, 6, 4, 8, 7}, 
     {7}, 
     {3, 1, 8, 2, 4, 7, 10, 6}, 
     {7, 6}, 
     {10, 2, 8, 5, 6, 9, 7, 3}, 
     {1, 4, 8}, 
     {5, 6, 1}, 
     {3, 2, 1}, 
     {10,6, 4}, 
     {10, 7, 3}, 
     {10, 2, 4}, 
     {1, 3, 5, 9, 7, 4, 2, 8}, 
     {7, 1, 3}, 
     {5, 7, 1, 10, 2, 3, 6, 8}, 
     {10, 8, 3, 6, 9, 4, 5, 7}, 
     {3, 10, 5}, 
     {1}, 
     {7, 9, 1, 6, 2, 4}, 
     {9, 7, 6, 2}, 
     {5, 6, 9, 7}, 
     {1, 5}, 
     {1,9, 7, 5, 4}, 
     {5, 4, 9, 3, 1, 7, 6, 8}, 
     {6}, 
     {10}, 
     {6}, 
     {7, 9}}.