Finding optimal nodes whose presence satisfies nested JSON logic

Question

Below is the JSON, I am using to generate following UI:

{
    "Text" : "1. Parent group"
    "Logic" : "all of the following",
    "Id":"1" //some unique id
    "children": [
        {
            "Text' : "1.1 Level Child group"
            "Logic' : "1 or more of the following",
            "Id':"1.1" //some unique id,
            "children" :  [
                {
                    "Text' : "1.1.1 Level Child group"
                    "Logic' : "all of the following",
                    "Id':"1.1.1" //some unique id,
                    "children": [
                        {
                            "Text' : "1.1.1.1 Level Child"
                            "Id':"1.1.1.1" //some unique id,

                        },
                        {
                            "Text' : "1.1.1.2 Level Child"
                            "Id':"1.1.1.2" //some unique id,
                            "Logic" : "one or more of the following",
                            "children" : [
                                      { 
                                      "Text": "1.1.1.2.1 Level Child", 
                                      "Id": "1.1.1.2.1" 
                                      }, 
                                      { 
                                     "Text": "1.1.1.2.2 Level Child", 
                                      "Id": "1.1.1.2.2" 
                                      }, 
                              ]
                        }
                    ]
                },
                {
                    "Text' : "1.1.2 Level Child group"
                    "Id':"1.1.2" //some unique id,
                },
                {
                    "Text' : "1.1.3 Level Child group"
                    "Id':"1.1.3" //some unique id,
                },
                {
                    "Text' : "1.1.4 Level Child group"
                    "Logic' : "one or more of the following",
                    "Id':"1.1.4" //some unique id,
                    "children": [
                        {
                            "Text' : "1.1.4.1 Level Child"
                            "Id':"1.1.4.1" //some unique id,
                        },
                        {
                            "Text' : "1.1.4.2 Level Child"
                            "Id':"1.1.4.2" //some unique id,
                        }
                    ]
                },
                {
                    "Text' : "1.1.5 Level Child group"
                    "Logic' : "all of the following",
                    "Id':"1.1.5" //some unique id,
                    "children": [
                        {
                            "Text' : "1.1.5.1 Level Child"
                            "Id':"1.1.5.1" //some unique id,
                        },
                        {
                            "Text' : "1.1.5.2 Level Child"
                            "Id':"1.1.5.2" //some unique id,
                        }
                    ]
                }

            ]
        },
        {
            "Text" : "1.2 Level Child"
            "Id":"1.2" //some unique id
        }
    ]
}

 1. Parent group (all of the following)

    1.1 Level Child group (1 or more )

        1.1.1 Level Child group (all of the following)
            1.1.1.1 Level Child // selectable
            1.1.1.2 Level Child // selectable

        1.1.2 Level Child   // selectable

        1.1.3 Level Child  // selectable

        1.1.4 Level Child group (one or more of the following)
            1.1.4.1 Level Child  // selectable
            1.1.4.2 Level Child  // selectable

        1.1.5 Level Child group (all of the following)
            1.1.5.1 Level Child  // selectable
            1.1.5.2 Level Child  // selectable

    1.2 Level Child   // selectable

Node working logic:

only nodes with no children can be selected by the user.
Node is implicitly selected if the Logic is "all of the following" if and only if all its nested children are selected
Node is implicitly selected if the logic is "n or more of the following" if only if its "n" nested children are selected

Scenario: If the user selects 1.1.2(it implicitly satisfies 1.1) and 1.2 then "1. parent group" is "Met", so it is selected(makes the whole group met);

Scenario: If the user selects 1.1.1.1, the user has to select 1.1.1.2 so that 1.1.1 is "Met" and selecting 1.2, will make the whole group as "Met".

Actual need is to find the optimal ids when "parent group is not met":

If the selecting any nodes and the top most parent group is still not "met". Then On a button click, I need to find and return the optimal node ids whose presence would have made the "parent group" to be "Met".

NOTE : when finding the optimal node ids we should importance to child groups if any of its children are selected.

For eg:

If only 1.2 is selected by the user, the fastest way to make the "parent group" to met is to select 1.1.2. But if 1.1.1 has any children selected, then I should give precedence to 1.1.1 node, as result I need to return following ids: [ 1.1.1.2, 1.1.1, 1.1 ]

Not sure what type of algorithm, I should be using to solve this problem.

you may start by adding valid data. how do you know if a node is selected? — Nina Scholz
every time a node is selected, I maintain the node id in an array. — Praveen
Let us say the user selects, "1.2 Level Child" node. All I do is store the node "Id" of the particular node. It would look like this : ["1.2"]. If you want a property to be added called "selected":true or false based on the node being selected or deselected. I can do it. — Praveen
if a user select something where do you get the selected nodes from? — Nina Scholz

Nina Scholz Nina Scholz · Accepted Answer · 2020-03-26T22:23:23

Here a short approach by having a look to the constraints, which are now in the data set metioned with q: 'some' or q: 'every'.

function select(node, selected) {

    function iter(node) {
        if (!node.children) return [node.Id];
		
        var temp = node.children.map(iter);

        if (node.q === 'every') return [...temp.flat(), node.Id];

        var filtered = temp.filter(a => a.some(v => selected.includes(v)));
        if (filtered.length) return [...filtered.flat(), node.Id];

        return [...temp.reduce((a, b) => b.length < a.length ? b : a), node.Id];
    }

    return iter(node).filter(v => !selected.includes(v));
}

var data = { q: 'every', Text: "1. Parent group", Logic: "all of the following", Id: "1", children: [{ q: 'some', Text: "1.1 Level Child group", Logic: "1 or more of the following", Id: "1.1", children: [{ q: 'every', Text: "1.1.1 Level Child group", Logic: "all of the following", Id: "1.1.1", children: [{ Text: "1.1.1.1 Level Child", Id: "1.1.1.1" }, { Text: "1.1.1.2 Level Child", Id: "1.1.1.2" }] }, { Text: "1.1.2 Level Child group", Id: "1.1.2" }, { Text: "1.1.3 Level Child group", Id: "1.1.3" }, { q: 'some', Text: "1.1.4 Level Child group", Logic: "one or more of the following", Id: "1.1.4", children: [{ Text: "1.1.4.1 Level Child", Id: "1.1.4.1" }, { Text: "1.1.4.2 Level Child", Id: "1.1.4.2" }] }, { q: 'every', Text: "1.1.5 Level Child group", Logic: "all of the following", Id: "1.1.5", children: [{ Text: "1.1.5.1 Level Child", Id: "1.1.5.1" }, { Text: "1.1.5.2 Level Child", Id: "1.1.5.1" }] }] }, { Text: "1.2 Level Child", Id: "1.2" }] };

console.log(select(data, ["1.2"]));
console.log(select(data, ["1.2", "1.1.1.1"]));
console.log(select(data, ["1.1.1.1"]));

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

Finding optimal nodes whose presence satisfies nested JSON logic

1 Answers