Split 2D Array into multiple connected pieces by given rows and columns

Question

I'm trying to find the most efficient way of breaking a two-dimensional array into different two-dimensional pieces, all stored into a new array which will be returned as the result.

I have a 2D array consisting of a string "N M" in the cell at row N and column M. For example, the value in row 2, column 3 would be "2 3".

Now given some rows and column indexes, I want to remove those rows and columns, and group each "piece" into its own 2D array. A "piece" is a set of orthogonally connected cells, without any intervening cells from the rows and columns removed above.

e.g. if I have an array with 8 rows and 7 columns, and I try to remove the rows [2, 3, 5], and columns [2, 6], the resulting array of "pieces" should be

[
  [["0, 0", "0, 1"], ["1, 0", "1, 1"]],
  [["0, 3", "0, 4", "0, 5"], ["1, 3", "1, 4", "1, 5"]],
  [["4, 0", "4, 1"]],
  [["4, 3", "4, 4", "4, 5"]],
  [["6, 0", "6, 1"], ["7, 0", "7, 1"]],
  [["6, 3", "6, 4", "6, 5"], ["7, 3", "7, 4", "7, 5"]]
]

In case the description is unclear, I went ahead and made a visual example of the process in mind here to detail the steps, problems and goals involved.

This is what I was able to come up with, but it's producing arrays that include exception columns. I know why, but I don't know how to get around it short of adding extra complexity which is not conducive to efficiency.

const SourceArray = [ ['R0·C0', 'R0·C1', 'R0·C2', 'R0·C3', 'R0·C4', 'R0·C5', 'R0·C6'],
                      ['R1·C0', 'R1·C1', 'R1·C2', 'R1·C3', 'R1·C4', 'R1·C5', 'R1·C6'],
                      ['R2·C0', 'R2·C1', 'R2·C2', 'R2·C3', 'R2·C4', 'R2·C5', 'R2·C6'],
                      ['R3·C0', 'R3·C1', 'R3·C2', 'R3·C3', 'R3·C4', 'R3·C5', 'R3·C6'],
                      ['R4·C0', 'R4·C1', 'R4·C2', 'R4·C3', 'R4·C4', 'R4·C5', 'R4·C6'],
                      ['R5·C0', 'R5·C1', 'R5·C2', 'R5·C3', 'R5·C4', 'R5·C5', 'R5·C6'],
                      ['R6·C0', 'R6·C1', 'R6·C2', 'R6·C3', 'R6·C4', 'R6·C5', 'R6·C6'],
                      ['R7·C0', 'R7·C1', 'R7·C2', 'R7·C3', 'R7·C4', 'R7·C5', 'R7·C6'] ];

function split2DArray_test() {
  let arrObjs = {
    oldArr: {
    obj: SourceArray,
      bounds: { row: 8, col: 7, },
      setBounds: function() {
        this.bounds.row = this.obj.length;
        this.bounds.col = this.obj[0].length;
      },
    },
    newArr: { collection: [], component: [], design: { rInit: 0, rEnd: 0, cInit: 0, cEnd: 0 } },
    splits: { atRows: [2, 3, 5], atCols: [2, 5] }
  };
  arrObjs.oldArr.setBounds();

  let i = { lv1_R: 0, lv2_C: 0 , lv3_R: 0, lv4_C: 0, slicer: 0 }; let escape = false;

  /*
    1.  Iterate through rows. (1st level)
    2.  If row excepted, continue iterating through rows. If not excepted, iterate through columns. (2nd level)
    3.  If column not excepted, RECORD ADDRESS and continue iterating through column.
    4.  When excepted column found, RECORD COLUMN - 1, and regin iterating through rows again (3rd level). When excepted row found, RECORD ROW - 1.
    5.  Record data (SliceArr): [RECORD ADDRESS[R] = RowA, RECORD ADDRESS[C] = ColA, RECORD ROW - 1 = RowB, RECORD COLUMN - 1 = ColB]
    6.  Create NewArr[] and SliceArrObj[]
    7.  Iterate through rows (r) from new SliceArr (4th level), and do SliceArrObj.push(OldArr[r].slice(ColA, ColB - ColA))
    8.  NewArr.push(SliceArrObj)
    9.  Set 2nd-level iterator to RECORD COLUMN + 1
    10. Loop should work theoretically. Untested.
  */

  Logger.log(`Excepting rows: ${arrObjs.splits.atRows.join(', ')}`);
  Logger.log(`Excepting columns: ${arrObjs.splits.atCols.join(', ')}`);

  console.time('slicer');
  for (i.lv1_R = 0; i.lv1_R < arrObjs.oldArr.bounds.row; i.lv1_R++) {
    if (arrObjs.splits.atRows.includes(i.lv1_R)) { continue; } else {
      // We've arrived at a non-excepted row.
      for (i.lv2_C = 0; i.lv2_C < arrObjs.oldArr.bounds.col; i.lv2_C++) {
        if (arrObjs.splits.atCols.includes(i.lv2_C)) { continue; } else {
          arrObjs.newArr.design.rInit = i.lv1_R; arrObjs.newArr.design.cInit = i.lv2_C;
          Logger.log(`Found origin cell '${arrObjs.oldArr.obj[i.lv1_R][i.lv2_C]}'`);
          for (i.lv3_R = arrObjs.newArr.design.rInit; i.lv3_R < arrObjs.oldArr.bounds.row; i.lv3_R++) {
            if (arrObjs.splits.atRows.includes(i.lv3_R)) {
              arrObjs.newArr.design.rEnd = i.lv3_R - 1;
              for (i.lv4_C = arrObjs.newArr.design.cInit; i.lv4_C < arrObjs.oldArr.bounds.col; i.lv4_C++) {
                if (arrObjs.splits.atCols.includes(i.lv4_C)) {
                  arrObjs.newArr.design.cEnd = i.lv4_C - 1;
                  for (i.slicer = arrObjs.newArr.design.rInit; i.slicer < arrObjs.newArr.design.rEnd + 1; i.slicer++) {
                    arrObjs.newArr.component.push([arrObjs.oldArr.obj[i.slicer].slice(arrObjs.newArr.design.cInit, arrObjs.newArr.design.cEnd + 1)]);
                  };
                  arrObjs.newArr.collection.push('Split'); // For the sake of output logging.
                  arrObjs.newArr.collection.push(arrObjs.newArr.component);
                  arrObjs.newArr.component = [];
                  i.lv2_C += 1 + arrObjs.newArr.design.cEnd - arrObjs.newArr.design.cInit;
                  arrObjs.newArr.design.rInit = 0; arrObjs.newArr.design.rEnd = 0; arrObjs.newArr.design.cInit = 0; arrObjs.newArr.design.cEnd = 0;
                  escape = true; break;
                };
              };
            };
            if (escape) { escape = false; break; };
          };
        };
      };
      i.lv2_R += 1 + arrObjs.newArr.design.rEnd - arrObjs.newArr.design.rInit;
    };
  };
  console.timeEnd('slicer');

  Logger.log(`Splitting 2D Array into:\n\n${(arrObjs.newArr.collection.join('\n\n'))}`); // The output logging.

  /* Idea Space:

    ===== PROPOSED METHOD, INCOMPLETE =====
      1. Save the origin cell of the first valid slice bounds.
      2. Iterate (FOR) through columns, starting at the Bound Minimum, and going to the Bound Maximum.
      3. If an exception row is found, save slice col bound max as (i.c - 1).
      4. Now, iterate through rows from slice origin to next exception or bound. Once this is met, save slice row bound max as (i.r - 1).
      5. Iterate through slice row bounds, pushing slices with slice column bounds as Array.slice() arguments.
      6. Push new 2D array to new array collection.

      === CONCEPTS WORTH TESTING ===

      I.    Iterative Cell Search

        Consider moving forward by setting exception or bound limits. Ex: Column iteration runs into a bound limit: slices.resume.c = false. If it's an exception, slices.resume.c = true. This way,
        any time a full 2D slice is pushed to the collection of arrays, it can take the existing current slice data and either iterate across to the next horizontal array (Resume = true), or
        iterate down to the next vertical array (Resume = false). If both Column and Row resume are false, then we are done adding sliced 2D arrays to the array collection.

        If at least one Resume is true, then another resume can be made true. Once both are true, then a new slice origin point can be made.

      II.   Iterative Bounds & Exception Search.

      1. Table Bounds defined and adjacent exceptions trimmed (Done).
          > The current exceptions are now the top-left-side borders of the desired slices.
      2. Iterate through exception indices column first (On first loop, operate from top-left bound), then row. On each, set slice start to (i.r + 1, i.c + 1), where i.? = the exception column or
         row. Set the end bounds to the index represented by the next element in the list (column or row).
  */
};

Answer 1

In the approach I take below, I split up the problem in two main steps:

const ranges = (splits, length) => [...splits, length].reduce(
  (r, e, i, a) => (s = i ? a[i - 1] + 1 : 0, e - s ? [...r, {s, e}] : r),
  []
);

const blocks = (array, rowRanges, colRanges) => rowRanges.map(
  ({s, e}) => array.slice(s, e)
).map(block => colRanges.map(
  ({s, e}) => block.map(row => row.slice(s,e))
)).flat();

• The ranges() function takes an input array containing "splits" information (i.e. rowSplits or colSplits), and then uses that information to create an array of ranges for the row blocks or column blocks. Each range is defined as an object of type {s: number, e: number}, where s is the start of the range (inclusive) and e is the end (exclusive). The reduce operation used in this function makes it so that empty ranges are filtered out.

• The blocks() function takes the 2D array and the row and column ranges as input. It first uses the row ranges to split the 2D array into row blocks, and then uses the column ranges to split those blocks down to the regions defined in the problem statement. The splitting operations are all implemented by mapping the ranges to their corresponding array slices. Finally, the entire result is flattened to arrive at the required output.

---

Complete snippet:

const rows = 8;
const cols = 7;
const arrOld = Array.from(
  { length: rows}, (_, y) => Array.from(
    { length: cols }, (_, x) => `${y}, ${x}`
  )
);
const rowSplits = [2, 3, 5];
const colSplits = [2, 6];

const ranges = (splits, length) => [...splits, length].reduce(
  (r, e, i, a) => (s = i ? a[i - 1] + 1 : 0, e - s ? [...r, {s, e}] : r),
  []
);

const blocks = (array, rowRanges, colRanges) => rowRanges.map(
  ({s, e}) => array.slice(s, e)
).map(block => colRanges.map(
  ({s, e}) => block.map(row => row.slice(s,e))
)).flat();

const arrNew = blocks(
  arrOld,
  ranges(rowSplits, rows),
  ranges(colSplits, cols)
);

console.log(arrNew);