Given 4 digits [7, 6, 5, 1]. Find an expression(s) containing all those digits (once each) and
arithmetical operations: +, -, *, / and parentheses that evaluates to 21.
Example of possible expression: (7+6)*(5+1)
References:
Last active
August 11, 2019 00:06
-
-
Save ValeriiVasin/41bc2c3e83558a4792b5bbfb0ce6be5e to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const nums = [7, 6, 5, 1]; | |
| const operations = new Set(['+', '-', '*', '/']); | |
| function permutations(nums, result = [], results = []) { | |
| if (nums.length === 0) { | |
| results.push([...result]); | |
| return; | |
| } | |
| for (let [index, num] of nums.entries()) { | |
| result.push(num); | |
| nums.splice(index, 1); | |
| permutations(nums, result, results); | |
| result.pop(); | |
| nums.splice(index, 0, num); | |
| } | |
| return results; | |
| } | |
| function combinations(operations, length, result = [], results = []) { | |
| if (result.length === length) { | |
| results.push([...result]); | |
| return; | |
| } | |
| for (let operation of operations) { | |
| result.push(operation); | |
| combinations(operations, length, result, results); | |
| result.pop(); | |
| } | |
| return results; | |
| } | |
| function solve(nums, operations, target) { | |
| const results = []; | |
| const operationCombinations = combinations(operations, 3); | |
| for (let numbers of permutations(nums)) { | |
| for (let ops of operationCombinations) { | |
| const tokens = [...numbers, ...ops]; | |
| if (evalRPN(tokens) === target) { | |
| results.push(tokens); | |
| } | |
| } | |
| } | |
| return results; | |
| } | |
| // Revers polish notation below | |
| const evalRPN = function(tokens) { | |
| const stack = []; | |
| for (let token of tokens) { | |
| if (!isOperation(token)) { | |
| stack.push(Number(token)); | |
| continue; | |
| } | |
| const b = stack.pop(); | |
| const a = stack.pop(); | |
| stack.push(evaluate(a, b, token)); | |
| } | |
| return stack.pop(); | |
| }; | |
| const isOperation = token => operations.has(token); | |
| function evaluate(a, b, operation) { | |
| switch (operation) { | |
| case '+': | |
| return a + b; | |
| case '-': | |
| return a - b; | |
| case '*': | |
| return a * b; | |
| case '/': | |
| return a / b; | |
| } | |
| } | |
| function rpnToString(tokens) { | |
| const stack = []; | |
| for (let token of tokens) { | |
| if (!isOperation(token)) { | |
| stack.push(token); | |
| continue; | |
| } | |
| const b = stack.pop(); | |
| const a = stack.pop(); | |
| stack.push(`(${a} ${token} ${b})`); | |
| } | |
| // unwrap top level brace | |
| return stack.pop().slice(1, -1); | |
| } | |
| function main() { | |
| const solutions = solve(nums, operations, 21); | |
| if (solutions.length === 0) { | |
| console.log('No solutions found...'); | |
| return; | |
| } | |
| console.log('Solutions:'); | |
| for (let solution of solutions) { | |
| console.log(' ', rpnToString(solution)); | |
| } | |
| } | |
| main(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment