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
2

Surely a nice challenge. As is, Prolog merely provides a way to write the brute force solution quickly. Without anything else and floats rather than integers I have little clue whether it is possible to do better. I guess you need some divide and conquer, i.e. finding some key numbers and an operation that gets you close, remove the used numbers and try the same with the remaining numbers on how far you are off. Random starts and trying to fix these may also work. Prolog is still a nice language for coding such attempts quickly :slight_smile:

1 Like
4

Depending on what the real problem is, there might be other angles for attack. Like,

  • are they really reverse engineering?
  • What else do they know about the system?
  • Can they test/refute certain assumptions?
  • Is there a possibility for a side-channel attack?

and so on. Because from what you have in the question, it really sounds that brute-forcing is the only approach, but maybe there are additional constraints that we don’t know about?

(when I say “brute forcing is the only approach” I mean that otherwise you won’t get the one true answer. But with floats “almost equal” and so on this really sounds like there is some information we are missing…)

A side note: are the numbers really REALS or floating point? I am asking because at least Oracle uses a somewhat unusual representation for numbers (well… it makes sense for currency), and you need to specifically ask it to use proper floats or doubles (see here).

1 Like
7

Can this be treated as bipartite graph problem, first generating the form of the equation then matching numbers to unbound variables?

8

Cute problem!

There is a big speed up if one add tabling to equation/4, i.e.

:- table equation/4. % <---
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).

Running the following (time(go).) show all 864 solutions in 0.03s on my machine.

go :-
        List = [2.1,8.3,2.5,0.4],
        Target = 13.3,
        equation_matching_target(List, Target, Eq),
        write(Eq),
        nl,
        fail,
        nl.

go.
3 Likes
9

See https://swish.swi-prolog.org/p/PIrHlciG.swinb

Note that the answers are mostly/all (?) variations of 2.1+8.3+(2.5+0.4), reordering the arguments and changing the nesting. I think it should be possible to avoid that using a smarter generator algorithm.

1 Like
10

Good point.

The example was perhaps not that good. I just added some “random float numbers” for the example.

Using equation_matching_target([1,2,3,4], 10, Eq) give some more variety, but it’s integers.

Perhaps Annie has some real example that we can evaluate…

11

I added an alternative using a new generator to the SWISH notebook. That works a lot better, but still not perfect. Can do lists up to 6 without tabling in a reasonable time (24M formulas). There should be more trivial optimizations …

2 Likes
13

Brilliant!

14

Extremely impressive speedup!

1 Like