Advertisement
Guest User

Untitled

a guest
Aug 22nd, 2019
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.25 KB | None | 0 0
  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();
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement