I am trying to iterate through a multi-level, and varied-level dictionary.
I have an org char (dictionary) with the keys as people names, and values as either None or a dictionary with another org chart.
If the name has any values other than None they're a "leader", otherwise, they're "non-leader". Every first-level dictionary names are the leader's direct reports, and further through the nested dictionaries are the leader's indirect reports.
Given a name (string) and an org_chart (nested dictionary), I'd like to implement a function lookup_info, that outputs whether the name is a "leader" or "non-leader", how many direct reports they have, and how many indirect reports they have.
I'm not new to Python, but I'm stuck at the traversing (is this BFS or DFS) and how to use recursion here.
Here's an example:
ORG_CHART = {
"chloe" : {
"mark" : {
"tim" : {
"varun" : None,
"misha" : None
}
},
"julie" : None
},
"annie" : {
"jimmy" : {
"haily" : None,
"alex" : None
},
"helen" : {
"miley" : {
"stella" : {
"allie" : None
},
"tom" : None
}
}
},
"jenny" : None
}
def lookup(name, org_chart):
#TODO
return leadership_type, num_direct_reports, num_total_reports
name = "annie" should output: "leader", 2, 8
because annie has people reporting to her so she's a leader. She has 2 people directly in her values dict, so 2 direct reports, and 8 total people working under her.
name = "tom" should output: "non-leader", 0, 0
name = "miley" should output "leader", 2, 3
I've tried the following to recurse the nested dictionaries (not actually getting any info yet, but just trying to find the values in the dictionaries first, because the counting is the next step), but I'm stuck at this very first step. It's returning None of course if it hits any level above the first level that doesn't have a dictionary as it's values.
def lookup_info(name, org_chart):
def get_name_value(name, org_chart):
if org_chart != None:
for k, v in org_chart.items():
if k == name:
return k
else:
if v != None:
for i, j in v.items():
get_name_value(name, j)
name = get_name_value(name, org_chart)
return name
Any ideas please let me know, thank you!
CodePudding user response：
A quick and dirty solution would be to define some other helper functions, and recurse through the org_chart object:
def lookup(name: str, org_chart: dict):
it = _in(name, org_chart)
if not it:
return 'non-leader', 0, 0
return 'leader', len(it), _count(it)
def _count(o: dict):
if not o:
return 0
return len(o) sum(_count(v) for v in o.values())
def _in(name: str, o: dict):
if not o:
return None
if name in o:
return o[name]
for v in o.values():
res = _in(name, v)
if res:
return res
return None
Usage:
ORG_CHART = {
"chloe": {
"mark": {
"tim": {
"varun": None,
"misha": None
}
},
"julie": None
},
"annie": {
"jimmy": {
"haily": None,
"alex": None
},
"helen": {
"miley": {
"stella": {
"allie": None
},
"tom": None
}
}
},
"jenny": None
}
print(lookup('annie', ORG_CHART))
print(lookup('miley', ORG_CHART))
print(lookup('tom', ORG_CHART))
Out:
('leader', 2, 8)
('leader', 2, 3)
('non-leader', 0, 0)
CodePudding user response：
Recursion is a bit tricky to wrap the brain around, so here is a more verbose option which takes a naïve step-by-step through the process in a human readable manner.
Note that this does not account for duplicates or other edge cases and is certainly neither the shortest or most efficient method, but I think it should serve you well as a good jumping off point.
def lookup_info(name, org_chart):
# some local variables to hold our results
leadership_type = None
num_direct_reports = 0
num_total_reports = 0
def helper(obj, depth):
# declare our intent to use the variables from above as nonlocals
nonlocal leadership_type, num_direct_reports, num_total_reports
# if the value is None, we hit a leaf and should return
if obj is None:
return
# otherwise, iterate through the key value pairs
for key, value in obj.items():
# if we see the name in the keys, we proceed accordingly
if key == name:
if value is not None:
# mark as a leader, and recurse with increased depth noted in param
leadership_type = "leader"
helper(obj=value, depth=depth 1)
else:
# otherwise this is a non-leader, we can return
leadership_type = "non-leader"
return
elif depth == 1:
# at depth 1 we handle direct subordinates, and recurse
num_direct_reports = 1
num_total_reports = 1
helper(obj=value, depth=depth 1)
elif depth > 1:
# at depth > 1 we handle indirect subordinates, and recurse
num_total_reports = 1
helper(obj=value, depth=depth 1)
else:
# here we continue checking deeper into the structure to cover all other cases from depth 0
helper(obj=value, depth=0)
# run our helper with the appropriate defaults to start
helper(obj=org_chart, depth=0)
# finally return the thruple
return leadership_type, num_direct_reports, num_total_reports
CodePudding user response：
If computational cost is a matter and you expect to call your function with a significant number of individuals, I would rather advise to scan one time the whole org_chart and save the resulting values in a new dict like so:
def reports(d):
ret = {}
total_reports = 0
for k in d: # scan children one at the time
if d[k] is None: # if None, direct and indirect reports are 0
ret[k] = [0, 0]
total_reports = 1
else:
d_k, reports_son = reports(d[k]) # recursion on the son
ret = {**ret, **d_k} # merge final dict and son's one
ret[k] = [len(d[k]), reports_son - len(d[k])]
total_reports = reports_son 1
return ret, total_reports
The results are computed, which outputs a directory of the form name -> [direct reports, indirect reports]. Note that I did not add the "leader" field because it is redundant with a direct reports number of 0.
mapping = reports(ORG_CHART)[0]
print(mapping)
outputs:
{'varun': [0, 0],
'misha': [0, 0],
'tim': [2, 0],
'mark': [1, 2],
'julie': [0, 0],
'chloe': [2, 3],
'haily': [0, 0],
'alex': [0, 0],
'jimmy': [2, 0],
'allie': [0, 0],
'stella': [1, 0],
'tom': [0, 0],
'miley': [2, 1],
'helen': [1, 3],
'annie': [2, 6],
'jenny': [0, 0]}
And you can access the results in O(1).