Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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();
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement