/* 

  Greatest combination problem in Picat.

  From Stack Overflow:
  solving prolog puzzle
  http://stackoverflow.com/questions/10001344/solving-prolog-puzzle
  """
  I am trying to solve a puzzle in prolog that involves taking a square 
  of numbers (a list of a list of numbers) and returning the list of the 
  greatest combination of numbers starting at the top and going down, 
  row by row. Each move must be either down, down to the right, or 
  down to the left.

  I've been trying to do this for a while now, does anyone have a 
  place I could begin?

  for example:

  on the board [[0,2,1,0], [0,1,1,0], [0,10,20,30]]

  the best move would be [1,2,3] for 33 points.
  
  """

  Notes: 
   - the example use 0-based index
   - there are two optimal solutions (using 1-based) with
     values of 33:
     * 2,2,4  (values: 2, 1, 30)
     * 2,3,4  (values: 2, 1, 30)  This is the solution in the example.



  Another example (from the comments):
  """
  if the square is like this [0,1,1] [0,2,1] [10,0,0] the program should say 
  that the best path is [1,1,0] for 13 points. the 1st element in the first 
  line, 1st element in the 2nd and 0th element in the third. 
  """

  There are two optional solutions (with 13 points):
    * 2,2,1   (values 1, 2, 10)
    * 3,2,1   (values 1, 2, 10)


  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 ?=>
  foreach(P in 1..2)
    println(p=P),
    data(P,Grid,_),
    greatest_combination(Grid, X,MaxVal),
  
    println(maxVal=MaxVal),
    println('x     '=X),
    println(values=[Grid[I,X[I]] : I in 1..Grid.len]),
    nl
  end,
  nl.

go => true.

%
% All optimal solutions
%
go2 =>
  foreach(P in 1..1)
    println(p=P),
    data(P,Grid,MaxVal),
    greatest_combination(Grid, X,MaxVal),
  
    println(maxVal=MaxVal),
    println('x     '=X),
    println(values=[Grid[I,X[I]] : I in 1..Grid.len]),
    nl
  end,
  fail,
  nl.

greatest_combination(Grid, X,MaxVal) =>
  N = Grid.len,
  M = Grid[1].len,

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

  MaxVal #= sum([E : I in 1..N, matrix_element(Grid,I,X[I],E)]),

  foreach(I in 2..N)
    J :: 1..M,
    abs(X[I-1]-J) #<=1,
    X[I] #= J
  end,

  if var(MaxVal) then
    solve($[max(MaxVal)],X)
  else
    solve(X)  
  end.


%
% data
%
data(1,Grid,MaxVal) =>
  Grid = 
{{0, 2, 1, 0},
 {0, 1, 1, 0},
 {0,10,20,30}},
 MaxVal = 33.

data(2,Grid,MaxVal) =>
  Grid = 
 {{ 0, 1, 1}, 
  { 0, 2, 1},
  {10, 0, 0}},
  MaxVal = 13.