Program to 2D Array complex alignment

问题:

Given 2D Array, where there are 2 sets of array the first set is not aligned properly, there is a space in 1st set, the 1st set should be aligned with second set. Length of the 2sets are same. But in the first set there are empty column comes till the starting of 2nd set.

We need to write an algorithm which will remove the unnecessary spaces in 1st set. In the given example space came in 1st column till 8th row, we should remove based on condition that if there are more blanks. Constraint is we should not remove if only one space is there.

Input

[[,1,,2,,3,,4,],
 [,1,,2,,3,,4,],
 [,1,,2,,3,,4,],
 [,1,,2,,3,,4,],
 [,1,,2,,3,,4,],
 [,1,,2,,3,,4,],
 [,1,,2,,3,,4,],
 [,1,,2,,3,,4,],


 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,]
]

Output array

[

 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,]


 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,],
 [1,2,3,4,,,,,]

]

1. There will be alignment issue only with 1st set, all the remaining sets are having no alignment issues. We should not change the remaining sets.
2. First we need to find out set information.
3. If there is a column which is empty in every set then we need to remove that set.
4. We should not decide the set based on one space, rather based on 10% of the spaces in entire column.
5. We should not remove all the spaces, we should remove only if there are more 10% of the space in entire column.
6. The data is not in numbers but strings. Empty spaces are nothing but empty strings ("")

I have wrote different algorithms but nothing seems to be working.

One algorithm is to send format array and input array. But this is not solving the problem.

  alignArray(arr1, arr2) {
    let arr3 = [];
    let arr4 = _.compact(arr2);
    let count = 0;
    _.map(arr1, function (num, index) {
      if (_.isString(num) && !(_.isEmpty(num))) {
        if (arr4[count])
          arr3.push(arr4[count]);
        else
          arr3.push("");
        count++;
      } else {
        arr3.push("");
      }
    });
    return arr3;
  }

EDGE CASES:

1. There should be some sets which are similar to 1st set.

   [[,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,],

   [1,2,3,4,,,,,], [1,2,3,4,,,,,], [1,2,3,4,,,,,], [1,2,3,4,,,,,], [1,2,3,4,,,,,], [1,2,3,4,,,,,], [1,2,3,4,,,,,], [1,2,3,4,,,,,], [1,2,3,4,,,,,],

   [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,], [,1,,2,,3,,4,] ]

回答1:

You could get the pattern first, build a filter pattern for the pattern and map the array by filtering the values with the filter pattern.

For example this array contains three different strings and the pattern of the strings are the truthy values of the splitted string with one or zero for falsy (missing values).

',1,,2,,3,x,4,' // 010101010
',1,,2,,3,,4,'  // 010101010
'1,2,3,4,,,,,'  // 111100000

After getting an object with the pattern and count of these patterns, a filtering pattern is added by looking if the relation between pattern count and total count is greater than 0.1, then the whole pattern is taken for filtering or a new filter pattern is build by adding columnwise truthy values. This sum is checked and if the relation to total is greater than 0.1, this column is included in the filter pattern.

The result of the object columns looks like this:

{
    111100000: {
        count: 9,
        filter: "111100000"
    },
    "010101110": {
        count: 1,
        filter: "010101010"
    },
    "010101010": {
        count: 8,
        filter: "010101010"
    }
}

As result, all columns are filtered by the filter pattern of the pattern of the array.

const
    getPattern = a => a.map(v => v ? 1 : 0).join('');

var csv = [',1,,2,,3,x,4,', ',1,,2,,3,,4,', ',1,,2,,3,,4,', ',1,,2,,3,,4,', ',1,,2,,3,,4,', ',1,,2,,3,,4,', ',1,,2,,3,,4,', ',1,,2,,3,,4,', ',1,,2,,3,,4,', '1,2,3,4,,,,,', '1,2,3,4,,,,,', '1,2,3,4,,,,,', '1,2,3,4,,,,,', '1,2,3,4,,,,,', '1,2,3,4,,,,,', '1,2,3,4,,,,,', '1,2,3,4,,,,,', '1,2,3,4,,,,,'],
    arrays = csv.map(s => s.split(',')),
    total = 0,
    columns = arrays.reduce((r, a) => {
        var p = getPattern(a);
        r[p] = r[p] || { count: 0 };
        r[p].count++;
        total++;
        return r;
    }, {}),
    patterns = Object.keys(columns),
    result;

patterns.forEach(p => {
    if (columns[p].count / total >= .1) {
        columns[p].filter = p;
        return;
    }
    columns[p].filter = Array
        .from(p, (v, i) => patterns.reduce((t, p) => t + v * p[i] * columns[p].count, 0) / total >= .1 ? 1 : 0)
        .join('');
});

result = arrays.map(a => (f => a.filter((_, i) => +f[i]))(columns[getPattern(a)].filter));

console.log(result);
console.log(columns);

.as-console-wrapper { max-height: 100% !important; top: 0; }