Dicky Bullin Dicky Bullin - 1 month ago 6
Javascript Question

JS how to reform this irregular object

I have this object which its keys are guaranteed sorted and will be used for the operation. And each of its value is a 2d array.

var obj = {
"0": [
[0, 1], [0, 3], [0, 4]
],
"1": [
[1, 2], [1, 3]
],
"2": [
[2, 3], [2, 5]
],
"3": [
[3, 4], [3, 6]
],
"5": [
[5, 6]
],
"6": [
[6, 5]
]
}


I am trying to concatenate them and for each of its last value of the array is the next index of the object. So, my expected result is an array like this,

The pattern is, I have to find a way from
0
which is the first index of
obj
, to the last index which is
6
by using the values in each of it and linking its last array value to the next object. If that makes sense.

[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 6]
[0, 1, 2, 5, 6]
[0, 1, 3, 4, 5, 6]
[0, 1, 3, 4]
[0, 1, 3, 6]
[0, 3, 4, 5, 6]
[0, 3, 6]
[0, 4]


This is my code so far, as I don't know how to proceed further..

var result = [];
for (var key in obj) {
var myarr = obj[key];
for (var i = 0; i < myarr.length; i++) {
result.push(myarr[i])
}
}


Any idea or feedback is welcome.

Edit

One of the expected result was
[0, 1, 2, 3, 4, 5, 6]
, here's the step by step explanation.


  1. The
    obj
    key starts from
    0
    and ends in
    6
    , I have to form a way from
    0
    to
    6
    with the arrays in its value.

  2. Starts from
    obj[0]
    , the first array returns
    [0, 1]
    , save this to
    res
    . (
    res
    is now
    [0, 1]
    )

  3. The last value of array in
    res
    is
    1
    , now find the next value in
    obj[1]

  4. obj[1]
    has two arrays, and ends with
    2
    or
    3
    .. So it's possible to append with both of them, so it can be
    [0, 1, 2]
    or
    [0, 1, 3]
    . In this case, get the first one which is
    [1, 2]
    and append the last value to
    res
    . (
    res
    is now
    [0, 1, 2]
    ).

  5. The last value of array in
    res
    is now
    2
    , now find the next value in
    obj[2]
    .

  6. obj[2]
    has two arrays, and ends with
    3
    , or
    5
    .. It's possible to append with both of them, so it can be
    [0, 1, 2, 3]
    or
    [0, 1, 2, 5]
    . In this case, get the first one which is
    [2, 3]
    and append the last value to
    res
    . (
    res
    is now
    [0, 1, 2, 3]
    )

  7. The last value of array in
    res
    is now
    3
    , now find the next value in
    obj[3]
    .

  8. Repeat step 4 or 6. (
    res
    is now
    [0, 1, 2, 3, 4]
    ).

  9. The last value of array in
    res
    is now
    4
    , now find the next value in
    obj[4]
    .

  10. Repeat step 4 or 6. (
    res
    is now
    [0, 1, 2, 3, 4, 5]
    ).

  11. The last value of array in
    res
    is now
    5
    , now find the next value in
    obj[5]
    .

  12. Now value
    6
    is found which should be the end of iteration if you look at the step
    4
    . Repeat step 4 or 6. (
    res
    is now
    [0, 1, 2, 3, 4, 5, 6]
    ).

  13. Repeat from step 1, and form another way to do it, with no duplicates of
    [0, 1, 2, 3, 4, 5 ,6]
    .


Answer

This is a proposal, with a single extra output, mentioned below.

[
    [0, 1, 2, 3, 4, 5, 6],
    [0, 1, 2, 3, 6],
    [0, 1, 2, 5, 6],
    [0, 1, 3, 4, 5, 6],     /* extended from below                           */
    [0, 1, 3, 4],           /* original result                               */
    [0, 1, 3, 6],
    [0, 3, 4, 5, 6],        /* extended from below                           */
    [0, 3, 4],              /* extra line, line should not be in result      */
    [0, 3, 6],              /* but follows the same building rule than above */
    [0, 4]
]

Basically this solution is building a tree with the given information about linked nodes.

If some nodes are not contiguous, a backtracking is made for the missing links, with the above function for nodes, checkNodes or with iterPath, to walk the actual collected nodes for missing items.

function getParts(value, path, nodes) {
    function checkNodes(a) {
        if (a[1] === value + 1) {
            getParts(a[1], path.concat(a[1]), nodes);
            return true;
        }
    }

    function iterPath(k) {
        return (object[k] || []).some(function (a) {
            return path[path.length - 1] + 1 === a[1] || iterPath(a[1]);
        });
    }

    value = value || 0;
    path = path || [value];
    nodes = nodes || [];
    if (object[value]) {
        object[value].forEach(function (a, i, aa) {
            if (a[1] === lastKey) {
                parts.push(path.concat(a[1]));
                return;
            }
            getParts(a[1], path.concat(a[1]), nodes.concat(aa.slice(i + 1)));
        });
        return;
    }
    if (nodes.some(checkNodes)) {
        return;
    }
    path.slice(1).some(iterPath) && getParts(path[path.length - 1] + 1, path.concat(path[path.length - 1] + 1), nodes);
    parts.push(path);
}

var object = {
        0: [[0, 1], [0, 3], [0, 4]],
        1: [[1, 2], [1, 3]],
        2: [[2, 3], [2, 5]],
        3: [[3, 4], [3, 6]],
        5: [[5, 6]],
        6: [[6, 5]]
    },
    lastKey = 6,
    parts = [];

getParts();
parts.forEach(function (a) { console.log(JSON.stringify(a)); });
.as-console-wrapper { max-height: 100% !important; top: 0; }