-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathcelebrity_problem.py
More file actions
executable file
·57 lines (36 loc) · 954 Bytes
/
Copy pathcelebrity_problem.py
File metadata and controls
executable file
·57 lines (36 loc) · 954 Bytes
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
#!/usr/bin/env python2.7
from stack import Stack
from node import Node
s = Stack()
MATRIX = [ [ 0, 0, 0, 0 ],
[ 0, 0, 1, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 1, 0 ] ]
# return True or False based on if a knows b or not
def knows(a, b):
if MATRIX[a][b] == 1:
return True
else:
return False
def find_celebrity(n):
for i in range(n):
s.push(Node(i))
while s.count > 1:
a = s.pop()
b = s.pop()
if not knows(a.data, b.data) and knows(b.data, a.data):
s.push(Node(a.data))
elif not knows(b.data, a.data) and knows(a.data, b.data):
s.push(Node(b.data))
if not s.is_empty():
c = s.pop()
return c.data
else:
return -1
if __name__ == "__main__":
n = 4
result = find_celebrity(n)
if result == -1:
print "no celebrity"
else:
print "celebrity = " + str(result)