Skip to content

Instantly share code, notes, and snippets.

@jakearchibald

jakearchibald/1-exact-only.ts Secret

Last active May 1, 2020
Embed
What would you like to do?
/*
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<T>(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');
/*
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<T>(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');
@jakearchibald

This comment has been minimized.

Copy link
Owner Author

@jakearchibald jakearchibald commented Apr 29, 2020

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.