Split an array of strings into chunks of equal length

Question

Context:
I'm trying to organize blocks of HTML text so that they appear to evenly spread across an element, while keeping their original size (i.e. the size of the string).

Problem:
I have an array of strings and I want to sort them with the given conditions:

Each run of strings should have it's length no longer than W
The length of a run is the sum of it's strings' lengths
Each run should be roughly equal in size
- i.e. the length should be closer to the median length of all runs than to the maximum allowed
The median length of a run should be as close to the maximum as possible

Bonus:
Each string has a color that constrains where it can be placed. i.e. all blues must be adjacent to each other and cannot be placed randomly throughout. This means that at the head/tail ends of a run of colors must "align" with the next color.

(I think my greedy approach below satisfies this, but fails to make the rows of a similar length)

2x Bonus (easier/harder?):
Allow for runs of colors to be interrupted, but each run must be at least K long, the last run of a color can be smaller than K

Solution can be in any (programming) language, I just put JS cause that's what I'm working with.

Example:

> f(S=['abcd', 'def', 'a', 'b', 'wx', 'dsaad'], W=5)
=> [
  'dsaad',
  'abcd',    
  'def', 'b', // length of 4 is better than 5, then 3 
  'wx', 'a', // length of 3 is better than 2
]

Here is my greedy solution, if nothing else I'd appreciate some advice on optimizations.

interface Tag { name: string; color: string}

const greedyTagSort = (arr: Tag[], width: number) => {
  const sorted: Tag[] = [];
  const copy = [...arr];
  let combined = 0;
  let color = '';
  const PADDING = 2;

  while (sorted.length !== arr.length) {
    let max, maxC, maxW, maxWC;
    max = maxC = maxW = maxWC = copy[0];
    let iMax, iMaxC, iMaxW, iMaxWC;
    iMax = iMaxC = iMaxW = iMaxWC = 0;

    let i = 0;

    while (i < copy.length) {
      const tmp = copy[i];
      const weightCheck = tmp.name.length + PADDING + combined <= width;

      if (color === tmp.color) {
        if ((maxWC.color !== color || tmp.name.length > maxWC.name.length) && weightCheck) {
          maxWC = tmp;
          iMaxWC = i;
        } else if (maxC.color !== color || tmp.name.length > maxC.name.length) {
          maxC = tmp;
          iMaxC = i;
        }
      }

      if (tmp.name.length > maxW.name.length && weightCheck) {
        maxW = tmp;
        iMaxW = i;
      }

      if (tmp.name.length > max.name.length) {
        max = tmp;
        iMax = i;
      }
      i++;
    }

    if (color === maxWC.color && maxWC.name.length + PADDING + combined <= width) {
      max = maxWC;
      iMax = iMaxWC;
    } else if (color === maxC.color) {
      max = maxC;
      iMax = iMaxC;
      combined = 0;
    } else if (maxW.name.length + PADDING + combined <= width) {
      max = maxW;
      iMax = iMaxW;
    } else {
      combined = 0;
    }

    sorted.push(...copy.splice(iMax, 1));
    combined += max.name.length + PADDING;
    color = max.color;
  }

  return sorted;
};

Thanks in advance

user_10112154 · Answer

I took some time to revisit this and make some improvements. It's mostly the same function, but unifies all the condition checks into something more manageable, and sorts in-place. The only additional thing I can think to add, but didn't implement is sorting the color blocks in the most efficient way. Doing that I think would optimize the total "height" of the array, but the results are good enough as is to not warrant additional work.

Uses lodash and core-js pollyfills

const sortTags = (
  array: T[],
  targetWidth: number,
  getLength: (item: T) => number = item => item.id.length,
  getColor: (item: T) => string = item => item.color,
) => {
  getLength = _.memoize(getLength);
  getColor = _.memoize(getColor);
  const PADDING = 1;

  let color = '';
  let combined = 0;
  for (const i of Number.range(0, array.length)) {
    let maxIndex = i;
    let maxColor = getColor(array[i]);
    let maxLength = getLength(array[i]) + PADDING + combined;

    for (const [j, tmp] of array.values().indexed().drop(i + 1)) {
      const tmpColor = getColor(tmp);
      const tmpLength = getLength(tmp) + PADDING + combined;

      const maxOver = maxLength > targetWidth;
      const tmpUnder = tmpLength <= targetWidth;
      const tmpBetter = tmpLength > maxLength;
      const matchingColor = tmpColor === color;
      const mismatchedColor = maxColor !== color;
      const widthConstraint = maxOver === tmpUnder ? tmpUnder : tmpBetter; // x && y || x && z || y && z
      if (matchingColor === mismatchedColor ? mismatchedColor : widthConstraint) { // a && b || a && c || b && c
        maxIndex = j;
        maxColor = tmpColor;
        maxLength = tmpLength;
      }
    }

    combined = maxLength - (maxLength > targetWidth ? combined : 0);
    color = maxColor;
    [array[i], array[maxIndex]] = [array[maxIndex], array[i]];
  }
  return array;
};

Split an array of strings into chunks of equal length

1 Answers