Here's a computer science problem I'm trying to solve:
Given an expression tree:
type expr =
| GCD of expr * expr
| LCM of expr * expr
| Number of int
Write a function insert: expr -> int -> int where insert e n outputs smallest number x which, when plugged into expr instead of zeroes (we exchange every occurence of Number 0 to Number x) gives n when evaluating the expression, for example:
insert (LCM(LCM(Number 2, Numer 0), GCM(Number 0, Number 49)) 42 = 21
The function should return 0 when reaching n is not possible.
And that last sentence gives me a headache. I've written 'brute-force' algorithm (for every integer j from 1 to answer we go through the tree setting all zeroes to j and then we traverse the tree again evaluating the expression, and when we find the answer we output it). But I don't have a clue where should I stop executing it - what is the condition under which we are guaranteed that there is no solution?
Also - is there a more efficient algorithm or my 'brute-force' algorithm is all that is possible?