Instantly share code, notes, and snippets.

# jakearchibald/1-exact-only.ts Secret

Last active July 8, 2021 08:30
Star You must be signed in to star a gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* Countdown rules: Players select 6 number cards at random from two different decks. One deck has 25, 50, 75, 100. Another has the numbers 1-10, each twice. A random number, the target, is picked between 100-999. Players must find a way to the target using the number cards. Numbers can be added, deducted, multiplied, or divided. A card can only be used once in a given solution. Negative numbers are not allowed. Non-integers are not allowed. */ function pickRandom(arr: T[]): T { const index = Math.floor(Math.random() * arr.length); return arr.splice(index, 1)[0]; } const largeNums = [25, 50, 75, 100]; // 1-10, twice const smallNums = Array.from({ length: 20 }, (_, i) => (i % 10) + 1); const ops = ['+', '-', '*', '/']; // 100-999 const target = Math.floor(Math.random() * 900) + 100; const numbers = [ pickRandom(largeNums), pickRandom(largeNums), pickRandom(smallNums), pickRandom(smallNums), pickRandom(smallNums), pickRandom(smallNums), ]; console.log('Target', target); console.log('Numbers', numbers); let solutionSteps = Infinity; function solveBranch(numbers: number[], steps: number = 0): string | undefined { let branchSolution: string | undefined = undefined; // The solution is not allowed to dip into negative numbers at any point. // So. sort the numbers descending, to avoid negatives and fractions < 1. numbers.sort((a, b) => b - a); for (let i = 0; i < numbers.length; i++) { // We only need to look forward from the current position, because: // Order doesn't matter with addition. // Order matters with deduction, but the other way around would be < 0. // Order doesn't matter with multiplication. // Order matters with division, but the other way around would be < 1. for (let j = i + 1; j < numbers.length; j++) { for (const op of ops) { let subResult: number; switch (op) { case '+': subResult = numbers[i] + numbers[j]; break; case '-': subResult = numbers[i] - numbers[j]; // Zero doesn't help, and might land us with div-by-zero later. if (subResult === 0) continue; break; case '*': // Multiplying by 1 is a waste of a move. if (numbers[i] === 1 || numbers[j] === 1) continue; subResult = numbers[i] * numbers[j]; break; default: // '/' // Dividing by 1 is a waste of a move. // Fractions are not allowed. if (numbers[j] === 1 || numbers[i] % numbers[j]) continue; subResult = numbers[i] / numbers[j]; break; } if (subResult === target) { solutionSteps = steps + 1; return `\${numbers[i]} \${op} \${numbers[j]} = \${subResult}`; } // We've already found a simpler solution. Bail. if (steps + 1 === solutionSteps) return; // Create a new set of numbers, removing the cards we've used, // and replacing them with a made-up card of our intermediate result. const newNumbers = [ ...numbers.slice(0, i), ...numbers.slice(i + 1, j), ...numbers.slice(j + 1), subResult, ]; const subSolution = solveBranch(newNumbers, steps + 1); if (!subSolution) continue; // Document the solution, but a shorter solution may come up later. branchSolution = `\${numbers[i]} \${op} \${numbers[j]} = \${subResult}\n\${subSolution}`; } } } return branchSolution; } console.log(solveBranch(numbers) || 'Could not solve');
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* Countdown rules: Players select 6 number cards at random from two different decks. One deck has 25, 50, 75, 100. Another has the numbers 1-10, each twice. A random number, the target, is picked between 100-999. Players must find a way to the target using the number cards. Numbers can be added, deducted, multiplied, or divided. A card can only be used once in a given solution. Negative numbers are not allowed. Non-integers are not allowed. */ function pickRandom(arr: T[]): T { const index = Math.floor(Math.random() * arr.length); return arr.splice(index, 1)[0]; } const largeNums = [25, 50, 75, 100]; // 1-10, twice const smallNums = Array.from({ length: 20 }, (_, i) => (i % 10) + 1); const ops = ['+', '-', '*', '/']; // 100-999 const target = Math.floor(Math.random() * 900) + 100; const numbers = [ pickRandom(largeNums), pickRandom(largeNums), pickRandom(smallNums), pickRandom(smallNums), pickRandom(smallNums), pickRandom(smallNums), ]; console.log('Target', target); console.log('Numbers', numbers); let solutionDiff = Infinity; let currentSolution: string[] | undefined = undefined; function solveBranch(numbers: number[], steps: string[] = []): void { // The solution is not allowed to dip into negative numbers at any point. // So, sort the numbers descending, to avoid negatives and fractions < 1. numbers.sort((a, b) => b - a); for (let i = 0; i < numbers.length; i++) { // We only need to look forward from the current position, because: // Order doesn't matter with addition. // Order matters with deduction, but the other way around would be < 0. // Order doesn't matter with multiplication. // Order matters with division, but the other way around would be < 1. for (let j = i + 1; j < numbers.length; j++) { for (const op of ops) { let subResult: number; switch (op) { case '+': subResult = numbers[i] + numbers[j]; break; case '-': subResult = numbers[i] - numbers[j]; // Zero doesn't help, and might land us with div-by-zero later. if (subResult === 0) continue; break; case '*': // Multiplying by 1 is a waste of a move. if (numbers[i] === 1 || numbers[j] === 1) continue; subResult = numbers[i] * numbers[j]; break; default: // '/' // Dividing by 1 is a waste of a move. // Fractions are not allowed. if (numbers[j] === 1 || numbers[i] % numbers[j]) continue; subResult = numbers[i] / numbers[j]; break; } const diff = Math.abs(target - subResult); const step = `\${numbers[i]} \${op} \${numbers[j]} = \${subResult}`; if ( // A better solution, or our first solution diff < solutionDiff || // Or a same solution in fewer steps (diff === solutionDiff && steps.length + 1 < currentSolution!.length) ) { solutionDiff = diff; currentSolution = [...steps, step]; } // If we've got an exact answer, and we're about to perform more steps, bail. if (solutionDiff === 0 && steps.length + 1 >= currentSolution!.length) { return; } // Create a new set of numbers, removing the cards we've used, // and replacing them with a made-up card of our intermediate result. const newNumbers = [ ...numbers.slice(0, i), ...numbers.slice(i + 1, j), ...numbers.slice(j + 1), subResult, ]; solveBranch(newNumbers, [...steps, step]); } } } } solveBranch(numbers); console.log(currentSolution!.join('\n')); if (solutionDiff) console.log(solutionDiff, 'out');

### Teiem commented Jul 7, 2021 • edited

I hope this is the right place to post other solutions, here is mine

``````const randomInRange = (from, to) => Math.floor(Math.random() * (to - from)) + from;
const pickRandom = arr => arr.splice(Math.floor(Math.random() * arr.length), 1)[0];

const operations = [{
name: "+",
fn: (a, b) => a + b,
},
{
name: "-",
fn: (a, b) => a - b,
},
{
name: "*",
fn: (a, b) => a * b,
},
{
name: "/",
fn: (a, b) => a / b,
},
];

const target = randomInRange(100, 1000);

const smallNumbers = [25, 50, 75, 100];
const largeNumbers = [...Array(20).keys()].map(i => (i % 10) + 1);

const numbers = [
pickRandom(largeNumbers),
pickRandom(largeNumbers),
pickRandom(smallNumbers),
pickRandom(smallNumbers),
pickRandom(smallNumbers),
pickRandom(smallNumbers),
];

const solve = (numbers, target) => {
let permutations = numbers.map(permutation => ({ permutation, path: [permutation], remaining: numbers.filter(number => number !== permutation) }));

// every round we increase the number of numbers used by one, using the result of the previous round
// therefore the solution should be minimal
while (permutations[0].remaining.length !== 0) {

const foundTarget = permutations.find(({ permutation }) => target === permutation);
if (foundTarget) return foundTarget;

// we take the previous result, an operation and a not used number and calculate the new result
permutations = permutations.flatMap(({ permutation, path, remaining }) => remaining.flatMap(number => operations.map(({ fn, name }) => ({
permutation: fn(permutation, number),
path: [...path, name, number],
remaining: remaining.filter((numberA, i, self) => numberA !== number || self.indexOf(numberA) !== i),
}))))
.filter(({ permutation }) => permutation % 1 === 0 && permutation >= 0);

}
};

console.log(`looking for target \${target}`);
console.log(`\${new Intl.ListFormat().format(numbers.map(String))} are given`);

const res = solve(numbers, target);

if (res) {
console.log(`\none of the shortest calculations is \${res.path.join(" ")}`);

} else {
console.log("\nthere is no solution");

}
``````

### jakearchibald commented Jul 7, 2021

Does this work if the set of numbers contains duplicates? Looking at those filters, it feels like it might remove too many.

### Teiem commented Jul 8, 2021

True, `remaining: remaining.filter(numberA => numberA !== number),` removes every number, event though it should only remove the first one. I fixed it by checking if the number to remove is the first occurrence in the array `remaining: remaining.filter((numberA, i, self) => numberA !== number || self.indexOf(numberA) !== i),`.