Is there a way to get the operations needed to get from some input to a specific output? For example, I have some input 1 and output 3. I also have a couple of operations, F(x)=x 1 and G(x)=x-1. How would I create a program that would find that the solution of F(F(x))

Another example, with operations of F(x)=-x and G(x)=-2x. With an input of 1 and an output of 2. The solution requires F(x) to be used but F(x) increases the difference between the input and output.

Note: Operations may not be linear and may include some variable constant.

CodePudding user response：

Your description of the problem is pretty lacunary. Anyway, I guess that it can be solved by brute force:

• maintain a set of values "reached" so far, initially empty, and a set of "new" values, initially containing the starting value, {1}.

• apply F to the "new" set, here giving {2}

• apply G to the "new" set, here giving {0}

• take the union of the images, minus the "reached" set to get a new "new" set, (giving {0,2}) and add the images to the "reached" set (giving {0,1,2}).

At the next iteration, you will get "new" {-1,3} and "reached" {-1,0,1,2,3}. And so on. Obviously, you stop when you reach the target value.

To obtain the path that led to the final value, you can tag every element with a "parent", i.e. another element that led to it by F or G (and a flag telling which). E.g., 2 = F(1).

For the second example,

{1}, {}
{-2,-1}, {-2,-1,1}
{4}, {-2,-1,1,2,4}
{-4,-8}, {-8,-2,-1,1,2,4}
{8}, {-8,-2,-1,1,2,4,8}
...