Presentation : Among Us - Mini problem¶
This mini-problem is available online: ADSA Project.
You should definitely go on Google Collab try the code.
The subject can also be downloaded here. And this is the report we've submitted to the computer science department.
Basically, this is about organizing a giant tournament of Among Us with the best data structure, setting up the best strategies to demask impostor using our graph theory skills. So here is the code we worked on to achieve this. Don't hesitate to copy the notebook to run it.
NB: Some functions are interactive.
This job has been done by ADJARIAN Stéphan & LEBLANC César.
Step 1¶
import random
import numpy as np
class Player:
"""Create nodes that represent players with their information."""
def __init__(self, player):
self.player = player
self.name = player["name"]
self.impostor = player["impostor"] # True or False
self.scores = player["scores"]
self.score = player["scores"][0]
self.info = player["name"] + " " + str(player["scores"][0])
self.left = None
self.right = None
self.height = 1
"""Some nice display methods found on geeksforgeek blog."""
def display(self):
lines, *_ = self._display_aux()
for line in lines:
print(line)
def _display_aux(self):
if self.right is None and self.left is None:
line = '%s' % self.info
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle
if self.right is None:
lines, n, p, x = self.left._display_aux()
s = '%s' % self.info
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
shifted_lines = [line + u * ' ' for line in lines]
return [first_line, second_line] + \
shifted_lines, n + u, p + 2, n + u // 2
if self.left is None:
lines, n, p, x = self.right._display_aux()
s = '%s' % self.info
u = len(s)
first_line = s + x * '_' + (n - x) * ' '
second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
shifted_lines = [u * ' ' + line for line in lines]
return [first_line, second_line] + \
shifted_lines, n + u, p + 2, u // 2
left, n, p, x = self.left._display_aux()
right, m, q, y = self.right._display_aux()
s = '%s' % self.info
u = len(s)
first_line = (x + 1) * ' ' \
+ (n - x - 1) * '_' \
+ s + y * '_' \
+ (m - y) * ' '
second_line = x * ' ' + '/' \
+ (n - x - 1 + u + y) * ' ' \
+ '\\' + (m - y - 1) * ' '
if p < q:
left += [n * ' '] * (q - p)
elif q < p:
right += [m * ' '] * (p - q)
zipped_lines = zip(left, right)
lines = [first_line, second_line] \
+ [a + u * ' ' + b for a, b in zipped_lines]
return lines, n + m + u, max(p, q) + 2, n + u // 2
"""AVL tree class with nodes containing dictionnary with player's info."""
class AVLTree(object):
"""Recursive function to insert nodes in our AVL tree."""
def insert_player(self, root, player):
# Since we passed a node in argument and not a key
# we have to retrieve beforehand the key value
score = player.score
# Step 1 - Perform normal BST
if root is None:
return player
elif score < root.score:
root.left = self.insert_player(root.left, player)
else:
root.right = self.insert_player(root.right, player)
# Step 2 - Update the height of the ancestor node
root.height = 1 + max(self.get_height(root.left),
self.get_height(root.right))
# Step 3 - Get the balance factor
balance_factor = self.get_balance(root)
# Step 4 - If the node is unbalanced, then try out the 4 cases
# Case 1 - Left Left
if balance_factor > 1 and score <= root.left.score:
return self.right_rotate(root)
# Case 2 - Right Right
if balance_factor < -1 and score >= root.right.score:
return self.left_rotate(root)
# Case 3 - Left Right
if balance_factor > 1 and score > root.left.score:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
# Case 4 - Right Left
if balance_factor < -1 and score < root.right.score:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
"""Delete a node in our AVL tree."""
def delete_player(self, root, player):
score = player.score
if not root:
return root
elif score < root.score:
root.left = self.delete_player(root.left, player)
elif score > root.score:
root.right = self.delete_player(root.right, player)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.get_min_value_player(root.right)
root.val = temp.player
root.right = self.delete_player(root.right, temp.player)
if root is None:
return root
root.height = 1 + max(self.get_height(root.left),
self.get_height(root.right))
balance = self.get_balance(root)
# If the deletion unbalanced the tree we have
# to rebalance by performing rotations
if balance > 1 and self.get_balance(root.left) >= 0:
return self.right_rotate(root)
if balance < -1 and self.get_balance(root.right) <= 0:
return self.left_rotate(root)
if balance > 1 and self.get_balance(root.left) < 0:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
if balance < -1 and self.get_balance(root.right) > 0:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
"""Perform left rotation."""
def left_rotate(self, player):
right = player.right
left = right.left
right.left = player
player.right = left
player.height = 1 + max(self.get_height(player.left),
self.get_height(player.right))
right.height = 1 + max(self.get_height(right.left),
self.get_height(right.right))
return right
"""Perform right rotation."""
def right_rotate(self, player):
left = player.left
right = left.right
left.right = player
player.left = right
player.height = 1 + max(self.get_height(player.left),
self.get_height(player.right))
left.height = 1 + max(self.get_height(left.left),
self.get_height(left.right))
return left
"""Return the height of the tree."""
def get_height(self, root):
if not root:
return 0
return root.height
"""Return the balance factor of a node."""
def get_balance(self, root):
if not root:
return 0
return self.get_height(root.left) - self.get_height(root.right)
"""Return leftmost node which is the smallest value in the tree."""
def get_min_value_player(self, root):
if root is None or root.left is None:
return root
else:
Get_min_value_player(root.left)
1. Propose a data structure to represent a Player and its Score¶
"""We create 100 impostors named from player_1 to player_100.
At the beginning they all have a mean score of 0 and they aren't impostor."""
players = []
for x in range(1, 101):
player = {"name": "player_{}".format(x), "scores": [0], "impostor": False}
players.append(player)
2. Propose a most optimized data structures for the tournament¶
(called database in the following questions)
"""Create an AVL Tree and insert every player in it."""
tree = AVLTree()
root_tree = None
for player in players:
root_tree = tree.insert_player(root_tree, Player(player))
root_tree.display()
3. Present and argue about a method that randomize player score at each game¶
(between 0 point to 12 points)
"""Randomize players score."""
def randomize_score(players):
for player in players:
# We add a random score to the list of scores
player["scores"].append(random.randint(0,12))
# We must then update the mean score of the player,
# which is the first cell of the list
player["scores"][0] = round(np.mean(player["scores"][1:]),2)
return players
4. Present and argue about a method to update Players score and the database¶
# We choose to traverse the Tree in-order so that we get
# all players in a ascending order (from worst to best).
players = []
"""In order traversing."""
def print_inorder(root):
if root:
print_inorder(root.left)
# print(root.info)
player = {"name": root.name,
"scores": root.scores,
"impostor": root.impostor}
players.append(player)
print_inorder(root.right)
print_inorder(root_tree)
# Once they played a game, we have to update their score
print(players)
players = randomize_score(players)
print(players)
# We can then re-insert them in the tournament.
tree = AVLTree()
root_tree = None
for player in players:
root_tree = tree.insert_player(root_tree, Player(player))
root_tree.display()
5. Present and argue about a method to create random games based on the database¶
# We create 10 AVL Trees (because there are still 100 players)
roots = []
for x in range(10):
roots.append(None)
trees = []
for x in range(10):
trees.append(AVLTree())
players = []
print_inorder(root_tree)
# The key of the dictionnary is the number of the tree.
# The value of each key is the number of player in this tree.
dictionary = {0: 0, 1: 0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0}
for i in range(len(players)):
# We choose a random tree in which we place the player
choice = random.choice(tuple((dictionary.keys())))
# We increment the value of the associated key in the dictionnary
dictionary[choice] += 1
# If there are now 10 players in a game
if dictionary[choice] == 10:
# We remove this game from the choices
dictionary.pop(choice)
# We insert the player in this game
roots[choice] = trees[choice].insert_player(roots[choice], Player(players[i]))
for i in range(10):
roots[i].display()
6. Present and argue about a method to create games based on ranking¶
players = []
print_inorder(root_tree)
# This time we create a number of games based on the number of remaining players.
roots = []
for x in range(int(len(players) / 10)):
roots.append(None)
trees = []
for x in range(int(len(players) / 10)):
trees.append(AVLTree())
count = 0
current = 0
# This time we want to put the best players together in order.
for i in range(len(players)):
# When a game is full we go to the next game and continue
if count == 10:
count = 0
current += 1
roots[current] = trees[current].insert_player(roots[current], Player(players[i]))
count += 1
for i in range(int(len(players) / 10)):
roots[i].display()
7. Present and argue about a method to drop the players and to play game until the last 10 players¶
"""You have to run this cell the number of times you want to drop 10 players.
For example if you want to remove 10 players just run it once. However if you
want to remove all the players, you have to run this cell 9 times (to remove
90 players). Don't be afraid of clicking fast, there is a security and you
won't be able to remove all the players. It will stop when 10 players are
remaining and you won't be able to remove more."""
players = []
print_inorder(root_tree)
if len(players) > 10:
# We remove the 10 players with the worst score
players = players[10:]
tree = AVLTree()
root_tree = None
for player in players:
root_tree = tree.insert_player(root_tree, Player(player))
root_tree.display()
8. Present and argue about a method which display the TOP10 players and the podium after the final game.¶
players = []
print_inorder(root_tree)
for i in range(10):
print(str(10-i) + " : " + players[i]["name"] + " with an average of " + str(players[i]["scores"][0]) + " points")
STEP 2¶
4. Implement the algorithm and show a solution.¶
"""To create the adjacency matrix, we create a square matrix of dimensions
rooms x rooms (the number of rooms being 14 in our case). Then we put 0 in
the diagonal. Now we look only at the upper side of the diagonal. If the
intersection of the line and the column represents two rooms that are
connected by a path, we put a 1. For example, if the room 1 and the room 3
are connected, we put a "1" on the intersection of line 1 and column 3.
Otherwise, if there is no direct path, we put a 0. Then, because our graph
is undirected (if someone can go from room A to room B then he can go from
room B to room A), we make the matrix symetrical. For example, if we have
a 1 on the intersection of line 1 and column 3, then we put a 1 on the
intersection of line 3 and column 1."""
adjacency_matrix = [[0, 1, 0, 0, 1, 1, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 1, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 1, 1],
[0, 0, 1, 0, 0, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 1, 0, 0]]
impostor1 = [1, 4, 5]
# We will not visit player that we already
# know are possible impostor or dead player
neighborToVisit = [i for i in range(10) if i not in impostor1 and i != 0]
solution = []
# For every possible impostor
for impostor in impostor1:
# We look at all players that are not dead nor a possible impostor
for i in neighborToVisit:
# If their path didn't cross
if adjacency_matrix[i][impostor] == 0:
# We add the tuple of the impostor and this
# player to the possible set of impostors.
solution.append([impostor, i])
solution
STEP 3¶
2. Argue about a pathfinding algorithm to implement.¶
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
"""Just to print the matrix in a "nice way"."""
def print_solution_floyd_warshall(self, distance):
for i in range(self.vertices):
for j in range(self.vertices):
if distance[i][j] == 999:
print("! ", end=" ")
else:
print(distance[i][j], end=" ")
print(" ")
"""Print and return the matrix containing all the distance between rooms."""
def floyd_warshall(self):
distance = list(map(lambda i: list(map(lambda j: j, i)), self.graph))
for k in range(self.vertices):
for i in range(self.vertices):
for j in range(self.vertices):
# We want to find the shortest path between room i
# and room j (we round it so it's still readable)
distance[i][j] = round(min(distance[i][j],
distance[i][k] + distance[k][j]),
2)
for i in range(self.vertices):
for j in range(i, self.vertices):
# If we find a shorter path than what we had
if distance[i][j] < distance[j][i]:
# This becomes the shortest path
distance[j][i] = distance[i][j]
else:
distance[i][j] = distance[j][i]
self.print_solution_floyd_warshall(distance)
return distance
3. Implement the method and show the time to travel for any pair of rooms for both models.¶
# Create the graph with 14 rooms.
g_crew = Graph(14)
# We use the adjacency matrix of the crewmates
g_crew.graph = [
[0, 8.31, 8.31, 6.52, 999, 999, 999, 999, 999, 999, 999, 999, 999, 999],
[8.31, 0, 9.54, 7.75, 9.7, 12.33, 999, 999, 999, 999, 999, 999, 999, 999],
[8.31, 9.54, 0, 7.75, 999, 999, 11.77, 13.25, 999, 999, 999, 999, 999, 999],
[6.52, 7.75, 7.75, 0, 999, 999, 999, 999, 999, 999, 999, 999, 999, 999],
[999, 9.7, 999, 999, 0, 10.01, 999, 999, 999, 999, 999, 999, 999, 999],
[999, 12.33, 999, 999, 10.01, 0, 999, 9.87, 999, 9.98, 999, 7.54, 999, 999],
[999, 999, 11.77, 999, 999, 999, 0, 9.34, 999, 999, 999, 999, 999, 999],
[999, 999, 13.25, 999, 999, 9.87, 9.34, 0, 8.21, 7.71, 999, 999, 999, 8.6],
[999, 999, 999, 999, 999, 999, 999, 8.21, 0, 999, 999, 999, 999, 5.99],
[999, 999, 999, 999, 999, 9.98, 999, 7.71, 999, 0, 999, 999, 999, 999],
[999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 0, 5.82, 9.36, 12.92],
[999, 999, 999, 999, 999, 7.54, 999, 999, 999, 999, 5.82, 0, 10.16, 13.72],
[999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 9.36, 10.16, 0, 11.6],
[999, 999, 999, 999, 999, 999, 999, 8.6, 5.99, 999, 12.92, 13.72, 11.6, 0]]
# Store the result for crewmates graph
distance_between_rooms_crewmates = g_crew.floyd_warshall()
# Create the graph with 14 rooms.
g_impostors = Graph(14)
# We use the adjacency matrix of the impostors.
g_impostors.graph = [
[0, 1, 1, 6.52, 999, 999, 999, 999, 999, 999, 999, 999, 999, 999],
[1, 0, 9.54, 7.75, 9.7, 12.33, 999, 999, 999, 999, 999, 999, 999, 999],
[1, 9.54, 0, 7.75, 999, 999, 11.77, 13.25, 999, 999, 999, 999, 999, 999],
[6.52, 7.75, 7.75, 0, 1, 999, 1, 999, 999, 999, 999, 999, 999, 999],
[999, 9.7, 999, 1, 0, 10.01, 1, 999, 999, 999, 999, 999, 999, 999],
[999, 12.33, 999, 999, 10.01, 0, 999, 9.87, 999, 1, 999, 7.54, 999, 1],
[999, 999, 11.77, 1, 1, 999, 0, 9.34, 999, 999, 999, 999, 999, 999],
[999, 999, 13.25, 999, 999, 9.87, 9.34, 0, 8.21, 7.71, 999, 999, 999, 8.6],
[999, 999, 999, 999, 999, 999, 999, 8.21, 0, 999, 999, 999, 999, 5.99],
[999, 999, 999, 999, 999, 1, 999, 7.71, 999, 0, 999, 999, 999, 1],
[999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 0, 5.82, 9.36, 12.92],
[999, 999, 999, 999, 999, 7.54, 999, 999, 999, 999, 5.82, 0, 1, 13.72],
[999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 9.36, 1, 0, 1],
[999, 999, 999, 999, 999, 1, 999, 8.6, 5.99, 1, 12.92, 13.72, 1, 0]]
# Store the result for impostors graph
distance_between_rooms_impostors = g_impostors.floyd_warshall()
Here we provide a user friendly method to know the distance between rooms in both case.
print("Please input the rooms you want to know the \
in between distance (an int between 0 and 13):")
# Inputs
while True:
print("Room 1 =>")
try:
room_one = int(input())
if room_one in range(14):
break
else:
print("Value not in range(0,14). Try again.")
except:
print("Value not an int. Try again.")
while True:
print("Room 2 =>")
try:
room_two = int(input())
if room_two in range(14):
break
else:
print("Value not in range(0,14). Try again.")
except:
print("Value not an int. Try again.")
print("Is it for crewmates (enter yes or anything else for no)?")
choice = input()
# For crewmates choice
validate = ["y", "ye", "yes", "Y", "Ye", "Yes", "YES", "YE",
"o", "ou", "oui", "O", "Ou", "Oui", "OUI", "OU"]
# Print result
if choice in validate: # Yes
print("The distance between room {0} and {1} \
for crewmates is about {2}cm or about {2}s." \
.format(room_one,
room_two,
distance_between_rooms_crewmates[room_one][room_two]))
else:
print("The distance between room {0} and {1} \
for impostors is about {2}cm or about {2}s." \
.format(room_one,
room_two,
distance_between_rooms_impostors[room_one][room_two]))
STEP 4¶
# Install dependencies
! apt-get install -y graphviz-dev
! pip install pygraphviz
! pip install mpld3
4. Implement the algorithm and show a solution¶
import numpy as np
from math import inf
# For better graph plots
import matplotlib.pyplot as plt
import networkx as nx
from networkx.drawing.nx_agraph import graphviz_layout
class Graph:
"""We init the adjacency with inf value and then
values in the matrix with the add_edge function."""
def __init__(self, nb_node=0):
self.adjacency_matrix = np.ones((nb_node, nb_node)) * inf
self.label = [""] * nb_node
"""Modify the adjacency matrix with the input nodes and weight"""
def add_edge(self, node_one, node_two, weight=1.0):
self.adjacency_matrix[node_one, node_two] = weight
self.adjacency_matrix[node_two, node_one] = weight
"""Return the list of available neighbors of
one node to construct the hamiltonian path"""
def get_neighbors(self, node):
neighbors = []
for i in range(self.nb_node):
if i != node and self.adjacency_matrix[i, node] != inf:
neighbors.append(i)
return neighbors
"""Return all the hamilton paths from all vertices
sorted with respect to the travelled distance."""
def get_all_hamilton_paths(self):
all_path = []
for i in range(self.nb_node):
graph.get_hamilton_paths([i], all_path)
return sorted(all_path, key=lambda x: x[1])
"""Return all the hamilton paths from one vertex."""
def get_hamilton_paths(self, path, all_path):
# The path isn't valid, we have two times the same node in the path
if path.count(path[-1]) > 1:
return None
# The path is valid, thus added to all paths
if len(path) == self.nb_node:
# Compute the score of the path
travelled_distance = 0
for i in range(len(path) - 1):
travelled_distance += self.adjacency_matrix[path[i]][path[i + 1]]
all_path.append([path, travelled_distance])
return None
neighbors = self.get_neighbors(path[-1])
for n in neighbors:
new_path = path + [n]
self.get_hamilton_paths(new_path, all_path)
def __getattr__(self, key):
if key == "nb_node":
return self.adjacency_matrix.shape[0]
"""Plot the graph thanks to the adjacency matrix. Encoded here for
more visibility but can easily be retrieved from class graph
(just need to replace inf by zeros)"""
def plot(self):
matrix = [[0, 12.33, 9.7, 0, 0, 0, 0, 0, 0, 0, 0, 9.54, 8.31, 7.75],
[0, 0, 10.01, 7.54, 0, 0, 0, 0, 9.87, 9.98, 0, 0, 0, 0],
[9.7, 10.01, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 7.54, 0, 0, 5.82, 10.16, 13.72, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 5.82, 0, 9.36, 12.92, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 10.16, 9.36, 0, 11.6, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 13.72, 12.92, 11.6, 0, 5.99, 8.6, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 5.99, 0, 8.21, 0, 0, 0, 0, 0],
[0, 9.87, 0, 0, 0, 0, 8.6, 8.21, 0, 7.71, 9.34, 13.25, 0, 0],
[0, 9.98, 0, 0, 0, 0, 0, 0, 7.71, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 9.34, 0, 0, 11.77, 0, 0],
[9.54, 0, 0, 0, 0, 0, 0, 0, 13.25, 0, 11.77, 0, 8.31, 7.75],
[8.31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8.31, 0, 6.52],
[7.75, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7.75, 6.52, 0]]
# Create networks graph using the adjacency matrix
G = nx.from_numpy_matrix(np.matrix(matrix))
# Retrieve coordinates
pos = graphviz_layout(G, prog='sfdp')
# Rescale plot
plt.figure(1, figsize=(12, 8))
# Plot
nx.draw_networkx(G, pos, font_weight='bold',
with_labels=False, width=2)
# Add Vertex Label
nx.draw_networkx_labels(G, pos, {0: '1', 1: '5', 2: '4', 3: '11',
4: '10', 5: '12', 6: '13', 7: '8',
8: '7', 9: '9', 10: '6', 11: '2',
12: '0', 13: '3'})
# Add Edge Label
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
# Save snapshot
plt.savefig("graph.pdf")
graph = Graph(14)
graph.add_edge(0, 1, 8.31)
graph.add_edge(0, 2, 8.31)
graph.add_edge(0, 3, 6.52)
graph.add_edge(1, 2, 9.54)
graph.add_edge(1, 3, 7.75)
graph.add_edge(1, 4, 9.7)
graph.add_edge(1, 5, 12.33)
graph.add_edge(2, 3, 7.75)
graph.add_edge(2, 6, 11.77)
graph.add_edge(2, 7, 13.25)
graph.add_edge(4, 5, 10.01)
graph.add_edge(5, 7, 9.87)
graph.add_edge(5, 9, 9.98)
graph.add_edge(5, 11, 7.54)
graph.add_edge(6, 7, 9.34)
graph.add_edge(7, 8, 8.21)
graph.add_edge(7, 9, 7.71)
graph.add_edge(7, 13, 8.6)
graph.add_edge(8, 13, 5.99)
graph.add_edge(10, 11, 5.82)
graph.add_edge(10, 12, 9.36)
graph.add_edge(10, 13, 12.92)
graph.add_edge(11, 13, 13.72)
graph.add_edge(11, 12, 10.16)
graph.add_edge(12, 13, 11.6)
# Plot
graph.plot()
# For all hamiltonian paths in the graph sorted
# in function of the travelled distance
graph.get_all_hamilton_paths()
# For all hamiltonian paths from one vertex
all_path = []
graph.get_hamilton_paths([7], all_path) # here you choose the node '4'
for path in all_path:
print(path)
! jupyter nbconvert --to html "LEBLANC_&_ADJARIAN_Among_Us.ipynb"