SHARE
TWEET

Untitled

a guest Aug 22nd, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const nums = [7, 6, 5, 1];
  2. const operations = new Set(['+', '-', '*', '/']);
  3.  
  4. function permutations(nums, result = [], results = []) {
  5.   if (nums.length === 0) {
  6.     results.push([...result]);
  7.     return;
  8.   }
  9.  
  10.   for (let [index, num] of nums.entries()) {
  11.     result.push(num);
  12.     nums.splice(index, 1);
  13.     permutations(nums, result, results);
  14.     result.pop();
  15.     nums.splice(index, 0, num);
  16.   }
  17.  
  18.   return results;
  19. }
  20.  
  21. function combinations(operations, length, result = [], results = []) {
  22.   if (result.length === length) {
  23.     results.push([...result]);
  24.     return;
  25.   }
  26.  
  27.   for (let operation of operations) {
  28.     result.push(operation);
  29.     combinations(operations, length, result, results);
  30.     result.pop();
  31.   }
  32.  
  33.   return results;
  34. }
  35.  
  36. function solve(nums, operations, target) {
  37.   const results = [];
  38.   const operationCombinations = combinations(operations, 3);
  39.  
  40.   for (let numbers of permutations(nums)) {
  41.     for (let ops of operationCombinations) {
  42.       const tokens = [...numbers, ...ops];
  43.  
  44.       if (evalRPN(tokens) === target) {
  45.         results.push(tokens);
  46.       }
  47.     }
  48.   }
  49.  
  50.   return results;
  51. }
  52.  
  53. // Revers polish notation below
  54. const evalRPN = function(tokens) {
  55.   const stack = [];
  56.  
  57.   for (let token of tokens) {
  58.     if (!isOperation(token)) {
  59.       stack.push(Number(token));
  60.       continue;
  61.     }
  62.  
  63.     const b = stack.pop();
  64.     const a = stack.pop();
  65.     stack.push(evaluate(a, b, token));
  66.   }
  67.  
  68.   return stack.pop();
  69. };
  70.  
  71. const isOperation = token => operations.has(token);
  72.  
  73. function evaluate(a, b, operation) {
  74.   switch (operation) {
  75.     case '+':
  76.       return a + b;
  77.     case '-':
  78.       return a - b;
  79.     case '*':
  80.       return a * b;
  81.     case '/':
  82.       return a / b;
  83.   }
  84. }
  85.  
  86. function rpnToString(tokens) {
  87.   const stack = [];
  88.  
  89.   for (let token of tokens) {
  90.     if (!isOperation(token)) {
  91.       stack.push(token);
  92.       continue;
  93.     }
  94.  
  95.     const b = stack.pop();
  96.     const a = stack.pop();
  97.     stack.push(`(${a} ${token} ${b})`);
  98.   }
  99.  
  100.   // unwrap top level brace
  101.   return stack.pop().slice(1, -1);
  102. }
  103.  
  104. function main() {
  105.   const solutions = solve(nums, operations, 21);
  106.  
  107.   if (solutions.length === 0) {
  108.     console.log('No solutions found...');
  109.     return;
  110.   }
  111.  
  112.   console.log('Solutions:');
  113.   for (let solution of solutions) {
  114.     console.log('  ', rpnToString(solution));
  115.   }
  116. }
  117.  
  118. main();
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top