Calculating the worst case threshold length

worstCaseThresholdLength.js

'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))