Calculates which plates to put on barbell to get desired weight

barbellPlatesCalculator.ts

// example calculator functions
const barbellTotal = (plateWeights: Weight[]) => barbellWeight + 2 * plateWeights.reduce((a, b) => a + b, 0);
const singleDumbbellTotal = (plateWeights: Weight[]) => dumbbellWeight + 2 * plateWeights.reduce((a, b) => a + b, 0);
const doubleDumbbellTotal = (plateWeights: Weight[]) => 2 * singleDumbbellTotal(plateWeights);

const availableWeights: PlatesInventory = new Map([
  // [weight, total number of plates available]
  // NOTE: put number of plates -> two for each pair
  [20, 2],
  [12.5, 2],
  [10, 2],
  [7.5, 2],
  [6, 2],
  [5, 8],
  [2.5, 6],
  [1.25, 8],
]);
const barbellWeight = 8; // kg
const dumbbellWeight = 1.5; // kg

// CHANGE WEIGHT HERE
const targetWeight = 72.5;
printPlatesToPut(barbellTotal);

function printPlatesToPut(totalWeightFormula: TotalWeightFn) {
  const [foundPlates, gap] = findPlatesBFS(targetWeight, barbellWeight, availableWeights, totalWeightFormula);
  if (gap > 0) {
    const reachableWeight = targetWeight - gap;
    console.log(`Couldn't find plates for ${targetWeight} kg, closest match is ${reachableWeight} kg.`)
  }
  console.log('Plates to put: ' + foundPlates.map(it => `${it} kg`).join(', '));
}

type Weight = number;
type TotalWeightFn = (plateWeights: Weight[]) => Weight;
type PlatesInventory = Map<Weight, number>;

function findPlatesBFS(targetWeight: Weight, nonPlateWeight: Weight, weights: PlatesInventory, calcTotalWeight: TotalWeightFn): [plates: Weight[], gap: number] {
  let bestPlateWeights: Weight[] = [];
  let bestLength = -1; // best number of plates, lower=better

  const hasEnoughWeight = () => {
    let sum = nonPlateWeight;
    for (const [plateWeight, numPlates] of weights) {
      sum += plateWeight * numPlates;
    }
    return sum > targetWeight;
  }
  if (!hasEnoughWeight()) {
    throw new Error("Not enough plates available to reach target weight");
  }

  if (nonPlateWeight > targetWeight) {
    throw new Error("Barbell/dumbbell heavier than target");
  } else if (nonPlateWeight === targetWeight) {
    // raw barbell is enough
    return [[], 0];
  }

  let exactWeightFound = false;
  let bestLocalGap = Number.MAX_VALUE;
  function BFS(plateWeights: number[], remainingPlates: PlatesInventory): [length: number, best: Weight[], gap: number] {
    const currWeight = calcTotalWeight(plateWeights);
    if (currWeight === targetWeight) {
      // found exact weight
      return [plateWeights.length, bestPlateWeights, 0];
    } else if (currWeight > targetWeight) {
      // constructed weight greater than desired
      return [-1, bestPlateWeights, Number.MAX_VALUE];
    } else {
      // go for breadth

      // gap between current branch weight and the target one
      let localGap = Math.min(bestLocalGap, targetWeight - currWeight);

       if (bestLength > 0 && plateWeights.length >= bestLength) {
          // won't find any better in this branch
          return [bestLength, bestPlateWeights, localGap];
        }
      
      for (const [plateWeight, numPlates] of remainingPlates) {
        if (numPlates <= 0) {
          continue;
        }
       
        // 
        const childWeights = [...plateWeights, plateWeight];
        const childRemainingWeights = new Map(remainingPlates);
        childRemainingWeights.set(plateWeight, numPlates - 2);
        const [childLength, , childGap] = BFS(childWeights, childRemainingWeights);

        // found exact result
        if (childLength > 0) {
          exactWeightFound = true;
          if (bestLength === -1 || childLength < bestLength) {
            // new exact best
            bestLength = childLength;
            bestPlateWeights = childWeights;
          }
        }
        // didn't found exact match, but check if difference from target (gap) isn't better
        // this checks if:
        // - haven't found any exact result yet (no need to find nearby weights if exact exists)
        // - the child branch has a closer match than current
        // - child branch needs less plates needed than current approximation
        else if (!exactWeightFound && childGap < localGap && (bestPlateWeights.length === 0 || childWeights.length < bestPlateWeights.length)) {
          // the above condition isn't enough, as sometimes worse neighbor branch could overwrite already best result
          // the solution is to also compare local branch gaps and update only if better
          if (localGap < bestLocalGap) {
            // console.debug('set', bestLocalGap, localGap, childGap, best, newState)
            bestPlateWeights = childWeights;
            bestLocalGap = localGap;
          }
        }
        localGap = Math.min(localGap, childGap);
      }
      
      return [bestLength, bestPlateWeights, localGap];
    }
  }

  // sort descending
  const sortResult = (a: number, b: number) => (a > b ? -1 : a < b ? 1 : 0);

  let [, plates, gap] = BFS([], weights);
  return [plates.sort(sortResult), gap];
}