/* 

  Map coloring with costs in Picat.

  From Tom Zaremba
  "Graph Coloring, Map Coloring, and Chromatic Number"
  http://www.geom.uiuc.edu/~zarembe/grapht2.html
  """
  You need to color the entire map of South America. This may 
  seem simple, but but there are some rescrictions.

     - No country may touch another country of the same color.
     - You will be charged each time you use a color to fill in a 
       country -regardless of its size.
     - You must color the map as cheaply as possible. 
  
     Color   Cost Per Country
     Red     $100
     Blue    $200
     Green   $300
     Orange  $400
     Yellow  $500
     Purple  $600
     Brown   $700
     Black   $800
  
  The cost for each color is shown above.
  """

  The minimum cost is 3100 and there are 16 different solutions.
  Here is one solution:

    total: 3100
    x: [3, 2, 1, 2, 1, 2, 1, 3, 4, 1, 2, 2, 3, 1, 2, 1]
  
    Galapagos Islands: Green  300
    Ecuador          : Blue   200
    Colombia         : Red    100
    Venezuela        : Blue   200
    Guyana           : Red    100
    Suriname         : Blue   200
    French Guiana    : Red    100
    Brazil           : Green  300
    Peru             : Orange 400
    Bolivia          : Red    100
    Paraguay         : Blue   200
    Chile            : Blue   200
    Argentina        : Green  300
    Uruguay          : Red    100
    Falklands Island : Blue   200
    South Georgia    : Red    100

  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 ?=>

  Countries = [GalapagosIslands,Ecuador,Colombia,Venezuela,Guyana,Suriname,FrenchGuiana,
               Brazil,Peru,Bolivia,Paraguay,Chile,Argentina,Uruguay,FalklandsIsland,SouthGeorgia],
  NumCountries = Countries.len,
  Countries = 1..NumCountries,
  println(numCountries=NumCountries),

  Neighbours = 
  {
  { Ecuador, Colombia},  % GalapagosIslands,
  { GalapagosIslands,Colombia,Peru},  % Ecuador
  { Venezuela, Ecuador, Peru, Brazil},  % Colombia
  { Colombia, Guyana, Brazil},   % Venezuela
  { Venezuela, Suriname, Brazil},   % Guyana
  { Guyana, FrenchGuiana, Brazil},   % Suriname
  { Suriname, Brazil},   % FrenchGuiana
  { FrenchGuiana, Suriname, Guyana, Venezuela, Colombia, Peru, Bolivia, Paraguay, Uruguay},   % Brazil
  { GalapagosIslands, Ecuador, Colombia, Brazil, Bolivia, Chile},   % Peru
  { Peru, Brazil, Paraguay, Chile, Argentina},   % Bolivia
  { Bolivia, Brazil, Argentina, Uruguay},   % Paraguay
  { Peru, Bolivia, Argentina},   % Chile
  { Chile, Bolivia, Paraguay, Uruguay, FalklandsIsland},   % Argentina
  { Argentina, Paraguay, Brazil},   % Uruguay
  { Argentina, SouthGeorgia},   % FalklandsIsland
  { FalklandsIsland}   % SouthGeorgia
  },

  CountriesStr = [
   "Galapagos Islands",
   "Ecuador          ",
   "Colombia         ",
   "Venezuela        ",
   "Guyana           ",
   "Suriname         ",
   "French Guiana    ",
   "Brazil           ",
   "Peru             ",
   "Bolivia          ",
   "Paraguay         ",
   "Chile            ",
   "Argentina        ",
   "Uruguay          ",
   "Falklands Island ",
   "South Georgia    "
  ],

  % Colors/Cost
  % Red     $100
  % Blue    $200
  % Green   $300
  % Orange  $400
  % Yellow  $500
  % Purple  $600
  % Brown   $700
  % Black   $800
  % Colors = [Red,Blue,Green,Orange,Yellow,Purple,Brown,Black],
  % NumColors = Colors.len,
  % Colors = 1..NumColors,
  
  ColorCost = [100,200,300,400,500,600,700,800],
  ColorStr = 
   ["Red   ", 
    "Blue  ",
    "Green ",
    "Orange",
    "Yellow",
    "Purple",
    "Brown ",
    "Black "],

  % Note: must be 4 colors (3 is not enough)
  MaxColors = 4,

  % Assigned colors
  X = new_list(NumCountries),
  X :: 1..MaxColors,
  
  Total :: 0..NumCountries*max(ColorCost),


  foreach(I in 1..NumCountries, J in Neighbours[I])
    X[I] #!= X[J]
  end,

  Total #= sum([C : I in 1..NumCountries,element(X[I],ColorCost,C)]),

  % Total #= 3100, %

  solve($[min(Total)],X),
  % solve($[],X),  

  println(total=Total),
  println(x=X),
  nl,
  foreach(I in 1..NumCountries)
    printf("%-20s %-10s $%d\n", CountriesStr[I], ColorStr[X[I]], ColorCost[X[I]])
  end,
  % fail,
  nl.

go => true.