Skip to content

Instantly share code, notes, and snippets.

@jakearchibald

jakearchibald/1-exact-only.ts Secret

Last active July 8, 2021 08:30
Show Gist options
  • Star 7 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jakearchibald/a177a21ad4d1d901bd544deabcbc108f to your computer and use it in GitHub Desktop.
Save jakearchibald/a177a21ad4d1d901bd544deabcbc108f to your computer and use it in GitHub Desktop.
Download ZIP
Raw
1-exact-only.ts
/*
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');
Raw
1-include-nearest.ts
/*
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 •
edited

Running example: https://jsbin.com/yimejin/4/edit?js,console

@Teiem
Copy link

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

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