Fun - Equation that evaluates to n

Help!
1

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.

equation_matching_target(List, Target, Eq) :-
    permutation(List, RList),
    between(1, 10, MaxDepth),
    equation(MaxDepth, RList, Eq, _),
    catch(Target is Eq,
          _,
          fail).

%! equation(+InList:list, -Eq:acyclic, -OutList) is nondet
%
% @arg InList list of unused numbers
% @arg Eq    list of
equation(0, _, _, _) :- !, fail.
equation(_, [H | T], H, T).
equation(N, In, Eq, Out) :-
    succ(NN, N),
    member(Op, [ '+', '-', '*', '/']),
    Eq =.. [Op, A, B],
    equation(NN, In, A, Mid),
    equation(NN, Mid, B, Out).
3 Likes