Skip to content

Instantly share code, notes, and snippets.

@kellegous kellegous/puzzle.js
Created Sep 28, 2019

Embed
What would you like to do?
#!/usr/bin/env node
/**
* Solve the problem by guessing.
*
* @param {number} n
* @param {number} k
* @param {number} min
* @param {Int8Array} src
* @param {Int8Array} dst
* @param {() => void} fn
*/
function solve(n, k, min, src, dst, fn) {
if (src.length == 0) {
fn();
return;
}
// Each time we add k things, let's make sure that
// everything that remains is greater than the min
// of the previously selected items.
if (src.length < n && (src.length % k) == 0) {
if (Math.min(...src) < min) {
return;
}
min = n;
}
let tmp = new Int8Array(src.length - 1);
src.forEach((x) => {
dst[0] = x;
let j = 0;
src.forEach((y) => {
if (x != y) {
tmp[j] = y;
j++;
}
});
solve(n, k, Math.min(min, x), tmp, dst.subarray(1), fn);
});
}
/**
* Create a string to show the solution.
*
* @param {Int8Array} sol
*/
function format(sol) {
let ad = sol[1]*10 + sol[2],
bd = sol[4]*10 + sol[5],
cd = sol[7]*10 + sol[8];
return `${sol[0]}/${ad} + ${sol[3]}/${bd} + ${sol[6]}/${cd} = 1`;
}
/**
* Does this guess solve the problem?
*
* @param {Int8Array} sol
* @returns {boolean}
*/
function isSolution(sol) {
let ad = sol[1]*10 + sol[2],
bd = sol[4]*10 + sol[5],
cd = sol[7]*10 + sol[8],
s = sol[0]/ad + sol[3]/bd + sol[6]/cd;
return s > 0.9999 && s < 1.0001;
}
let n = 9,
k = 3,
src = new Int8Array(n).map((x, i) => {
return i + 1;
}),
dst = new Int8Array(n);
solve(n, k, n, src, dst, () => {
if (isSolution(dst)) {
console.log(format(dst));
}
});
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.