# Untitled

a guest
Aug 22nd, 2019
91
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