title: Calculating weighted values as integers for layout
body: <p>I have a layout in which:</p>
  
  <ul>
  <li>The page is broken up into as many fixed width <strong>columns</strong> as can fit across it.</li>
  <li>Rows of <strong>boxes</strong> fit across these <strong>columns</strong>, each spanning a whole number of <strong>columns</strong>.</li>
  <li><strong>Boxes</strong> each have a weight used to determine their column span (IE: if a row has 6 <strong>columns</strong> and 2 <strong>boxes</strong> with weights 1 and 2, the <strong>boxes</strong> will have column spans of 2 and 4 respectively).</li>
  </ul>
  
  <p>If fractional column spans were allowed, this would be simple (multiply each weight by the column count and divide by the total weight) but breaking it into integers turns out to be waaaay more difficult.  This is what I've come up with:</p>
  
  <pre><code>function weightedIntegerValues(weights, total) {
      const totalWeight = totalValues(weights);
      const weightedValues = weights.map(weight =&gt; Math.round(total * weight / totalWeight));
  
      for (let totalValue = totalValues(weightedValues); totalValue &gt; total; totalValue = totalValues(weightedValues))
          subtractOneFromHighest(weightedValues);
  
      return weightedValues;
  }
  </code></pre>
  
  <p>For brevity I've omitted the following functions:</p>
  
  <ul>
  <li><code>totalValues</code> - gets the sum of all values in an array</li>
  <li><code>subtractOneFromHighest</code> - finds the highest value in an array and subtracts 1 from it (modifies array in place)</li>
  </ul>
  
  <p>The function works like this:</p>
  
  <ol>
  <li>Calculates the weighted values as described above, but rounds each value as it progresses</li>
  <li>Continually subtracts 1 from the highest value in <code>weightedValues</code> until the sum of <code>weightedValues</code> is less than or equal to <code>total</code> (accounting for any pairs of 0.5s that were rounded up)</li>
  </ol>
  
  <p>This function has 2 major problems:</p>
  
  <ol>
  <li>It's horribly inefficient (both <code>totalValues</code> and <code>subtractOneFromHighest</code> have to loop through the array inside of the function's main loop)</li>
  <li>It incorrectly favors reducing the first "highest value" it finds.</li>
  </ol>
  
  <p>To illustrate point (2) consider the following:</p>
  
  <pre><code>weightedIntegerValues([1, 2, 4, 3], 5); // [1, 1, 1, 2]
  </code></pre>
  
  <p>The weighting function found rounded values of <code>[1, 1, 2, 2]</code>, determined that was greater than the desired total of 5 and subtracted 1 from the first highest value it found (at index 3), but really we would have liked to subtract 1 from index 4, which was 1.5 before rounding, giving us <code>[1, 1, 2, 1]</code>.</p>
  
  <p>My questions are as follows:</p>
  
  <ol>
  <li>Can this be done in better than N<sup>2</sup>?  It'd be great to get it down to N.</li>
  <li>Is there some simple, and more mathematical way to favor numbers that were rounded to 0.5 instead of favoring lefter or righter values?</li>
  <li>Is there some neato CSS that could handle this use-case for me?  Flex-box comes pretty close, but hasn't quite lined up for me, yet (this is probably an entire other question on its own).</li>
  </ol>