/* 

  Countdown problem in Picat.

  From Ruby Quiz #7
  http://www.rubyquiz.com/quiz7.html
  """
  One of the longest-running quiz shows on UK TV is called Countdown, 
  and has a "numbers round". There are some cards laid face down in 
  front of the host - the top row contains 'large' numbers (from the 
  set 25, 50, 75, 100), and the rest are 'small' (1 to 10). Six cards 
  are picked and displayed: the choice is made by one of the contestants, 
  who typically will ask for one large number and five small ones.
  
  Next, a machine called "Cecil" picks a target number between 100 and 
  999 at random. The contestants then have 30 seconds to find a way of 
  combining the source numbers using the normal arithmetic operators 
  (+, -, *, /) to make the target number, or to get as close as possible.
  
  Each source card can be used no more than once. The same applies to any 
  intermediate results, although of course you don't have to explicitly 
  show the intermediate results.
  
  Example: source 100 5 5 2 6 8, target 522
  
  100 * 5 = 500
  5 + 6 = 11
  11 * 2 = 22
  500 + 22 = 522
  
  or more succinctly, (5*100)+((5+6)*2) = 522
  
  Another solution is (100+6)*5-8 = 522
  
  Normal arithmetic rules apply, and in particular you are not allowed to 
  use integer rounding. That is, 7 divided by 3 is 2 1/3, not 2.
  
  The quiz is to write a program which will accept one target number and 
  a list of source numbers, and generate a solution which calculates 
  the target or a number as close to the target as possible.
  """

  This is a little different approach than countdown_cp.pi 
  (and countdown2.pi):
   - permutate the numbers
   - select some subset of the operators
   - check solution with 
        parse_term/1

  However this program requires that we use all numbers exactly once,
  and it allows divisioon by anything (i.e. float division).

  Some features:
  * tabling 
    countdown_t/4: tables the solutions to reduce duplicate solutions.
    E.g tabling reduces the problem Target = 24, numbers=[4,4,4,4]
    from 72 solutions to just 3 solutions
      4+4+4*4
      4+4*4+4
      4*4+4+4
    For instances with unique numbers, tabling has no such effects.

  * PermuteNumbers: if true then all the permutation of the numbers 
    are tested. If false the numbers are only tested in the order   
    of the list.

    For example numbers 2..5 and targets 1..120 give only these
    solutions:
      target = 5 = [2*3+4-5] = len = 1
      target = 6 = [2+3-4+5] = len = 1
      target = 7 = [2*3-4+5] = len = 1
      target = 8 = [2-3+4+5] = len = 1
      target = 9 = [2+3*4-5] = len = 1
      target = 14 = [2+3+4+5] = len = 1
      target = 15 = [2*3+4+5] = len = 1
      target = 19 = [2+3*4+5,2-3+4*5,2*3*4-5] = len = 3
      target = 25 = [2+3+4*5] = len = 1
      target = 26 = [2*3+4*5] = len = 1
      target = 29 = [2*3*4+5] = len = 1
      target = 62 = [2+3*4*5] = len = 1
      target = 120 = [2*3*4*5] = len = 1

  There might be quite a lot of redundancy in the solutions. 
  For example for numbers 2..4 and target 24 there are 6 solutions (i.e. 4!),
  all the same apart from the order of the numbers:
    2*3*4
    2*4*3
    3*2*4       
    3*4*2
    4*2*3
    4*3*2
  (This is not reduced by tabling in countdown_t/4.)

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

*/

import util.

main => go.

go ?=>
  Map = get_global_map(),
  Map.put(count,0),
  
  % Numbers = [4, 50, 10, 100, 8, 2],
  % Target = 464,

  Numbers = [100, 5, 5, 2, 6, 8],
  Target = 522,


  % Target = 12,  
  % Numbers = [1,2,3,4,5,6],

  % Target = 25,  
  % Numbers = 1..5,

  println(numbers=Numbers),
  println(target=Target),

  PermuteNumbers=true,
  countdown(Numbers,Target,PermuteNumbers,L),
  Map.put(count,Map.get(count)+1),
  println(L.flatten),
  flush(stdout),
  fail,
  nl.
go => println(count=get_global_map().get(count)).


go2 ?=>
  member(Target,1..120),
  % Target = 14,
  % println(target=Target),
  % Target = 24,
  % Numbers = [4,4,4,4],
  Numbers = [2,3,4,5],
  PermuteNumbers=true,
  All=findall(L,countdown(Numbers,Target,PermuteNumbers,L)),
  if All.len > 0 then 
     println(target=Target=[L.flatten : L in All]=len=All.len)
     
  end,
  flush(stdout),
  fail,
  nl.
go2 => true.

merge([N],[], L,L2) :- L2 = L ++ [N].
merge([N|Ns],[Op|Ops], L0,[N,Op|L]) :-
  merge(Ns,Ops, L0,L).

countdown(Numbers,Target,PermuteNumbers,L) :-
  Len = Numbers.len,
  NumbersS = [I.to_string : I in Numbers],
  Operators = ["+","-","*","/"],
  if PermuteNumbers then
    permutation(NumbersS,Ns),
    subsets(Len-1,Operators,Ops),
    merge(Ns,Ops,[],L)
  else
    subsets(Len-1,Operators,Ops),
    merge(NumbersS,Ops,[],L)
  end,
  % L = zip(Ns,Ops).map(to_list).flatten ++ [Ns[Len]], % slower
  L2 = L.flatten,
  PT = parse_term(L2).apply,
  PT*1.0 == Target*1.0.

%
% Using tabling reduces the problem
%   Target = 24, numbers=[4,4,4,4]
% from 72 solutions to just 3 solutions
%   4+4+4*4
%   4+4*4+4
%   4*4+4+4
% 
table
countdown_t(Numbers,Target,PermuteNumbers,L) :-
  countdown(Numbers,Target,PermuteNumbers,L).

subset([],_).
subset([H|T],Y) :-
  member(H,Y),subset(T,Y).

%  all(N,L,X). All possible pairs with elements from [a,b,c,d]:
subsets(N,L,X) :-
  X = new_list(N),
  subset(X,L).