Algorithm for finding a solution using basic operations

Question

I need help creating an algorithm. I am currently developing something for a class that I accept.

Given 4 numbers, I need to find the entire (or at least the first) combination of 4 numbers, using the basic operations (+ - * /) to make a specific answer.

For example, if the numbers [1,2,3,4] are given. and I have to answer 12. I see (without a program) that (2-1) * 3 * 4 = 12

But for more complex numbers, it can be harder to solve just thinking about it. Therefore, I need a program that will help me find at least one possible combination to solve the problem .

Please note that in the 4 numbers indicated, numbers can be repeated, but each number can be used only once. For example, a set of 4 may be [2,3,3,4]. But in this set, 2 and 4 cannot be used more than once.

Initially, I had a power-search plan to find all possible combinations / orders from every four numbers, and then repeat all the operations. Later I realized that this would not work, since it does not take into account operations like (1-2) * (3 + 4).

So I was wondering if anyone has an idea on how I can solve this problem?

Please keep in mind that I'm still fairly new to programming, so I don’t understand some of the more complex terms and functions. But I can do nice things like loops and arrays.

Answer 1

In fact, there are not many combinations to check, because the number of priority cases is limited to 5:
((a:b):c):d
(a:b):(c:d)
(a:(b:c)):d
a:((b:c):d)
a:(b:(c:d))
therefore, with 24 permutations and 3 options out of 4 possible operators, which gives 7680 combinations. And many of these combinations are really identical, since priority is not important in such cases as:
a+b+c+d
a+b+cd
a*b*c*d
a*b*c/d

Run the code snippet to see a simple loop-based algorithm that tests these 7680 combinations in action. For the case 1:2:3:4=12 there is an amazing amount of solutions.

 function findArithmetic(target, numbers) { // PUT THE ARITHMETIC FUNCTIONS IN AN ARRAY, SO WE CAN ITERATE OVER THEM function sum(a, b) {return a + b} function dif(a, b) {return a - b} function prd(a, b) {return a * b} function div(a, b) {return a / b} var func = [sum, dif, prd, div]; // DEFINE THE ORDER OF THE CALCULATIONS FOR THE 5 PRECEDENCE CASES var prec = [[0, 1, 4, 2, 5, 3], // 0,1,2,3 are the four numbers [0, 1, 2, 3, 4, 5], // 4 is the result of the 1st calculation [1, 2, 0, 4, 5, 3], // 5 is the result of the 2nd calculation [1, 2, 4, 3, 0, 5], // so here, do 1:2, then result1:3, then 0:result2 [2, 3, 1, 4, 0, 5]]; // and here, do 2:3, then 1:result1, then 0:result2 // FIND ALL PERMUTATIONS OF THE NUMBERS AND STORE THEM IN ARRAY "NUMS" var nums = []; for (var a = 0; a < 4; a++) { for (var b = 0; b < 4; b++) { if (a == b) continue; for (var c = 0; c < 4; c++) { if (a == c || b == c) continue; for (var d = 0; d < 4; d++) { if (a == d || b == d || c == d) continue; nums.push([numbers[a], numbers[b], numbers[c], numbers[d]]); } } } } // NOW GET DOWN TO BUSINESS var solutions = []; // ITERATE OVER ALL 24 PERMUTATIONS for (var n = 0; n < nums.length; n++) { // ITERATE OVER ALL 5 PRECEDENCE CASES for (var p = 0; p < 5; p++) { // ITERATE OVER THE 4 OPERATORS FOR THE FIRST CALCULATION for (var i = 0; i < 4; i++) { // ITERATE OVER THE 4 OPERATORS FOR THE SECOND CALCULATION for (var j = 0; j < 4; j++) { // ITERATE OVER THE 4 OPERATORS FOR THE THIRD CALCULATION for (var k = 0; k < 4; k++) { // DO THE CALCULATIONS nums[n][4] = func[i](nums[n][prec[p][0]], nums[n][prec[p][1]]); nums[n][5] = func[j](nums[n][prec[p][2]], nums[n][prec[p][3]]); var result = func[k](nums[n][prec[p][4]], nums[n][prec[p][5]]); // IF THE RESULT IS CORRECT, MAKE A STRING AND ADD TO SOLUTIONS if (result == target) { solutions.push(makeString(n, p, i, j, k)); } } } } } } return solutions; // TURN THE RESULT INTO A PRESENTABLE STRING // this is a bit fiddly, because in each precedence case, the calculations are done in a different order function makeString(n, p, i, j, k) { // CHOOSE THE RIGHT STRING TEMPLATE, BASED ON THE PREFERENCE CASE var str = ["((aAb)Bc)Cd", "(aAb)B(cCd)", "(aA(bBc))Cd", "aA((bBc)Cd)", "aA(bB(cCd))"][p]; // REPLACE "a", "b", "c", AND "d" WITH THE NUMBERS for (var c = 0; c < 4; c++) str = str.replace(["a","b","c","d"][c], nums[n][c]); // REPLACE "A", "B" AND "C" WITH THE OPERATORS, BASED ON EXECUTION ORDER IN PREFERENCE CASE var order = [["A","B","C"], ["A","C","B"], ["B","A","C"], ["B","C","A"], ["C","B","A"]]; for (var c = 0; c < 3; c++) str = str.replace(order[p][c], ["+","-","*","/"][[i,j,k][c]]); return str + "=" + target; } } // RUN THE FUNCTION AND DISPLAY THE RESULTS IN THE CONSOLE var sol = findArithmetic(12, [1,2,3,4]); document.write(sol.length + " solutions found:<BR><PRE>"); for (var s in sol) document.write(sol[s] + "<BR>"); 

This is a simpler solution without an array of priorities. He has calculations for five cases of priority, written out separately. Typically, programmers consider this a fuzzy solution, because it violates the “don't repeat yourself” rule; however, in this case, the code is much easier to understand, and it greatly simplifies the display of results, so it seems to me that it makes sense to do it this way.

This version returns only one solution for the permutation of numbers and a combination of operators, because solutions with different parentheses, such as (a*b)+(cd) and ((a*b)+c)-d , are actually just duplicate. (This is what the continue statement after each calculation for.)

 function findArithmetic(target, numbers) { // PUT THE ARITHMETIC FUNCTIONS IN AN ARRAY, SO WE CAN ITERATE OVER THEM function sum(a, b) {return a + b} function dif(a, b) {return a - b} function prd(a, b) {return a * b} function div(a, b) {return a / b} var func = [sum, dif, prd, div]; // FIND ALL PERMUTATIONS OF THE NUMBERS AND STORE THEM IN ARRAY "NUMS" var nums = []; for (var a = 0; a < 4; a++) { for (var b = 0; b < 4; b++) { if (a == b) continue; for (var c = 0; c < 4; c++) { if (a == c || b == c) continue; for (var d = 0; d < 4; d++) { if (a == d || b == d || c == d) continue; nums.push([numbers[a], numbers[b], numbers[c], numbers[d]]); } } } } // NOW GET DOWN TO BUSINESS var solutions = []; var op = ["+","-","*","/"]; // ITERATE OVER ALL 24 PERMUTATIONS for (var n = 0; n < nums.length; n++) { var a = nums[n][0], b = nums[n][1], c = nums[n][2], d = nums[n][3]; // ITERATE OVER THE 4 OPERATORS FOR THE FIRST CALCULATION for (var i = 0; i < 4; i++) { // ITERATE OVER THE 4 OPERATORS FOR THE SECOND CALCULATION for (var j = 0; j < 4; j++) { // ITERATE OVER THE 4 OPERATORS FOR THE THIRD CALCULATION for (var k = 0; k < 4; k++) { // CHECK PRECEDENCE CASE 1: ((a:b):c):d if (target == func[k](func[j](func[i](a, b), c), d)) { solutions.push("((" + a + op[i] + b + ")" + op[j] + c + ")" + op[k] + d + "=" + target); continue; } // CHECK PRECEDENCE CASE 2: (a:b):(c:d) if (target == func[j](func[i](a, b), func[k](c, d))) { solutions.push("(" + a + op[i] + b + ")" + op[j] + "(" + c + op[k] + d + ")=" + target); continue; } // CHECK PRECEDENCE CASE 3: (a:(b:c)):d if (target == func[k](func[i](a, func[j](b, c)), d)) { solutions.push("(" + a + op[i] + "(" + b + op[j] + c + "))" + op[k] + d + "=" + target); continue; } // CHECK PRECEDENCE CASE 4: a:((b:c):d) if (target == func[i](a, func[k](func[j](b, c), d))) { solutions.push(a + op[i] + "((" + b + op[j] + c + ")" + op[k] + d + ")=" + target); continue; } // CHECK PRECEDENCE CASE 5: a:(b:(c:d)) if (target == func[i](a, func[j](b, func[k](c, d)))) { solutions.push(a + op[i] + "(" + b + op[j] + "(" + c + op[k] + d + "))=" + target); } } } } } return solutions; } // RUN THE FUNCTION AND DISPLAY THE RESULTS IN THE CONSOLE var sol = findArithmetic(2, [4,5,6,12]); document.write(sol.length + " solutions found:<BR><PRE>"); for (var s in sol) document.write(sol[s] + "<BR>"); 

Answer 2

You are looking for binary expression trees with 4 sheets. There is always a top level node (+, *, -, / in your case). For this top level node, arrange your search by the number of sheets to the left of the top level node, which should be a number in the range from 1 to 3. There is a natural recursive solution, because for example, if the left side has three sheets, then it itself is binary expression tree with three leaves. You really don't need to use tree data structures - you can use strings with full brackets (for example, for example "(((1 + 2) * 3) / 4)" for a tree, the top of the node is "/" and the left side of which is tree "((1 + 2) * 3)", the right side of which is sheet 4).