/* 

  Number generation in Picat.

  Given some numbers, generate a specific sum with the simple arithmetic operators.

  Cf http://hakank.org/picat/devils_word.pi

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

*/

import cp,util.


main => go.

%
% Can you get 666 with just 9s?
% Yes,10 9's can do that:
% 
% [9,+,9,=,18,cum = 18]
% [9,*,9,=,81,cum = 99]
% [9,*,9,=,81,cum = 180]
% [9,*,9,=,81,cum = 261]
% [9,*,9,=,81,cum = 342]
% [9,*,9,=,81,cum = 423]
% [9,*,9,=,81,cum = 504]
% [9,*,9,=,81,cum = 585]
% [9,*,9,=,81,cum = 666]
% total = 666
%
% There are 9 different solutions, i.e. the position of the addition.
%
go ?=>
  nolog,
  member(N,2..10),
  println(n=N),
  Dom = [9], % the numbers to use
  Total #= 666,
  gen(N,Dom,Total, X,Ops) ,
  print_sol(N,X,Ops,Total),
  
  fail,

  nl.

go => true.

%
% Can we generate all the numbers 1..100 with just 2 and 5?
% Answer: Yes, it can be done with a MaxLen of 8.
% E.g.
% 
% [2,div,2,=,1,cum = 1]
% [2,-,5,=,-3,cum = -2]
% [5,*,5,=,25,cum = 23]
% [5,*,5,=,25,cum = 48]
% [5,*,5,=,25,cum = 73]
% [5,*,5,=,25,cum = 98]
% total = 98
%
% As with 3 and 5, with a MaxLen of 7.
%
%
% Can we create 1.100 with just 5 with a max len of 10?
% Nope: 19 and 94 cannot be generated.
%
% But with a max length of 11 we can. Here's how to make 19 and 94:
%
% [5,+,5,=,10,cum = 10]
% [5,div,5,=,1,cum = 11]
% [5,div,5,=,1,cum = 12]
% [5,div,5,=,1,cum = 13]
% [5,div,5,=,1,cum = 14]
% [5,div,5,=,1,cum = 15]
% [5,div,5,=,1,cum = 16]
% [5,div,5,=,1,cum = 17]
% [5,div,5,=,1,cum = 18]
% [5,div,5,=,1,cum = 19]
% total = 19
% 
% [5,+,5,=,10,cum = 10]
% [5,+,5,=,10,cum = 20]
% [5,+,5,=,10,cum = 30]
% [5,+,5,=,10,cum = 40]
% [5,*,5,=,25,cum = 65]
% [5,*,5,=,25,cum = 90]
% [5,div,5,=,1,cum = 91]
% [5,div,5,=,1,cum = 92]
% [5,div,5,=,1,cum = 93]
% [5,div,5,=,1,cum = 94]
% total = 94
%
% Note that they make heavily use of 5 div 5 = 1.
%
%
% What can we do with single domain of 1..9 in max 11 steps with +,-,*,div?
% Here's the numbers we can create:
% 1: can: 1-20                          cannot: 21-100
% 2: can: 1-34,36-37,40                 cannot: 35,38-39,41-100
% 3: can: 1-76,78-79,81-82,84,87,90     cannot: 77,80,83,85-86,88-89,91-100
% 4: can: 1-62,64-70,72-77,80-85,88-92,96-100 cannot: 63,71,78-79,86-87,93-95
% 5: can: 1-100
% 6: can: 1-10,12-21,24-32,36-45,48-56,60-67,72-80,84-91,96-100 cannot: 11,22-23,33-35,46-47,57-59,68-71,81-83,92-95
% 7: can: 1-10,14-23,28-36,42-75,77-88,91-100 cannot: 11-13,24-27,37-41,76,89-90
% 8: can: 1-10,16-25,32-40,48-55,64-73,80-88,96-100 cannot: 11-15,26-31,41-47,56-63,74-79,89-95
% 9: can: 1-10,18-27,36-44,54-61,72-78,81-95,99-100 cannot: 11-17,28-35,45-53,62-71,79-80,96-98

% If we also allow the use of ** (power):
%
% 1: can: 1-20                          cannot: 21-100
% 2: can: 1-34,36-37,40                 cannot: 35,38-39,41-100   (same as without **)
% 3: can: 1-100
% 4: can: 1-62,64-70,72-77,80-85,88-92,96-100 cannot: 63,71,78-79,86-87,93-95 (same as without **)
% 5: can: 1-100
% 6: can: 1-10,12-21,24-32,36-45,48-56,60-67,72-80,84-91,96-100 cannot: 11,22-23,33-35,46-47,57-59,68-71,81-83,92-95 (same as without **)
% 7: can: 1-10,14-23,28-36,42-75,77-88,91-100 cannot: 11-13,24-27,37-41,76,89-90 (same as without **)
% 8: can: 1-10,16-25,32-40,48-55,64-73,80-88,96-100 cannot: 11-15,26-31,41-47,56-63,74-79,89-95 (same as without **)
% 9: can: 1-10,18-27,36-44,54-61,72-78,81-95,99-100 cannot: 11-17,28-35,45-53,62-71,79-80,96-98 (sam as without **)
% 
% So the only change is that 3 can generate all numbers with **.
% 
go2 ?=>
  nolog,
  MaxLen = 11,
  Dom = [9], 
  CannotCreate = [],
  CanCreate = [],
  foreach(Total in 1..100)
    println(total=Total),
    if member(N,2..MaxLen), gen(N,Dom,Total, X,Ops) then
      print_sol(N,X,Ops,Total),
      CanCreate := CanCreate ++ [Total]
    else
      println(cannot_create=Dom=Total),
      CannotCreate := CannotCreate ++ [Total]
    end
  end,
  CanRanges = make_ranges(CanCreate),
  println(can_create=CanRanges),
  CannotRanges = make_ranges(CannotCreate),
  println(cannot_create=CannotRanges),
  nl.

go2 => true.



%
% This is the Devil's word example (http://hakank.org/picat/devils_word.pi
%
go3 ?=>
  nolog,
  S = "håkan kjellerstrand",
  X = [ord(C) : C in S],
  println(x=X),
  N = X.len,
  Dom = X.sort_remove_dups,
  Total #= 666,   
  gen(N,Dom,Total, X,Ops) ,
  print_sol(N,X,Ops,Total),
  
  fail,

  nl.

go3 => true.

%
% Test all single domains 1..9 for generating 1..100.
% (cf go2/0).
% Note: sat might be faster for this.
% 
go4 ?=>
  nolog,
  MaxLen = 11,
  Cannot = [],
  foreach(Dom in 1..9)
    println(dom=Dom),
    CannotCreate = [],  
    foreach(Total in 1..100)
       % println(total=Total),
       if member(N,2..MaxLen),gen(N,[Dom],Total, _X,_Ops) then
         true
         % print_sol(N,X,Ops,Total)
       else
         println(cannot_create=[dom=Dom,total=Total]),
         CannotCreate := CannotCreate ++ [Total]
       end
    end,
    Cannot := Cannot ++ [Dom=CannotCreate]
  end,
  println(cannot=Cannot),
  nl.

go4 => true.


%
% Print the solution
%
print_sol(N, X,Ops,Total) =>
  println(n=N),
  println(x=X),
  println(ops=Ops),
  Res = 0,
  foreach(I in 1..N-1)
    ops(Ops[I],Op),
    Res1 = apply(Op,X[I],X[I+1]),
    Res := Res + Res1,
    println([X[I],Op,X[I+1],=,Res1,cum=Res])
  end,
  println(total=Total),
  nl.

%
% Solve the problem
%
gen(N,Dom,Total, X,Ops) =>
  % println($gen(N,Dom,Total, X,Ops)),
  if var(X) then
    X = new_list(N),
    X :: Dom  
  end,

  % array of operations
  OpsVals = find_all(I,ops(I,_)),
  Ops = new_list(N-1),
  Ops :: OpsVals,
  
  Max = fd_max(Total),
  
  % temp array of the result of operation
  S = new_list(N-1),
  S :: -Max..Max,
  Total #= sum(S),
  foreach(I in 1..N-1)
    get_op(X[I], X[I+1], Ops[I], S[I])
  end,

  Vars = X ++ Ops ++ [Total],
  solve($[degree, updown],Vars).
  % solve($[],Vars).  


%
%  Res = A op B
%  
get_op(A, B, Op, Res) =>
  Op #= 1 #=> Res #= A + B,
  Op #= 2 #=> Res #= A - B,
  Op #= 3 #=> Res #= A * B,
  % restrict div to result in an integer
  Op #= 4 #=> (A #>= B #/\ A mod B #= 0 #/\ Res #= A div B). 
  % Op #= 5 #<=> Res #= A**B. % This don't work on large numbers, e,g, Devil's Word
  %  
  %  Op #= 5 #<=> Res #= A * A + B* B,
  %  % note: Using this alternative may generate weird Results
  %  Op #= 6 #<=> Res #= A mod B.

% for presentation
ops(1,+).
ops(2,-).
ops(3,*).
ops(4,div).
% ops(5,**). % This is experimental

%
% Create the ranges from a list of (sorted) numbers.
%
make_ranges(L) = Res =>
  Ranges = [],
  if L.len > 0 then
    Range = [L[1]]
  else
    Range = []
  end,
  
  foreach(I in 2..L.length)
     Li1 = L[I-1],
     Li  = L[I],
     if Li == Li1+1 then
        Range := Range ++ [Li]
     else
        if length(Range) > 0 then
           Ranges := Ranges ++ [Range]
        end,
        Range := [] ++ [Li]
     end
  end,
  % pickup the last range
  if length(Range) > 0 then
     Ranges := Ranges ++ [Range] 
  end,
  Res :=  join([get_range(R) : R in Ranges], ",").

get_range(R) = 
   cond(R.length == 1, 
      R.first().to_string(),
      min(R).to_string() ++ "-" ++ max(R).to_string()).