You know how when you first learn algebra you're given an equation like "3 + x = 8", and you have to find x? findexpr solves a related problem, one in which the operators are the unknowns. That is, given "3 op 5 = 8" you have to solve for op and find "+". Let's try that:

$ echo '3 5 => 8' | findexpr
unary ops: - abs sgn
binary ops: + * - / ^ mod max min
constants: 1
allow reps: yes
require all: no
solutions: 1
columns: a b => f1
3 5 => 8

f1(a,b) = a + b

Ta da! Of course, findexpr is designed to solve much trickier problems. For example, can you find a single function f such that f(2, 3) = 4, f(3, 4) = 2, and f(4, 2) = 3? findexpr can:

$ echo -e '2 3 => 4\n3 4 => 2\n4 2 => 3' | findexpr
unary ops: - abs sgn
binary ops: + * - / ^ mod max min
constants: 1
allow reps: yes
require all: no
solutions: 1
columns: a b => f1
2 3 => 4
3 4 => 2
4 2 => 3

f1(a,b) = floor((b + 1) / ((a - 1) mod b))

findexpr provides control over the set of allowable operators, the set of constants that can be used, whether each input can be used more than once or not at all, and the number of alternative solutions desired.

Alas findexpr has a few limitations:

1. It works only with integers, not floating-point numbers.

2. It does not simplify its output (i.e., there are often too many parentheses).

3. It can be sloooooooooow.

The slowness comes from findexpr using a brute-force algorithm to solve for the mystery function. To make up for that, the findexpr implementation is multithreaded so the more CPU cores you have, the faster it'll run.

findexpr is written in Haskell and has been tested only with the Glasgow Haskell Compiler. You'll need that to compile the code. Currently, the build process consists of the usual

$ make
$ make install

and yes, you can override prefix and bindir on the make install command line. Some day I'll switch over to Cabal as the build tool, but Make works fine for now.

Scott Pakin, [email protected]