-
-
Notifications
You must be signed in to change notification settings - Fork 209
/
MinMax.py
132 lines (113 loc) · 4.1 KB
/
MinMax.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
class Problem:
def __init__(self):
# it a tree that is represented in the form of nested dictionary
# where every key represents a node having child and last nodes
#Hacktoberfest2022
# without child are represented in a list
# First symmetrical tree with each node having 2 children
"""self.tree = {
'A': {
'B': {
'D':
[3, 8]
,
'E':
[6, 4]
},
'C': {
'F':
[2, 3]
,
'G':
[1, 2]
}
}
}"""
# Second symmetrical tree with each node having 3 children
'''self.tree = {
'A': {
'B': {
'E':[3, 8, 4]
,
'F':[6, 4, 1]
,
'G':[1, 2,-1]
},
'C': {
'H':[2, 3, 5]
,
'I':[1, 2, 0]
,
'J':[8, 2, 4]
},
'D': {
'K':[2, 3, 5]
,
'L':[1, 2, 7]
,
'M':[5, 4, 9]
}
}
}'''
# third unsymmetrical tree with different number of children
# that looks like this
# A
# / \
# B C
# / \ / | \
# D E F G H
# | /\ | / \ / | \
# 5 3 6 9 2 0 9 8 4
self.tree = {
'A': {
'B': {
'D': [5]
,
'E': [3, 6]
},
'C': {
'F': [9]
,
'G': [2, 0]
,
'H': [9, 8, 4]
}
}
}
def apply_min_max(self, current_subtree=None, min_max_chose=max):
"""
Recursive function that gets a tree stored as dictionary
and calls itself recursively to apply min max on the sub-tree
on each recursive call it gets back an integer value that tree should have on each node.
Each node is represented by a recursive scope
:param current_subtree: type dict
:param min_max_chose: is a function default value is max.
:return: an int
"""
if current_subtree is None:
current_subtree = self.tree
print('Min Max Started')
# list that contains integers that are returned from next recursive scope.
# is a min or max of child nodes.
returned_values = list()
# min_max_chose stores a function that alternates in every scope (has min and max values only)
# in one scope it is min and in next scope it is max
# inverting min_max_chose because it will apply on child scope or nodes
min_max_chose = max if min_max_chose == min else min
# base condition where node does not have further children and is represented as a list
if type(current_subtree) == list:
return min_max_chose(current_subtree)
# available_keys has values of all available keys i-e child node
available_keys = current_subtree.keys()
# we iterate over these keys to get child subtrees
for key in available_keys:
value = self.apply_min_max(current_subtree[key], min_max_chose)
returned_values.append(value)
print(f"Values {returned_values} are returned to {'max' if min_max_chose == min else 'min'} scope")
# return min or max depending on which scope it is.
return min_max_chose(returned_values)
def main():
p = Problem()
print(p.apply_min_max())
if __name__ == '__main__':
main()