/* 

  Nonogram GCHQ puzzle in Picat.

  "A Christmas card with a cryptographic twist for charity"
  http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx

  via 
  "Can you solve the British spy agency’s ridiculously difficult Christmas puzzle?"
  http://qz.com/570665/can-you-solve-the-british-spy-agencys-ridiculously-difficult-christmas-puzzle/



  Comments:
  - This is not an ordinary Nonogram puzzle that can be solved with
    http://hakank.org/picat/nonogram_regular.pi .

    It has also some fixed black squares to be taken care of. Hence the separate model.

  - It's solved in 0.024s with 0 backtracks.
    The problem instance is actually solved (uniquely) _before_ the call to solve/1
    using the CP solver. 

    The domain tracing is shown in go2/0, using trace_domains2d/2
    from the trace_domains module: http://hakank.org/picat/trace_domains.pi .
    See the huge output at http://hakank.org/picat/nonogram_gchq_trace.txt .

  - Without the 22 black cell hints there are 4 distinct solutions.

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

*/

import cp.
import util.
import trace_domains. % from http://hakank.org/picat/trace_domains.pi 


main => go.


go ?=>
  rows(Rows),
  cols(Cols),
  blacks(Blacks),  

  % without domain tracing
  Trace = false,

  nonogram(Rows,Cols,Blacks,Trace,X),
  print_nonogram(X),
  nl,
  fail,

  nl.

go => true.

%
% with domain tracing
%
go2 ?=>
  rows(Rows),
  cols(Cols),
  blacks(Blacks),  

  Trace = true, % with domain tracing

  nonogram(Rows,Cols,Blacks,Trace,X),
  print_nonogram(X),
  nl,
  fail,

  nl.

go2 => true.



%
% Print a solution of Nonogram
%
print_nonogram(X) =>
  foreach(I in 1..X.length)
    foreach(J in 1..X[1].length)
      printf("%w", cond(X[I,J]=1," ","#"))
    end,
    nl
  end,
  nl.


% 
% nonogram/3: Used by nonogram/2.
%
nonogram(RowRules,ColRules,Blacks,Trace, X) =>

  Rows=RowRules.len,
  Cols=ColRules.len,
  X = new_array(Rows,Cols),
  X :: 1..2, % to be translated in output to 0..1

  % Fix the black cells
  foreach([C,R] in Blacks) 
    X[R,C] #= 2
  end,

  if Trace then trace_domains2d(X,"after blacks") end,

  foreach(I in 1..Rows)
    make_automaton2([X[I,J] : J in 1..Cols], RowRules[I]),
    if Trace then trace_domains2d(X,to_fstring("after row: %d",I)) end
  end,
  foreach(J in 1..Cols) 
    make_automaton2([X[I,J] : I in 1..Rows], ColRules[J]),
    if Trace then trace_domains2d(X,to_fstring("after col: %d",J)) end
  end,

  if Trace then trace_domains2d(X,"before solve") end,


  % The problem is solved before the call to solve/1
  Vars = X.to_list(),
  % println(vars=Vars),

  % solve($[constr,split],Vars).
  solve(Vars). 




% See http://hakank.org/picat/nonogram_regular.pi
%
% Another approach of encoding of the transition states.
% It seems to be faster sometimes than make_automaton/2.
%
make_automaton2(X,Pattern) =>
  % println($make_automaton2(_,Pattern)),
  N = Pattern.length,

  if N = 0; sum(Pattern) = 0 then
    % zero clues
    Len = 1,
    States = new_array(1,2),
    States[1,1] := 1,
    States[1,2] := 1
  else 
    Len = max(length([Pattern[I] : I in 1..N, Pattern[I] > 0]) + sum(Pattern),1),
    Tmp = [0],
    C = 0,
    foreach(P in Pattern) 
       foreach(I in 1..P)
         Tmp := Tmp ++ [1],
         C:= C+1
       end,
       if C < Len - 2 then
         Tmp := Tmp ++ [0]
       end
    end, 

    States = new_array(Len,2),
    States[Len,1] := Len, % final state
    States[Len,2] := 0,
    foreach(I in 1..Len)
      if Tmp[I] == 0 then
        States[I,1] := I,
        States[I,2] := I+1
      else 
        if I < Len then
          if Tmp[I+1] = 1 then
            States[I,1] := 0,
            States[I,2] := I+1
          else 
            States[I,1] := I+1,
            States[I,2] := 0
          end
        end
      end    
    end
  end,

  regular(X,Len,2,States,1,[Len]).

rows(Rows) => 
Rows = 
[
 [7,3,1,1,7],
 [1,1,2,2,1,1],
 [1,3,1,3,1,1,3,1],
 [1,3,1,1,6,1,3,1],
 [1,3,1,5,2,1,3,1],
 [1,1,2,1,1],
 [7,1,1,1,1,1,7],
 [3,3],
 [1,2,3,1,1,3,1,1,2],
 [1,1,3,2,1,1],
 [4,1,4,2,1,2],
 [1,1,1,1,1,4,1,3],
 [2,1,1,1,2,5],
 [3,2,2,6,3,1],
 [1,9,1,1,2,1],
 [2,1,2,2,3,1],
 [3,1,1,1,1,5,1],
 [1,2,2,5],
 [7,1,2,1,1,1,3],
 [1,1,2,1,2,2,1],
 [1,3,1,4,5,1],
 [1,3,1,3,10,2],
 [1,3,1,1,6,6],
 [1,1,2,1,1,2],
 [7,2,1,2,5]
].

cols(Cols) =>
Cols =
[
[7,2,1,1,7],
[1,1,2,2,1,1],
[1,3,1,3,1,3,1,3,1],
[1,3,1,1,5,1,3,1],
[1,3,1,1,4,1,3,1],
[1,1,1,2,1,1],
[7,1,1,1,1,1,7],
[1,1,3],
[2,1,2,1,8,2,1],
[2,2,1,2,1,1,1,2],
[1,7,3,2,1],
[1,2,3,1,1,1,1,1],
[4,1,1,2,6],
[3,3,1,1,1,3,1],
[1,2,5,2,2],
[2,2,1,1,1,1,1,2,1],
[1,3,3,2,1,8,1],
[6,2,1],
[7,1,4,1,1,3],
[1,1,1,1,4],
[1,3,1,3,7,1],
[1,3,1,1,1,2,1,1,4],
[1,3,1,4,3,3],
[1,1,2,2,2,6,1],
[7,1,3,2,1,1]
].




%
% Note: it's in the format [Col,Row], which is taken care of in nonogram/4.
%
blacks(Blacks) =>
Blacks = [
   [4,4],
   [5,4],
   [13,4],
   [14,4],
   [22,4],

   [7,9],
   [8,9],
   [11,9],
   [15,9],
   [16,9],
   [19,9],
   [7,17],
   [12,17],
   [17,17],
   [21,17],
   [4,22],
   [5,22],
   [10,22],
   [11,22],
   [16,22],
   [21,22],
   [22,22]
 ].