-
Notifications
You must be signed in to change notification settings - Fork 1
/
FamilyTree.py
203 lines (162 loc) · 6.09 KB
/
FamilyTree.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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
class Member(object):
def __init__(self, founder):
"""
founder: string
Initializes a member.
Name is the string of name of this node,
parent is None, and no children
"""
self.name = founder
self.parent = None
self.children = []
def __str__(self):
return self.name
def add_parent(self, mother):
"""
mother: Member
Sets the parent of this node to the `mother` Member node
"""
self.parent = mother
def get_parent(self):
"""
Returns the parent Member node of this Member
"""
return self.parent
def is_parent(self, mother):
"""
mother: Member
Returns: Boolean, whether or not `mother` is the
parent of this Member
"""
return self.parent == mother
def add_child(self, child):
"""
child: Member
Adds another child Member node to this Member
"""
self.children.append(child)
def is_child(self, child):
"""
child: Member
Returns: Boolean, whether or not `child` is a
child of this Member
"""
return child in self.children
class Family(object):
def __init__(self, founder):
"""
Initialize with string of name of oldest ancestor
Keyword arguments:
founder -- string of name of oldest ancestor
"""
self.names_to_nodes = {}
self.root = Member(founder)
self.names_to_nodes[founder] = self.root
def set_children(self, mother, list_of_children):
"""
Set all children of the mother.
Keyword arguments:
mother -- mother's name as a string
list_of_children -- children names as strings
"""
# convert name to Member node (should check for validity)
mom_node = self.names_to_nodes[mother]
# add each child
for c in list_of_children:
# create Member node for a child
c_member = Member(c)
# remember its name to node mapping
self.names_to_nodes[c] = c_member
# set child's parent
c_member.add_parent(mom_node)
# set the parent's child
mom_node.add_child(c_member)
def is_parent(self, mother, kid):
"""
Returns True or False whether mother is parent of kid.
Keyword arguments:
mother -- string of mother's name
kid -- string of kid's name
"""
mom_node = self.names_to_nodes[mother]
child_node = self.names_to_nodes[kid]
return child_node.is_parent(mom_node)
def is_child(self, kid, mother):
"""
Returns True or False whether kid is child of mother.
Keyword arguments:
kid -- string of kid's name
mother -- string of mother's name
"""
mom_node = self.names_to_nodes[mother]
child_node = self.names_to_nodes[kid]
return mom_node.is_child(child_node)
def cousin(self, a, b):
"""
Returns a tuple of (the cousin type, degree removed)
cousin type is an integer that is -1 if a and b
are the same node or if one is the direct descendent
of the other. Otherwise, cousin type is 0 or greater,
representing the shorter distance to their common
ancestor as described in the exercises above.
degree removed is the distance to the common ancestor
Keyword arguments:
a -- string that is the name of a
b -- string that is the name of b
"""
def parentList(member):
"""
Takes a member and returns a list of its parents.
member: string | The string used to access the Member object.
return: list of string | The list of the names of member's parents
"""
if member == str(self.root):
return [str(self.root)]
return [member] + parentList(str(self.names_to_nodes[member].get_parent()))
def intersect(a, b):
"""
Takes two lists and cuts them off one after the point they
intersect.
a: list | First list
b: list | Second list
return: (list, list) | The two lists after being modified
"""
for elem in a:
if elem in b:
return (a[:a.index(elem) + 1], b[:b.index(elem) + 1])
return ([], [])
aParents = parentList(a)
bParents = parentList(b)
aIntersected, bIntersected = intersect(aParents, bParents)
return (min(len(aIntersected) - 2, len(bIntersected) - 2),
abs(len(aIntersected) - len(bIntersected)))
f = Family("a")
f.set_children("a", ["b", "c"])
f.set_children("b", ["d", "e"])
f.set_children("c", ["f", "g"])
f.set_children("d", ["h", "i"])
f.set_children("e", ["j", "k"])
f.set_children("f", ["l", "m"])
f.set_children("g", ["n", "o", "p", "q"])
words = ["zeroth", "first", "second", "third", "fourth", "fifth", "non"]
## These are your test cases.
## The first test case should print out:
## 'b' is a zeroth cousin 0 removed from 'c'
t, r = f.cousin("b", "c")
print "'b' is a", words[t],"cousin", r, "removed from 'c'"
## For the remaining test cases, use the graph to figure out what should
## be printed, and make sure that your code prints out the appropriate values.
t, r = f.cousin("d", "f")
print "'d' is a", words[t],"cousin", r, "removed from 'f'"
t, r = f.cousin("i", "n")
print "'i' is a", words[t],"cousin", r, "removed from 'n'"
t, r = f.cousin("q", "e")
print "'q' is a", words[t], "cousin", r, "removed from 'e'"
t, r = f.cousin("h", "c")
print "'h' is a", words[t], "cousin", r, "removed from 'c'"
t, r = f.cousin("h", "a")
print "'h' is a", words[t], "cousin", r, "removed from 'a'"
t, r = f.cousin("h", "h")
print "'h' is a", words[t], "cousin", r, "removed from 'h'"
t, r = f.cousin("a", "a")
print "'a' is a", words[t], "cousin", r, "removed from 'a'"