/* 

  Matching problem of OR'ers in Picat.

  This is a port of the MiniZinc model http://hakank.org/minizinc/or_matching2.mzn
  that contains the following main comment:
  """
  This problem was inspired by the matching of OR'ers by
  Figure It Out's "Cupids with Computers" (Capgemini blog)
  http://blogs.uk.capgemini.com/orblog/2011/02/25/cupids-with-computers/
  
  where a bunch of OR'ers (including me) was matched according to some
  - not exactly stated - compatibility scores.

  Also, see the companion article
  "Two Deadly Sins"
  http://blogs.uk.capgemini.com/orblog/2011/03/02/two-deadly-sins/

  Here is an MiniZinc implementation of (pair) matching the different
  OR'ers. Note that the person unmatched person is also identified.
  
  This model is a MIP variant of 
    http://www.hakank.org/minizinc/or_matching.mzn
    http://www.hakank.org/minizinc/or_matching2.mzn

  and it use a 0/1 matrix for the assignments as well
  as using a dummy person which is assigned to the leftout.
  """

  This version is a 0/1 version with the 20th person is a dummy.

  Also, see http://hakank.org/picat/or_matching.pi for a non 0/1 model.

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

*/

import util.
% import cp. % slower
% import sat. % slower
import mip. % 0.01s

main => go.

go ?=>
  scores(Scores),
  N = Scores.len, 

  MaxScore = max([Scores[I,J] : I in 1..N, J in 1..N]),

  % decision variables: the assignment (matching)
  X = new_array(N,N),
  X :: 0..1,

  % sum of assigned scores, to maximize
  Total :: 0..N*MaxScore,

  foreach(I in 1..N)
    % Just one matching per person
    sum([X[I,J] : J in 1..N]) #= 1,
    sum([X[J,I] : J in 1..N]) #= 1,

    % a person cannot be matched to him/herself
    X[I,I] #= 0
  end,

  foreach(I in 1..N, J in 1..N)
    % ensure symmetry of matching:
    % a is assigned to b <-> b is assigned to a
    X[I,J] = X[J,I]
  end,

  % The total score
  Total #= sum([X[I,J]*Scores[I,J] : I in 1..N, J in I+1..N]),

  Vars = X.vars,
  solve($[max(Total)],Vars),

  println(total=Total),
  println("X:"),
  foreach(Row in X)
    println(Row)
  end,
  println("\nMatchings:"),

  Dummy = _,
  foreach(I in 1..N)
    P = [J : J in 1..N, X[I,J] == 1].first(),
    if Scores[I,P] == 0 then
      Dummy := P
    else
      printf("%2d = %2d: %d \n",I,P,Scores[I,P])    
    end,

  end,
  printf("Leftout = %2d\n",Dummy),
  nl,

  nl.

go => true.


%
% Convert a list representing an Rows x Cols matrix (e.g. from MiniZinc) to a proper array matrix.
% 
convert_board(R,C,Board0) = Board.array_matrix_to_list_matrix =>
  Board = new_array(R,C),
  foreach(I in 0..R-1, J in 0..C-1)
    Board[I+1,J+1] := Board0[C*I+J+1]
  end.


% Note the scores are from 1.0 to 9.2 but since many solves don't
% support floats I multiplied by 10 so the range is from 10 to 92
% and 0 is for the diagonals.
% 
% #20 is the Dummy with score DD
%
scores(Scores) => 
  DD = 0, % the score for the Dummy score
  N = 20, % 20 is the dummy
  Scores = convert_board(N,N,
  [
%  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19, Dummy
  00, 30, 10, 33, 49, 50, 38, 32, 92, 61, 31, 22, 31, 55, 26, 19, 21, 61, 14, DD, %  1
  30, 00, 21, 23, 10, 33, 28, 15, 22, 22, 36, 33, 36, 38, 36, 24, 26, 22, 55, DD, %  2
  10, 21, 00, 10, 22, 26, 10, 22, 10, 41, 26, 52, 21, 24, 21, 33, 33, 10, 33, DD, %  3
  33, 23, 10, 00, 24, 25, 37, 24, 36, 36, 22, 22, 22, 22, 22, 10, 13, 36, 10, DD, %  4
  49, 10, 22, 24, 00, 41, 55, 42, 57, 57, 16, 15, 21, 69, 16, 33, 31, 57, 23, DD, %  5
  50, 33, 26, 25, 41, 00, 25, 19, 53, 53, 44, 33, 39, 61, 34, 27, 30, 53, 22, DD, %  6
  38, 28, 10, 37, 55, 25, 00, 29, 36, 36, 22, 22, 44, 58, 22, 32, 18, 36, 10, DD, %  7
  32, 15, 22, 24, 42, 19, 29, 00, 30, 30, 16, 10, 16, 21, 11, 59, 36, 61, 45, DD, %  8
  92, 22, 10, 36, 57, 53, 36, 30, 00, 69, 28, 27, 33, 50, 28, 21, 19, 69, 11, DD, %  9
  61, 22, 41, 36, 57, 53, 36, 30, 69, 00, 28, 27, 33, 50, 28, 21, 19, 69, 11, DD, % 10
  31, 36, 26, 22, 16, 44, 22, 16, 28, 28, 00, 33, 42, 39, 37, 30, 27, 28, 25, DD, % 11
  22, 33, 52, 22, 15, 33, 22, 10, 27, 27, 33, 00, 38, 36, 38, 26, 21, 27, 21, DD, % 12
  31, 36, 21, 22, 21, 39, 44, 16, 33, 33, 42, 38, 00, 39, 42, 57, 27, 33, 25, DD, % 13
  55, 38, 24, 22, 69, 61, 58, 21, 50, 50, 39, 36, 39, 00, 34, 27, 32, 50, 22, DD, % 14
  26, 36, 21, 22, 16, 34, 22, 11, 28, 28, 37, 38, 42, 34, 00, 30, 22, 28, 25, DD, % 15
  19, 24, 33, 10, 33, 27, 32, 59, 21, 21, 30, 26, 57, 27, 30, 00, 39, 52, 37, DD, % 16
  21, 26, 33, 13, 31, 30, 18, 36, 19, 19, 27, 21, 27, 32, 22, 39, 00, 19, 34, DD, % 17
  61, 22, 10, 36, 57, 53, 36, 61, 69, 69, 28, 27, 33, 50, 28, 52, 19, 00, 11, DD, % 18
  14, 55, 33, 10, 23, 22, 10, 45, 11, 11, 25, 21, 25, 22, 25, 37, 34, 11, 00, DD, % 19
  DD, DD, DD, DD, DD, DD, DD, DD, DD, DD, DD, DD, DD, DD, DD, DD, DD, DD, DD, DD  % Dummy
  ]).