Last active
March 23, 2016 23:59
-
-
Save emschwartz/844b088c51367b51aff1 to your computer and use it in GitHub Desktop.
Calculating the worst case threshold length
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
'use strict' | |
const threshold = process.env.THRESHOLD ? parseInt(process.env.THRESHOLD) : 150 | |
const numSubconditions = process.env.NUM_SUBCONDITIONS ? parseInt(process.env.NUM_SUBCONDITIONS) : 10 | |
const minWeight = process.env.MIN_WEIGHT ? parseInt(process.env.MIN_WEIGHT) : 1 | |
const maxWeight = process.env.MAX_WEIGHT ? parseInt(process.env.MAX_WEIGHT) : 256 | |
const minLength = process.env.MIN_LENGTH ? parseInt(process.env.MIN_LENGTH) : 1 | |
const maxLength = process.env.MAX_LENGTH ? parseInt(process.env.MAX_LENGTH) : 1024 | |
function getRandomIntInclusive(min, max) { | |
return Math.floor(Math.random() * (max - min + 1)) + min; | |
} | |
const subconditions = [] | |
for (let t = 0; t < numSubconditions; t++) { | |
subconditions.push({ | |
weight: getRandomIntInclusive(minWeight, maxWeight), | |
length: getRandomIntInclusive(minLength, maxLength) | |
}) | |
} | |
// This function will either return the worst case total length | |
// or -1 if there is no combination of subconditions that will yield the threshold | |
function worstCaseLength (thresholdRemaining, nextSubconditions, totalLength) { | |
if (thresholdRemaining <= 0) { | |
return totalLength | |
} else if (nextSubconditions.length > 0) { | |
const nextCondition = nextSubconditions[0] | |
return Math.max( | |
// Try adding next subcondition | |
worstCaseLength( | |
thresholdRemaining - nextCondition.weight, | |
nextSubconditions.slice(1), | |
totalLength + nextCondition.length), | |
// Try not adding next one | |
worstCaseLength( | |
thresholdRemaining, | |
nextSubconditions.slice(1), | |
totalLength)) | |
} else { | |
// Ran out of conditions, no solution for this branch of the tree | |
return -1 | |
} | |
} | |
function highestWeightedFirst (conditions) { | |
let newArray = conditions.slice() | |
newArray.sort(function (a, b) { | |
return b.weight - a.weight | |
}) | |
return newArray | |
} | |
console.log('Subconditions:', highestWeightedFirst(subconditions)) | |
console.log('Worst case length:', worstCaseLength(threshold, highestWeightedFirst(subconditions), 0)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment