• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?