#!/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