Balance recordings

balance.js

function distribute_recordings_over_lines(num_recordings, distribution, lines) {
  // This function distributes number of recordings optimally 		
  // given the current distribution and the lines on which you want to record.
  
  function find_level(n, distribution, lines, low, high) {
    // Compute the level
    const level = (low + high) / 2;

    // Compute search statistic
    let s = 0;
    for (let line = 1; line <= distribution.length; line++)
      if (lines.includes(line))
        s += Math.max(0, level - distribution[line-1]);

    // Return normally if the correct value was found within tolerance
    const tolerance = 1e-6;
    if (Math.abs(n - s) < tolerance)
      return level;

    // Decide new search area
    if (s > n)
      return find_level(n, distribution, lines, low, level);
    else
      return find_level(n, distribution, lines, level, high);
  }

  // Validate inputs
  if(!Number.isInteger(num_recordings) || num_recordings <= 0)
    throw "num_recordings should be a positive integer > 0";
  if(Math.min(...lines) < 1)
    throw "you can only record lines: 1 till " + distribution.length + ". Got line = " + Math.min(...lines) + " as input.";
  if(Math.max(...lines) > distribution.length)
    throw "you can only record lines: 1 till " + distribution.length + ". Got line = " + Math.max(...lines) + " as input.";

  // Init output
  const recordings_per_line = new Array(distribution.length).fill(0);
  
  // 1. Find the level through binary search between high and low
  const low = Math.min(...distribution) + (num_recordings / lines.length);
  const high = Math.max(...distribution) + num_recordings;
  let level = find_level(num_recordings, distribution, lines, low, high);


  // 2. Compute recordings_per_line rounded to the nearest integer above
  for (let line = 1; line <= distribution.length; line++)
    if (lines.includes(line))
      recordings_per_line[line-1] = Math.ceil(Math.max(0, level - distribution[line-1]));

  // 3. Compute the number of excess recordings due to the ceiling in the step above
  const sum = recordings_per_line.reduce((a, b) => a + b, 0);
  let excess = sum - num_recordings;
  
  // 4. Remove excess recordings starting from the last line till we reach the correct number
  let line = recordings_per_line.length+1;
  while(excess > 0)
  {
    line--; 

    // Skip if line is not under consideration
    if(!lines.includes(line))
      continue;
    
    // Skip if recording is already 0 for this line
    if(recordings_per_line[line-1] == 0)
      continue;

    recordings_per_line[line-1]--;    
    excess--;
  }

  // 5. Return recordings_per_line
  return recordings_per_line;
}

// ----------------
// Test case
// ----------------

// Input
const distribution = [0, 0, 0];
const lines = [1, 2, 3];
const n = 15;

// Compute
const recordings_per_line = distribute_recordings_over_lines(n, distribution, lines);

// Output
const sum_recordings_per_line = recordings_per_line.reduce((a, b) => a + b, 0);
const new_distribution = []
for (let i = 0; i < distribution.length; i++)
  new_distribution.push(distribution[i] + recordings_per_line[i]);

// Print sum and old + new distribution
console.log("Old distribution per line: \t" + distribution);
console.log("Needed recordings per line: \t" + recordings_per_line + "\t (sum = " + sum_recordings_per_line + ")");
console.log("New distribution per line: \t" + new_distribution);

// Outputs:
// Old distribution per line:  10,  3, 35, 23, 50, 23, 10,  0
// Needed recordings per line:  0,  7,  0,  0,  0,  0,  0,  9  (sum = 16)
// New distribution per line:  10, 10, 35, 23, 50, 23, 10,  9