How to chunk array into nice grid of rows and columns, where columns always line up (all rows are even, or all are odd)?

Question

What is an algorithm (in JavaScript/TypeScript), which can chunk an array into rows and columns, where the columns always line up across rows (i.e. all rows either odd, or all rows are even, not a mixture of odd and even)?

The input is the maxColumns allowed per row, and the array. It then chunks the array into an array of arrays, no larger than maxColumns, such that all rows are even, or all rows are odd, and each subsequent row can have no less than 2 fewer than the previous row. This makes the grid look good IMO.

Here are a few examples to handle, how the grid should be laid out:

# length 6, maxColumns 5
# nope: rows are more than 2 apart
x x x x x
    x

# same, length 6, maxColumns: 5
# yep, both even *and* rows are no less than 2 apart
x x x x
  x x   

# length: 7, maxColumns: 6
# nope: can't mix even and odd...
x x x x x x
      x

# same, length: 7, maxColumns: 6
# close, but still can't mix even/odd
x x x x
  x x
   x

# same, length: 7, maxColumns: 6
# yep!, rows are no more than 2 apart, and both odd
x x x
x x x
  x

# length: 17, maxColumns: 7
# yep!, rows are no more than 2 apart, and both odd
x x x x x x x
  x x x x x
    x x x
      x
      x

# length: 17, maxColumns: 6
# yep!, rows are no more than 2 apart, and both odd
x x x x x
x x x x x
  x x x
  x x x
    x

Is there a simple equation or algorithm that can accomplish this? I have spent over an hour thinking about this problem but haven't made much progress as it feels complex to wrap my head around.

This is as far as I've gotten:

function layout(length: number, maxColumns: number) {
  const rows: Array<number> = []
  if (length % maxColumns === 0) {
    // 7 7 7
    while (length) {
      rows.push(maxColumns)
      length -= maxColumns
    }
  } else if (isEven(maxColumns)) {
    
  }
  return rows
}

Answer 1

Some observations:

• All rows in the output are either all even or all odd. Once we select the odd/even parity for the first row, this determines what the parity will be for all next rows.
• When length is odd, this means the first row should have an odd length, otherwise we could never match that length. When length is even, we could start with either parity.

We could perform a depth-first search with the greatest row width that is possible at each turn until we get in an impossible situation, at which we backtrack. Using memoization we can avoid recalculating the same unfruitful remaining state multiple times.

That leads to this algorithm, when encoded in JavaScript:

function distribute(length, maxColumns) {

    function recur(dp, length, width) {
        if (length == 0) return [];
        if (length < width - 2 || width <= 0) return false;
        if (dp[width].has(length)) return false;
        dp[width].add(length);
        for (let i = 0; i < 2; i++) {
            let result = recur(dp, length - width, width);
            if (result) return [width, ...result];
            width -= 2;
        }
        return false;
    }
    
    
    if (length <= maxColumns) return [length];
    const dec = 2 - length % 2;
    maxColumns -= maxColumns % dec;
    const dp = Array.from({length: maxColumns + 1}, () => new Set());
    for (let width = maxColumns; width > 0; width -= dec) {
        const result = recur(dp, length - width, width);
        if (result) return [width, ...result];
    }
    return false;
}

const tests = [
    [1, 5],
    [6, 5],
    [7, 6],
    [8, 6],
    [9, 6],
    [10, 6],
    [11, 6],
    [12, 6],
    [13, 6],
    [14, 6],
    [17, 7],
    [17, 6],
    [211, 16]
];

for (const [length, maxColumns] of tests) {
    const result = distribute(length, maxColumns);
    console.log(length, maxColumns, JSON.stringify(result));
}

This snippet just outputs an array of widths. Each width represents the size of the row you have pictured in your examples.