Skip to content

Instantly share code, notes, and snippets.

@maninak
Last active February 23, 2020 18:16
Show Gist options
  • Save maninak/c1df53e028fdfee2292021c479573b27 to your computer and use it in GitHub Desktop.
Save maninak/c1df53e028fdfee2292021c479573b27 to your computer and use it in GitHub Desktop.
Wanted to cut planks of wood. The size of the possible cuts was fixed. Wanted to utilize as much of the wooden planks as possible. Like any other engineer I took this to the editor :P .
// CONSTANTS
// =====================
const a = 210; // length of a possible cut
const b = 156; // length of another possible cut
const c = 138; // length of another possible cut
const K = 590; // length of the wood plank to be cut in pieces of the above lengths
// LOGIC
// =====================
let permutations = findAllWoodCuttingPermutations(a, b, c, K);
let optimalPermutation = findPermWithMinRemainder(permutations);
let utilization = parseFloat(((K - optimalPermutation.remainder) / K) * 100).toFixed(2);
console.log(`Optimal solution for cutting a wooden plank of length ${K} is to cut it into: \n`
+ `${optimalPermutation.x} pieces of length ${a} \n`
+ `${optimalPermutation.y} pieces of length ${b} \n`
+ `${optimalPermutation.z} pieces of length ${c} \n\n`
+ `This results in leftover length of ${optimalPermutation.remainder} length units`
+ `which is a utilization of ${utilization}%.`
);
// FUNCTION DECLARATIONS
// =====================
function findAllWoodCuttingPermutations(a, b, c, K) {
let permutations = [];
for (let x=0; x*a<=K; x++) {
for (let y=0; ((x*a)+(y*b))<=K; y++) {
for (let z=0; ((x*a)+(y*b)+(z*c))<=K; z++) {
let remainder = K - ((x*a) + (y*b) + (z*c));
if ((remainder <= K) && (remainder >= 0)) {
permutations.push({
'x': x,
'y': y,
'z': z,
'remainder': remainder,
});
}
}
}
}
return permutations;
}
function findPermWithMinRemainder(permutations) {
let minRemainder = Number.MAX_SAFE_INTEGER;
let permWithMinRemainder;
for (perm of permutations) {
if (perm.remainder <= minRemainder) {
minRemainder = perm.remainder;
permWithMinRemainder = perm;
}
}
return permWithMinRemainder;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment