BFE.devでのAI解答例 - JavaScript コーディング問題
175. CSS Grid Layout auto-placement algorithm - dense

解法例

同様に、まずはセルを配置できるかどうかを判断し、できない場合には次の空いているセルに進みます。しかし、dense パッキングでは、接続セルが完全に占有されるまで、その空間を占有できないため、配置できなかったセルを放棄しなければなりません。

具体的には、多くの場合、行の開始から最初の穴までにあるセルを割り当てることができますが、可能な場合は、空いているスロットを効率的に使用して、可能な限り多くの子セルを配置することが重要です。

次に、配置されたセルをダブルカウントしている（占領されたセルに対して横方向のスペースを評価しない）点に注意してください。各行において、同じxの他のセルを配置することができ、次の空いているセルが見つかるまでに収束するように選択できる場合、セルIDを途中で挿入する必要があります。

最後に、sparse パックモードで見つかったセルの連結リストが有用ですが、dense パックモードでは、占有されているスロットの配列が必要になるため、 cellSlotsとaddCellToSlots関数をパックモードに対応するように修正する必要があります。

以下は実装です：

// 実際にキャリア内には、inputはコード内で定義され、
// 実行前に呼び出す必要があります
// input example: [{id: 1, style: {gridColumnStart: 2}}, ...]
function layout(rows, columns, input) {
  const grid = Array.from({length: rows}, () => new Array(columns).fill(0));
  const spans = {}; // 要素のcellスパンを追跡する
  const children = input.slice().sort((a, b) => b.style?.gridColumnEnd ? 1 : -1);
  const cellSlots = Array.from({length: rows}, () => new Array(columns).fill(false)); // 放棄された子セルがある場合に使用する
  const addCellToSlots = (slots, cell) => {
    const {x, y} = cellSlots.find(([x, y]) => !slots[x][y]) || []; // 最初に使用可能なスロットを検索する
    if (x !== undefined) {
      slots[x][y] = cell.id;
      cellSlots[x][y] = true;
      for (let i = 0; i < cell.style.gridRowSpan; i++) {
        for (let j = 0; j < cell.style.gridColumnSpan; j++) {
          cellSlots[x+i][y+j] = true; // 占領されたスロットをマークする
        }
      }
    }
  };

  const getNextCoord = (slots, x, y) => {
    if (slots[x][y] === 0) return {x, y};
    let startRow = x, startCol = y + 1;
    while (startRow < rows) {
      while (startCol < columns) {
        if (slots[startRow][startCol] === 0) {
          return {x: startRow, y: startCol};
        }
        startCol += 1;
      }
      startCol = 0;
      startRow += 1;
    }
    return null;
  };

  children.forEach((cell, idx) => {
    let [start, end] = [1, 1];

    if (cell.style) {
      if (cell.style.gridColumnStart) start = parseInt(cell.style.gridColumnStart.split(' ')[1]) || 1;
      if (cell.style.gridColumnEnd) end = parseInt(cell.style.gridColumnEnd.split(' ')[1]) || start + 1;
      if (cell.style.gridRowStart) {
        const rowStart = parseInt(cell.style.gridRowStart);
        if (rowStart > 1) {
          for (let r = 1; r < rowStart; r++) {
            grid[r-1] = grid[r-1].map((v, i) => v || (r === rowStart - 1 && i < start ? end - start : false));
          }
        }
      }
      if (cell.style.gridRowEnd) {
        const rowEnd = parseInt(cell.style.gridRowEnd);
        const maxSpan = [...grid.slice(rowEnd-2, rowEnd-1)[0]].reverse().find((v, i) => Boolean(v) && i < columns - 1 - start) || columns - start;
        spans[cell.id] = Math.min(maxSpan + 1, end - start);
      }
    }

    if (!spans[cell.id]) {
      spans[cell.id] = end - start;
    }

    addCellToSlots(grid, {id: cell.id, style: {gridColumnSpan: spans[cell.id], gridRowSpan: 1}});
    
    let coord = {x: 0, y: 0};
    for (let i = 0; i < rows; i++) {
      for (let j = 0; j < columns; j++) {
        if (grid[i][j] === cell.id) {
          coord = {x: i, y: j};
          break;
        }
      }
      if (grid[coord.x][coord.y] === cell.id) break;
    }
    // cellが拾われた位置に戻す
    grid[coord.x][coord.y] = 0;

    if (input[idx + 1] && input[idx + 1].style?.gridColumnStart === `span ${columns}`) {
      const endRow = Math.max(...grid[coord.x+spans[cell.id]-1]);
      const {x, y} = getNextCoord(grid, coord.x, endRow);
      if (x !== null) {
        grid[x][y] = cell.id;
        addCellToSlots(grid, {id: cell.id, style: {gridColumnSpan: spans[cell.id], gridRowSpan: x + spans[cell.id] - coord.x}});
        return;
      }
    }

    let {x, y} = coord;
    const rowSpan = Math.max(...grid[x].slice(y, y+spans[cell.id]));
    y = grid[x].findIndex((v, i) => i >= y && i < y + spans[cell.id] && v === rowSpan);
    grid[x][y] = cell.id;
    addCellToSlots(grid, {id: cell.id, style: {gridColumnSpan: spans[cell.id], gridRowSpan: 1}});
    if (y !== coord.y) {
      const nextCell = children.find((cell) => grid[x][y - 1] === cell.id);
      if (nextCell) {
        children.splice(idx + 1, 0, cell);
      }
    }
  });

  return grid;
}

また、解法の可読性を向上させるため、getNextCoord関数を独立させることができ、既存の関数をパラメータで、spreadして呼び出すことができます。これにより、2つの異なる実装の大部分を共有できます。ここで、多くの部分を再定義するために、2つ目の関数（layoutDenseとすることにします）を定義します。

function getNextCoord(grid, slotFn) {
  return function(x, y) {
    if (grid[x][y] === 0) return {x, y};
    let [startRow, startCol] = [x, y + 1];
    while (startRow < grid.length) {
      while (startCol < grid[startRow].length) {
        const data = {x: startRow, y: startCol};
        if (!grid[data.x][data.y] && !slotFn(data.x, data.y)) return data;
        startCol += 1;
      }
      startCol = 0;
      startRow += 1;
    }
    return null;
  };
}

function layoutDense(rows, cols, children) {
  const grid = Array.from({ length: rows }, () => new Array(cols).fill(0));
  const spans = {};
  const cellSlots = Array.from({ length: rows }, () => new Array(cols).fill(false));

  const getNextEmptyCoord = getNextCoord(grid, (x, y) => cellSlots[x][y]);

  let flushed = false;
  children.forEach((cell, idx) => {
    // 余計な部分を省略した略化版
    let [start, end] = [1, 1];
    if (cell.style) {
      if (cell.style.gridColumnStart) start = parseInt(cell.style.gridColumnStart.split(' ')[1]) || 1;
      if (cell.style.gridColumnEnd) end = parseInt(cell.style.gridColumnEnd.split(' ')[1]) || start + 1;
      if (cell.style.gridRowStart) {
        const rowStart = parseInt(cell.style.gridRowStart);
        if (rowStart > 1) {
          for (let r = 1; r < rowStart; r++) {
            for (let c = 0; c < cols; c++) {
              grid[r-1][c] = grid[r-1][c] || false;
              cellSlots[r-1][c] = true;
            }
          }
        }
      }
      if (cell.style.gridRowEnd) {
        const rowEnd = parseInt(cell.style.gridRowEnd);
        const maxSpan = [...grid.slice(rowEnd-2, rowEnd-1)[0]].reverse().find((v, i) => Boolean(v) && i < cols-1-start) || cols-start;
        spans[cell.id] = Math.min(maxSpan + 1, end - start);
      }
    }

    if (!spans[cell.id]) {
      spans[cell.id] = end - start;
    }

    let [_x, _y] = [null, null];
    while (!flushed) {
      const coord = getNextEmptyCoord(_x || 0, _y === null ? start - 1 : _y);
      if (coord !== null) {
        [_x, _y] = [coord.x, coord.y];
        break;
      } else { // キャッシュしきれなかった場合は一時的に占有する
        flushGrid(cellSlots);
        flushed = true;
        break;
      }
    }
    // childをグリッドとセルスロットに追加する
    if (!flushed) {
      for (let i = _y; i < _y + spans[cell.id]; i++) {
        cellSlots[_x][i] = true;
        grid[_x][i] = cell.id;
      }
    } else {
      addCellToSlots(cell, cellSlots, grid);
      flushed = false;
    }
  });

  return grid;
}

function flushGrid(cellSlots) {
  for (let i = 0; i < cellSlots.length; i++) {
    if (cellSlots[i].every(v => v)) {
      cellSlots.splice(i--, 1);
    }
  }
  cellSlots.push(new Array(cellSlots[0].length).fill(false));
}

function addCellToSlots(cell, cellSlots, grid) {
  const slot = getNextCoord(grid, () => false)(0, -1);
  if (slot === null) {
    throw new Error('Cannot place any cell');
  }
  const [start, end] = [slot.y, slot.y + (cell.style?.gridColumnSpan || 1)];
  if (start >= cellSlots[0].length) {
    throw new Error('Out of grid');
  }
  for (let i = 0; i < cell.style?.gridRowSpan || 1; i++) {
    for (let j = 0; j < end - start; j++) {
      cellSlots[slot.x + i][start + j] = true;
    }
  }
  grid[slot.x][start] = cell.id;
}