javascriptalgorithm

How to create a layout that only has all even or all odd row size, and changes by only 2?

I have been iterating with both Claude 3.7 Sonnet, and ChatGPT 4o, for days and days, trying to get this to be exactly how I want it, but it keeps making mistakes in the algorithm, and on an on in making the same mistakes in basically a circle.

How do I make a "layout" (array of integers), which represents a grid, which has the following constraints:

  1. The function is generateGridLayout(n, minColumns, maxColumns), where practically speaking it is usually called as gen(n, 3, 7), but could in theory be anything which would make a nice grid, say gen(n, 2, 256) as the max range.
  2. It should handle arbitrary number of elements (say up to Number.MAX_SAFE_INTEGER, which is 9007199254740991, but practically my "grid layouts" will only have mainly up to 1000 items).
  3. If the number of items n is odd, then each row should only have an odd number of values. If n is even, then each row can have either even or odd numbers (think 30, can be 10 rows of 3, or 3 rows of 10).
  4. The rows can only ever differ by 2 in size, always decreasing. It can't ever differ by 3, 4, etc.. This means that 7 CANNOT be [5, 2] or [4, 4, 1], as those have jumps > 2. It can only be [7] or [3, 3, 1], if gen(7, 3, 7).
  5. (meta note, this is for a UI layout, so it is based on viewport/container size, so if we say "max is 7", but there is only space for 5, it will set the max to 5, this fact isn't really relevant for the solution though)
  6. If we say "max is 7", but there is an even number of items, and the even number can't satisfy "all even or all odd rows", then try maxColumns - 1, and so on, down to minColumns.
  7. Important: it should minimize the number of small sized rows. So for 29, at 6 maxColumns, it should be [5, 5, 5, 5, 5, 3, 1], not [5, 5, 5, 5, 3, 3, 3]. That is, it maximizes the number of large rows, and minimizes the numbers of small rows. Likewise for 29, it should definitely not be [5, 5, 5, 5, 3, 3, 1, 1, 1].

Here are some examples to demonstrate the goal:

31
[5, 5, 5, 5, 5, 3, 3]
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1]

30
[5, 5, 5, 5, 5, 5]
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

29
[5, 5, 5, 5, 5, 3, 1]
[3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1]

28
[6, 6, 6, 6, 4]
[4, 4, 4, 4, 4, 4, 4]

27
[5, 5, 5, 5, 3, 3, 1]
[3, 3, 3, 3, 3, 3, 3, 3, 3]

26
[6, 6, 6, 4, 2, 2]
[4, 4, 4, 4, 4, 4, 4]

23
[5, 5, 5, 5, 3]
[3, 3, 3, 3, 3, 3, 3, 1, 1]

These show, if 5 or 6 is the max columns, what it would do, and what it should do if 4 or 3 is the max columns.

For example, 26 at 7 max columns should NOT be:

[6, 6, 6, 6, 2] # jumps more than 2
[4, 4, 4, 4, 4, 4, 2] # doesn't maximize maxColumns

It should ideally be:

[6, 6, 6, 4, 2, 2] # jumps max 2, maximizes large columns, minimizes small columns.

Here is my current solution:

log(29, 2, 7)
log(29, 2, 6)
log(29, 2, 5)
log(29, 2, 4)
log(44, 2, 3)

function distributeGridLayout(
  length,
  minColumns,
  maxColumns
) {
  function recur(
    dp,
    length,
    width,
  ) {
    if (length == 0) {
      return []
    }

    if (length < width - 2 || width <= 0) {
      return
    }

    if (dp[width].has(length)) {
      return
    }

    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
  }

  if (length <= maxColumns) {
    return [length]
  }

  if (maxColumns >= 3 && length === 7) {
    return [3, 3, 1]
  }

  if (maxColumns >= minColumns && length % maxColumns === 0) {
    const result = []
    while (length) {
      result.push(maxColumns)
      length -= maxColumns
    }
    return result
  }

  if (maxColumns > 4) {
    if (maxColumns > minColumns && length % (maxColumns - 1) === 0) {
      const result = []
      maxColumns--
      while (length) {
        result.push(maxColumns)
        length -= maxColumns
      }
      return result
    }
  }

  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) {
      if (width <= minColumns) {
        return
      }
      return [width, ...result]
    }
  }

  return
}

function log(n, min, max) {
  const grid = distributeGridLayout(n, min, max)
  console.log(`gen(${n}, ${min}, ${max})`, grid)
}

That is working for most, like this Tibetan layout (29 chars):

But it is not working for this Thai layout (44 chars, in 2-3 columns), here is the end of it (in my UI, if the algorithm returns undefined, it falls back to a basic grid layout):

What do I need to change exactly so this always fits my rules? The 44 layout of 3 max 2 min should be basically a 2 column layout...

Solution

  • This looks like an evolution on one of your earlier questions, with at least the difference that here we have a minColumns requirement.

    I didn't quite understand why in your code there is a specific treatment for the case length==7.

    Also the two blocks that check for length % maxColumns === 0 and length % (maxColumns - 1) === 0 seem quite arbitrary (like, why then not also length % (maxColumns - 2) === 0, ...etc?): these don't feel as real boundary cases that need special treatment.

    The exit condition inside the main loop, when width <= minColumns, should not depend on whether you got a successful result, but could just have been taken on board as a for loop condition (the opposite of it).

    There is also a problem with maxColumns -= maxColumns % dec: it makes maxColumns even when it was odd and length is even. Instead, you'll want maxColumns to be made odd when length is odd. I don't remember why this was so in the answer to your previous question, where the question had less specifications. Anyhow, this must be changed. It may be the easiest for code maintenance to just have a condition inside the main loop.

    There seem to be at least two mistakes in your expected results:

    26
[6, 6, 6, 4, 2, 2]
[4, 4, 4, 4, 4, 4, 4]

    I will assume this should be:

    26
[6, 6, 6, 4, 4]         // because of rule 7
[4, 4, 4, 4, 4, 4, 2]   // because sum must be 26

    Here is corrected code with some of your test cases.

    function distribute(length, minColumns, maxColumns) {
    const dp = Array.from({length: maxColumns + 1}, () => new Set());

    function recur(length, width) {
        if (length === 0) return [];
        if (length < width - 2 || width <= 0) return null;
        if (dp[width].has(length)) return null;
        dp[width].add(length);
        for (let i = 0; i < 2; i++) {
            let result = recur(length - width, width);
            if (result) return [width, ...result];
            width -= 2;
        }
        return null;
    }
    
    for (let width = maxColumns; width >= minColumns; width--) {
        // An odd length cannot be fulfilled with an even column count
        if (length % 2 > width % 2) continue; 
        const result = recur(length - width, width);
        if (result) return [width, ...result];
    }
    return null;
}

const tests = [
    // [length, minColumns, maxColumns, ...expected result]
    [31, 1, 6, 5, 5, 5, 5, 5, 3, 3],
    [31, 1, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1],
    [30, 1, 5, 5, 5, 5, 5, 5, 5],
    [30, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3],
    [29, 1, 6, 5, 5, 5, 5, 5, 3, 1],
    [29, 1, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1],
    [28, 1, 6, 6, 6, 6, 6, 4],
    [28, 1, 4, 4, 4, 4, 4, 4, 4, 4],
    [27, 1, 6, 5, 5, 5, 5, 3, 3, 1],
    [27, 1, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3],
    [26, 1, 6, 6, 6, 6, 4, 4],
    [26, 1, 4, 4, 4, 4, 4, 4, 4, 2],
    [23, 1, 6, 5, 5, 5, 5, 3],
    [23, 1, 4, 3, 3, 3, 3, 3, 3, 3, 1, 1],
    [29, 2, 7, 7, 7, 7, 5, 3],
    [29, 2, 6, 5, 5, 5, 5, 5, 3, 1],
    [44, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1],
    [7, 2, 6, 3, 3, 1],
];

for (const [length, minColumns, maxColumns, ...expected] of tests) {
    const result = distribute(length, minColumns, maxColumns);
    if (JSON.stringify(result) !== JSON.stringify(expected)) {
        throw Error(`Expected distribute(${length}, ${minColumns}, ${maxColumns}) to return ${JSON.stringify(expected)}, but got ${JSON.stringify(result)}`);
    }
}
console.log("All tests passed successfully.");