Skip to content

Instantly share code, notes, and snippets.

@jakearchibald
Last active Jul 8, 2021
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
Copy link
Author

jakearchibald commented Apr 29, 2020

@Teiem
Copy link

Teiem commented Jul 7, 2021

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
Copy link
Author

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
Copy link

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),.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment