Grouping sub-arrays with nonidentical items

Posted on

Problem

I have a 2D array like

[ [ 'B', 'O', 'C' ],
  [ 'J', 'B', 'F' ],
  [ 'F', 'B', 'D' ],
  [ 'F', 'D', 'W' ],
  [ 'N', 'F', 'X' ],
  [ 'X', 'J', 'F' ],
  [ 'T', 'Y', 'H' ],
  [ 'R', 'Q', 'P' ] ],

And i need to group the sub-arrays such that in the resulting 3D array each group should contain only the sub-arrays with items non identical with each other’s items. Besides there shouldn’t be any duplicate groups such as listing the same sub-arrays in a different order.

For the given array the result is;

[ [ [ 'B', 'O', 'C' ],
    [ 'F', 'D', 'W' ],
    [ 'T', 'Y', 'H' ],
    [ 'R', 'Q', 'P' ] ],
  [ [ 'J', 'B', 'F' ],
    [ 'T', 'Y', 'H' ],
    [ 'R', 'Q', 'P' ] ],
  [ [ 'F', 'B', 'D' ],
    [ 'T', 'Y', 'H' ],
    [ 'R', 'Q', 'P' ] ],
  [ [ 'N', 'F', 'X' ],
    [ 'T', 'Y', 'H' ],
    [ 'R', 'Q', 'P' ],
    [ 'B', 'O', 'C' ] ],
  [ [ 'X', 'J', 'F' ],
    [ 'T', 'Y', 'H' ],
    [ 'R', 'Q', 'P' ],
    [ 'B', 'O', 'C' ] ] ]

My code works fine but something back in my mind says i am doing some overkill and it can be done better. Any ideas how this job might be done any better?

var arr = [ [ 'B', 'O', 'C' ],
            [ 'J', 'B', 'F' ],
            [ 'F', 'B', 'D' ],
            [ 'F', 'D', 'W' ],
            [ 'N', 'F', 'X' ],
            [ 'X', 'J', 'F' ],
            [ 'T', 'Y', 'H' ],
            [ 'R', 'Q', 'P' ] ],
 result = arr.reduce((s,t,i,a) => t.used ? s
                                         : (s.push(a.map((_,j) => a[(i+j)%a.length])
                                                    .reduce((p,c,k) => k-1 ? p.every(t => t.every(n => c.every(v => n !== v))) ? (c.used = true, p.push(c),p) : p
                                                                           : [p].every(t => t.every(n => c.every(v => n !== v))) ? (c.used = true, [p,c]) : [p])),s),[]);
 console.log(JSON.stringify(result,null,2))

The code is slightly complicated but in the heart of it lies;

.reduce((p,c,k) => k-1 ? p.every(t => t.every(n => c.every(v => n !== v))) ? (c.used = true, p.push(c),p) : p
                                                                           : [p].every(t => t.every(n => c.every(v => n !== v))) ? (c.used = true, [p,c]) : [p]))

which will take

[ [ 'B', 'O', 'C' ],
  [ 'J', 'B', 'F' ],
  [ 'F', 'B', 'D' ],
  [ 'F', 'D', 'W' ],
  [ 'N', 'F', 'X' ],
  [ 'X', 'J', 'F' ],
  [ 'T', 'Y', 'H' ],
  [ 'R', 'Q', 'P' ] ],

and turn it into

[ [ 'B', 'O', 'C' ],
  [ 'F', 'D', 'W' ],
  [ 'T', 'Y', 'H' ],
  [ 'R', 'Q', 'P' ] ]

and will mark all sub arrays as used. Then we will rotate the given array with a.map((_,j) => a[(i+j)%a.length]), up until an unused sub array is at index 0 position and repeat the same job.

Solution

Cascaded ternaries, generic variable names, obfuscated logic produces write-only and mind-boggling code that requires deciphering for anyone, including you in the future.

Let’s try to write a self-explanatory code:

function groupUnique(input) {
    let results = [];
    for (let inputRow of input) {
        let collectedCells = new Set(inputRow);
        let draft = [inputRow].concat(
            input.filter(row => {
                if (row.some(cell => collectedCells.has(cell)))
                    return false;
                for (let cell of row)
                    collectedCells.add(cell);
                return true;
            })
        );
        let alreadyAdded = results.some(res =>
            res.length == draft.length && res.every(row => draft.includes(row))
        );
        if (!alreadyAdded)
            results.push(draft);
    }
    return results;
}

Leave a Reply

Your email address will not be published. Required fields are marked *