/* 

  Picking teams in Picat.

  This model was inspired by David Curran's
  blog post "The Fairest Way to Pick a Team "
  http://liveatthewitchtrials.blogspot.se/2012/06/fairest-way-to-pick-team.html
  """
  What is the best way to pick a team? As kids we would always strictly alternate 
  between teams so team 1 had first team 2 the second pick and then team 1 again etc.
  
  Most things you can measure about people are on a bell curve. A small number of 
  people are bad, most are in the middle and a few are good. There are a few good 
  known metrics of ability. None are perfect, there is no one number that can sum up 
  ability. The simpler the sport the more one metric can tell you, in cycling VO2 max is 
  a very good indicator. Whereas in soccer VO2 max, kicking speed, vertical leap, number 
  of keep me ups you can do etc could all measure some part of football ability.
  
  So say there was one good metric for a task and teams were picked based on this. 
  Is the standard strict alteration, where Team 1 picks then Team 2 alternating, fair? 
  Fair here meaning both teams end up with a similar quality. 
  """
  
  For n = 10, where s = 1..n there are 20 optimal solutions with a diff of 1
  (with the symmetry breaking that x[1] is in team 1).
  
  Example:
   
  x: [1, 2, 2, 2, 1, 1, 1, 1, 2, 2]
  diff: 1
  team1: [1, 5, 6, 7, 8]  sum: 27
  team2: [2, 3, 4, 9, 10]  sum: 28
  ----------
  x: [1, 2, 2, 2, 1, 1, 1, 2, 1, 2]
  diff: 1
  team1: [1, 5, 6, 7, 9]  sum: 28
  team2: [2, 3, 4, 8, 10]  sum: 27


  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 =>
   S =  [35, 52, 17, 26, 90, 55, 57, 54, 41, 9, 75, 24, 17, 23, 62, 74, 100, 67, 40, 48, 7, 6, 44, 19, 16, 14, 2, 66, 70, 2, 43, 45, 76, 53, 90, 12, 88, 96, 30, 30, 36, 93, 74, 1, 52, 45, 38, 7, 24, 96, 17, 21, 12, 12, 23, 90, 77, 64, 37, 79, 67, 62, 24, 11, 74, 82, 51, 17, 72, 18, 37, 94, 43, 44, 32, 86, 94, 33, 97, 27, 38, 38, 29, 92, 35, 82, 22, 66, 80, 8, 62, 72, 25, 13, 94, 42, 51, 31, 69, 66],
  picking_teams(S).

go2 => 
   S = [1+(random2() mod 10) : _I in 1..300],
   writeln(S),
   time2($picking_teams(S)).
   

go3 => 
   S = [1+(random2() mod 10000) : _J in 1..100],
   writeln(s=S),
   time(picking_teams(S)).


go4 => 
   S = [41,85,90,47,15,37,90,77,4,95,6,13,77,15,17,91,12,22,15,68,11,23,41,77,71,42,23,30,77,30,74,90,97,28,89,18,3,74,86,99,25,20,58,13,59,52,81,5,49,50,56,91,85,67,47,51,70,76,59,88,51,79,79,23,18,21,43,74,85,69,11,28,55,94,3,58,83,74,87,84,98,83,59,9,88,56,33,36,21,59,4,42,68,94,11,88,25,38,89,38],
   writeln(s=S),
   time(picking_teams(S)).


picking_teams(S) => 
   N = S.length,
   NumTeams = 2,

   Diff :: 0..sum(S) div 2,

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

   % the difference in strength between the teams
   Diff #= abs(sum([S[I]*(X[I] #= 1) : I in 1..N]) - 
               sum([S[I]*(X[I] #= 2) : I in 1..N])),

  % same size of team
  count(1, X, #=, N div NumTeams),

  % divisibility of the sum
  Diff mod 2 #= sum(S) mod 2,

  % symmetry breaking: assign first person to team 1
  % X[1] #= 1,

  solve([$min(Diff),split], X),

  writeln(diff=Diff),
  writeln(x=X).