/* 

  Equation that evaluates to n #2 in Picat v3.

  This is a port of Jan Wielemaker's Prolog version in:
  https://swish.swi-prolog.org/p/PIrHlciG.swinb
  ("Trying a smarter generator")

  that solves the problem in 

  "Fun - Equation that evaluates to n"
  https://swi-prolog.discourse.group/t/fun-equation-that-evaluates-to-n/2704
  """
  Commercial user on IRC asked a really interesting question.

  They are doing some awful reverse engineering job on an SQL DB.

  Given a list of reals List, and a real Target, find an equation using the 
  four basic operations +,-, *, / that makes the equation true.

  Each element may be used 0 or 1 times.

  Doing this naively quickly becomes intractable.

  There is no domain for the numbers, they could be anything

  It’s acceptable to use some ‘almost equals’ to deal with fp precision.

  My first reaction was ‘oh, that’s easy’ and dashed this off, but it’s slow.
  """

  Cf equation_that_evaluates_to_n_v3.pi for (a port of) Anne Ogborn's 
  approach.

  Note: list_formula/2 might give the same solution more than once.

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

*/

import util.


main => go.

go ?=>
  List = 1..6,
  Target = 27,
  list_formula(List, Formula),
  Formula =:= Target,
  println(Formula),
  fail,
  nl.

go => true.


go2 ?=>
  List = [2.1,8.3,2.5,0.4],
  Target = 13.3,
  All = findall(Formula,(list_formula(List, Formula),Formula=:=Target)),
  foreach(A in All)
    E is A,
    println(A=E)
  end,
  write(len=All.len),nl,
  nl.
             
go2 => true.


% random instances
go3 ?=>
  garbage_collect(200_000_000),
  N = 5,
  MaxValue = 20,
  MaxTarget = 100,
  _ = random2(),
  List = [1+random() mod MaxValue : _ in 1..N].sort_remove_dups,
  println(list=List),
  Target = 1+random() mod MaxTarget,
  println(target=Target),
  list_formula(List, Formula),
  % println(test=Formula),  
  Formula =:= Target,
  println(Formula),
  fail,

  nl.

go3 => true.

% From https://swish.swi-prolog.org/p/PIrHlciG.swinb
% hakank: I changed the spelling from list_fomula to list_formula)

% table
list_formula(List, Formula) :-
    select2(A1, A2, List, List1),
    formula(A1, A2, F1),
    (   Formula = F1
    ;   list_formula([F1|List1], Formula)
    ).

select2(A1, A2, [A1|L1], Rest) :-
    select(A2, L1, Rest).
select2(A1, A2, [H|L1], [H|Rest]) :-
    select2(A1, A2, L1, Rest).

formula(A1, A2, A1+A2).
formula(A1, A2, A1-A2).
formula(A1, A2, A2-A1).
formula(A1, A2, A1*A2).
formula(A1, A2, A1/A2) :- A2 =\= 0.
formula(A1, A2, A2/A1) :- A1 =\= 0.