Count non-empty end-leafs of a python dicitonary/array data structure - recursive algorithm?

Question

I'm looking for a function to find all the non-empty end-points of a kind of complex dictionary/array structure. I think that because I don't know the number of nested arrays or their locations, it would have to be recursive, and I just don't entirely get that way of thinking yet.

So for the nested dict:

x = {"top": {"middle" : [
                         {"nested": "value"},
                         {"nested":"val2"},
                         {"nested":""}
                        ],
            "last" : [
                         {"nested": [
                            {"first":1,"second":1},
                            {"first":0,"second":""}
                            ]
                            },
                         {"nested": [
                            {"first":1,"second":1},
                            {"first":1,"second":2}
                            ]
                            },
                         {"nested": [
                            {"first":1,"second":1},
                            {"first":"","second":""}
                            ]
                            }
                        ]
            },
      "other":1}

and variable "paths" named as follows, where ".XX" designates there is an array (in the style of variety.js):

vars = ["top.middle.XX.nested",
        "top.last.XX.nested.XX.first",
        "top.last.XX.nested.XX.second",
        "other"]

I'd like a function f(x,y) that can return...

f(x,"top.middle.XX.nested") = 2/3
f(x,"top.last.XX.nested.XX.first") = 5/6
f(x,"top.last.XX.nested.XX.second") = 4/6
f(x,"other") = 1

The problem for me seems to be trying to construct the tree as you go and where to put the counter for nulls. So, I don't quite understand how to record the counters or do recursion correctly.

Should maybe `["first":"","second":""]` be `{"first":"","second":""}`? — Hyperboreus, Aug 05 '13 at 23:11
Oh, I have a couple problems there, one sec, lemme revise more. — Mittenchops, Aug 05 '13 at 23:11
Next question: if `XX` denotes an array, why is the path `top.last.XX.nested.XX.first` and not `top.last.XX.nested.first`? Being `top.last.XX.nested` a dictionary. — Hyperboreus, Aug 05 '13 at 23:13
OK, now it is what I meant---thank you for pointing that out. — Mittenchops, Aug 05 '13 at 23:20
It sounds like you're doing something close to schema validation. I find tools like `voluptuous` very handy for this. — Justin, Aug 05 '13 at 23:20

Hyperboreus · Accepted Answer · 2013-08-05T23:52:33.387

Maybe this can guide you in the right direction. byPath collects the nested dictionary items. Once called, you can basically flatten out the resulting list and check if your condition is met (like elem != '' or not elem or whatever):

x = #your x as posted

def byPath (tree, path):
    try: head, tail = path.split ('.', 1)
    except: return tree [path]

    if head == 'XX': return [byPath (node, tail) for node in tree]
    else: return byPath (tree [head], tail)


print (byPath (x, 'top.middle.XX.nested') )
print (byPath (x, 'top.last.XX.nested.XX.first') )
print (byPath (x, 'top.last.XX.nested.XX.second') )
print (byPath (x, 'other') )

EDIT: Here the part for actually counting those elements that are not an empty string:

def count (result):
    if isinstance (result, list):
        total = 0
        positive = 0
        for e in result:
            r = count (e)
            total += r [1]
            positive += r [0]
        return (positive, total)
    else: return (0 if result == '' else 1, 1)

a = byPath (x, 'top.middle.XX.nested')
b = byPath (x, 'top.last.XX.nested.XX.first')
c = byPath (x, 'top.last.XX.nested.XX.second')
d = byPath (x, 'other')

for x in [a, b, c, d]: print (count (x) )

Putting everything together:

def f (tree, path):
    return count (byPath (tree, path) )

for path in ['top.middle.XX.nested', 'top.last.XX.nested.XX.first', 'top.last.XX.nested.XX.second', 'other']:
    print (path, f (x, path) )

That was basically it. Thank you. – Mittenchops Aug 06 '13 at 17:12 — Mittenchops, Aug 06 '13 at 17:12

Count non-empty end-leafs of a python dicitonary/array data structure - recursive algorithm?

1 Answers1

Linked