Quokka Survival Strategies
Story
A small quokka colony in Western Australia is migrating and since these creatures are vulnerable, we’ve been tasked with helping them make their way to their new home. For safety reasons, the quokka colony travels together at all times and can only travel between specific locations. We model these locations as the vertices of an undirected graph and two vertices are connected by an edge if the colony can travel from one location to the other.
Since the quokkas need to eat every so often, every vertex has additional information on whether sufficient food is available at a certain location. The colony can move through a number of locations before needing food and we assume that both their starting location and intended destination have food. All other locations may or may not have food.
Please help the quokkas find a path from their current home to their destination such that they have sufficient food along the way.
Informally, our implementation should support the following operations:
find_path(s, t, k)
The main operation consists of finding a path from vertex s to vertex t such that from any location with food along this path we reach the next location with food in at most k steps.
Implement find_path(s, t, k) returning the list of vertices used in the path, or None if no path exists.
fix_edge(u, v) block_edge(u, v)
We may need to update the graph sometimes when a certain edge is blocked or becomes accessible again. Implement the block_edge(u, v) and fix_edge(u, v) functions that removes an existing edge (if exists), or adds a new edge to the graph (if exists).
exists_path_with_extra_food(s, t, k, x)
We also want to help the quokkas by placing some extra food ourselves. Implement a method exists_path_with_extra_food(s, t, k, x) that returns whether it is possible for the quokkas to make it from s to t along a path where from any location with the food we reach the next location with food in at most k steps, by placing food at most x new locations. In other words, is it possible to place food at x new locations such that afterward find_path(s, t, k) can find a path?
This assignment was inspired by Hamster Obstacle Mazes and Quokkas. No quokkas or hamsters were harmed in the production of this assignment. Credit to Andre for the assignment creation.
Visual Example
Given a graph:
* *
A---B---C---D---E
The find_path(A, E, 2) is a valid, achievable path because between A and C there are 2 hops, and C and E are two hops, so the Quokkas will survive. This will then return: [A, B, C, D, E].
Whereas find_path(A, E, 1) cannot be reached, because A to B is 1 hop, and the Quokkas will need food. So this returns None.
exists_path_with_extra_food(A, E, 1, 3) returns True, because adding 3 extra food to (at least) B, and D will make the path [A, B, C, D, E] achievable as there is food at least 1 hop away for each vertex.
Solution:
Graph:
Quokka Maze
===========
This file represents the quokka maze, a graph of locations where a quokka is
trying to find a new home.
Please help the quokkas find a path from their current home to their
destination such that they have sufficient food along the way!
*** Assignment Notes ***
This is the main file that will be interacted with during testing.
All functions to implement are marked with a `TODO` comment.
Please implement these methods to help the quokkas find their new home!
"""
from typing import List, Union
from vertex import Vertex
class QuokkaMaze:
"""
Quokka Maze
-----------
This class is the undirected graph class that will contain all the
information about the locations between the Quokka colony's current home
and their final destination.
We _will_ be performing some minor adversarial testing this time, so make
sure you're performing checks and ensuring that the graph is a valid simple
graph!
===== Functions =====
* block_edge(u, v) - removes the edge between vertex `u` and vertex `v`
* fix_edge(u, v) - fixes the edge between vertex `u` and `v`. or adds an
edge if non-existent
* find_path(s, t, k) - find a SIMPLE path from veretx `s` to vertex `t`
such that from any location with food along this simple path we
reach the next location with food in at most `k` steps
* exists_path_with_extra_food(s, t, k, x) - returns whether it’s
possible for the quokkas to make it from s to t along a simple path
where from any location with food we reach the next location with
food in at most k steps, by placing food at at most x new locations
===== Notes ======
* We _will_ be adversarially testing, so make sure you check your params!
* The ordering of vertices in the `vertex.edges` does not matter.
* You MUST check that `k>=0` and `x>=0` for the respective functions
* find_path (k must be greater than or equal to 0)
* exists_path_with_extra_food (k and x must be greater than or equal to
0)
* This is an undirected graph, so you don't need to worry about the
direction of traversing during your path finding.
* This is a SIMPLE GRAPH, your functions should ensure that it stays that
way.
* All vertices in the graph SHOULD BE UNIQUE! IT SHOULD NOT BE POSSIBLE
TO ADD DUPLICATE VERTICES! (i.e the same vertex instance)
"""
def __init__(self) -> None:
"""
Initialises an empty graph with a list of empty vertices.
"""
self.vertices = []
def add_vertex(self, v: Vertex) -> bool:
"""
Adds a vertex to the graph.
Returns whether the operation was successful or not.
:param v - The vertex to add to the graph.
:return true if the vertex was correctly added, else false
"""
# TODO implement me, please?
# if self.vertices.insert(v) = True:
# return True
# else:
# return False
if v is not None and v not in self.vertices:
self.vertices.append(v)
return True
else:
return False
def fix_edge(self, u: Vertex, v: Vertex) -> bool:
"""
Fixes the edge between two vertices, u and v.
If an edge already exists, then this operation should return False.
:param u - A vertex
:param v - Another vertex
:return true if the edge was successfully fixed, else false.
"""
# TODO implement me please.
# pass
if u is not None and v is not None:
if u not in v.edges or v not in u.edges:
u.add_edge(v)
return True
else:
return False
else:
return False
def block_edge(self, u: Vertex, v: Vertex) -> bool:
"""
Blocks the edge between two vertices, u and v.
Removes the edge if it exists.
If not, it should be unsuccessful.
:param u - A vertex
:param v - Another vertex.
:return true if the edge was successfully removed, else false.
"""
# TODO implement me, please!
# pass
if u is not None and v is not None:
if u in v.edges or v in u.edges:
u.rm_edge(v)
return True
else:
return False
else:
return False
def find_all_path(self, s: Vertex, t: Vertex, path=[]):
path = path + [s]
if s == t:
return [path]
if s not in self.vertices:
return []
paths = []
for vertex in s.edges:
if vertex not in path:
extended_paths = self.find_all_path(vertex, t, path)
for p in extended_paths:
paths.append(p)
return paths
def find_path(
self,
s: Vertex,
t: Vertex,
k: int
) -> Union[List[Vertex], None]:
"""
find_path returns a SIMPLE path between `s` and `t` such that from any
location with food along this path we reach the next location with food
in at most `k` steps
:type t: object
:param s - The start vertex for the quokka colony
:param t - The destination for the quokka colony
:param k - The maximum number of hops between locations with food, so
that the colony can survive!
:returns
* The list of vertices to form the simple path from `s` to `t`
satisfying the conditions.
OR
* None if no simple path exists that can satisfy the conditions, or
is invalid.
Example:
(* means the vertex has food)
* *
A---B---C---D---E
1/ find_path(s=A, t=E, k=2) -> returns: [A, B, C, D, E]
2/ find_path(s=A, t=E, k=1) -> returns: None
(because there isn't enough food!)
3/ find_path(s=A, t=C, k=4) -> returns: [A, B, C]
"""
# TODO implement me please
if s is None:
return None
if t is None:
return None
if k < 0:
return None
paths = self.find_all_path(s, t)
for path in paths:
step = -1
has_food = False
num = 0
for vertex in path:
if step != -1:
step = step + 1
if vertex.has_food:
has_food = True
num = num + 1
if step > k:
has_food = False
break
step = 0
if has_food:
return path
return None
def exists_path_with_extra_food(
self,
s: Vertex,
t: Vertex,
k: int,
x: int
) -> bool:
"""
Determines whether it is possible for the quokkas to make it from s to
t along a SIMPLE path where from any location with food we reach the
next location with food in at most k steps, by placing food at at most
x new locations.
:param s - The start vertex for the quokka colony
:param t - The destination for the quokka colony
:param k - The maximum number of hops between locations with food, so
that the colony can survive!
:param x - The number of extra foods to add.
:returns
* True if with x added food we can complete the simple path
* False otherwise.
Example:
(* means the vertex has food)
*
A---B---C---D---E
1/ exists_with_extra_food(A, E, 2, 0) -> returns: False
(because we can't get from A to E with k=2 and 0 extra food)
Vertex:
Vertex
=======
Represents a vertex in the maze, holds the information about other
connected vertices, and checks whether this vertex has food.
"""
class Vertex:
"""
Vertex represents a location in the quokka's quest to find food.
It contains the relevant information surrounding the location.
Attributes:
* self.has_food (bool) - indicates whether this location has food.
* self.edges (List[Vertex]) - list of connected vertices.
Functions:
* add_edge(self, v) - connects 'v' to this vertex by adding an edge.
* rm_edge(self, v) - removes the vertex 'v' from this vertex's edges,
breaking the connection between this vertex and 'v'.
"""
def __init__(self, has_food: bool) -> None:
"""
Initialises this vertex, by setting the attribute whether it has food.
:param has_food - boolean indicating whether this location has food.
"""
self.has_food = has_food
self.edges = []
def add_edge(self, v: 'Vertex') -> None:
"""
Add an edge between this vertex and vertex 'v'.
:param v - The vertex to add an edge between.
"""
# TODO implement me please!
#pass
if v is not None and v not in self.edges:
# List of Vertices as edges in a vertex are unordered
# Hence we need to update both Vertices
self.edges.append(v)
v.add_edge(self)
def rm_edge(self, v: 'Vertex') -> None:
"""
Removes the edge between this vertex and 'v'.
:param v - The vertex to remove from edges.
"""
# TODO implement me please!
#pass
if v is not None and v in self.edges:
# List of Vertices as edges in a vertex are unordered
# Hence we need to update both Vertices
self.edges.remove(v)
v.rm_edge(self)
#test
Graph Sample:
import unittest
from vertex import Vertex
from graph import QuokkaMaze
def should_be_equal(got, expected, func, message="Incorrect result returned"):
"""
Simple Assert Helper Function
"""
assert expected == got, \
f"[{func}] MSG: {message} [Expected: {expected}, got: {got}]"
def should_be_true(got, func, message="Incorrect result returned"):
"""
Simple assert helper
"""
assert got is not None, \
f"[{func}] MSG: {message} [Expected True, but got {got}]"
assert got is True, \
f"[{func}] MSG: {message} [Expected True, but got {got}]"
def should_be_false(got, func, message="Incorrect result returned"):
"""
Simple false checker
"""
assert got is not None, \
f"[{func}] MSG: {message} [Expected False, but got {got}]"
assert got is False, \
f"[{func}] MSG: {message} [Expected False, but got {got}]"
def check_edges(
u,
v,
exists
):
if exists:
assert u in v.edges, "Vertex not found in edge list"
assert v in u.edges, "Vertex not found in edge list"
else:
assert u not in v.edges, "Vertex found in edge list when it shouldn't"
assert v not in u.edges, "Vertex found in edge list when it shouldn't"
def check_path_should_match(
got,
expected,
func="maze.find_path",
message="Returned incorrect path"
):
"""
Checks the equality of the path returned.
"""
# Check length
assert got is not None, "Returned a `None` response when it shouldn't be."
should_be_equal(
len(got),
len(expected),
func,
"Path length did not match expected!"
)
# For each vertex, check path matches
for idx in range(len(expected)):
should_be_equal(
got[idx],
expected[idx],
func,
message + f"(index: {idx} failed)"
)
class TestSampleGraph(unittest.TestCase):
def test_can_add_vertex(self):
"""
Can we add a vertex?
"""
bert_the_vert = Vertex(True)
m = QuokkaMaze()
should_be_true(
m.add_vertex(bert_the_vert),
"maze.add_vertex",
"Failed to add valid vertex"
)
should_be_equal(
len(m.vertices),
1,
"maze.add_vertex"
)
# Can't add the same vertex twice!
should_be_false(
m.add_vertex(bert_the_vert),
"maze.add_vertex",
"You added a vertex that should not have been added"
)
should_be_equal(
len(m.vertices),
1,
"maze.add_vertex"
)
def test_can_fix_edge(self):
"""
Can we add an edge?
"""
A = Vertex(True)
C = Vertex(True)
E = Vertex(True)
m = QuokkaMaze()
should_be_true(
m.add_vertex(C),
"maze.add_vertex",
"Failed to add valid vertex"
)
should_be_true(
m.add_vertex(E),
"maze.add_vertex",
"Failed to add valid vertex"
)
should_be_true(
m.add_vertex(A),
"maze.add_vertex",
"Failed to add valid vertex"
)
should_be_true(
m.fix_edge(A, E),
"maze.fix_edge"
)
should_be_true(
m.fix_edge(C, E),
"maze.fix_edge"
)
# check the edges
check_edges(A, E, True)
check_edges(C, E, True)
check_edges(A, C, False)
# now add the edge between A and C
should_be_true(
m.fix_edge(A, C),
"maze.fix_edge"
)
check_edges(A, C, True)
def test_can_block_edge(self):
"""
Can we block/remove an edge?
"""
A = Vertex(True)
B = Vertex(True)
m = QuokkaMaze()
should_be_true(
m.add_vertex(A),
"maze.add_vertex"
)
should_be_true(
m.add_vertex(B),
"maze.add_vertex"
)
should_be_true(
m.fix_edge(A, B),
"maze.fix_edge"
)
check_edges(A, B, True)
should_be_true(
m.block_edge(A, B),
"maze.fix_edge"
)
check_edges(A, B, False)
def test_find_path_comment_example(self):
"""
Checks that we can find the path as shown in comments.
"""
# * *
# A -- B -- C -- D -- E
A = Vertex(False)
B = Vertex(False)
C = Vertex(True)
D = Vertex(False)
E = Vertex(True)
m = QuokkaMaze()
should_be_true(m.add_vertex(A), "maze.add_vertex")
should_be_true(m.add_vertex(B), "maze.add_vertex")
should_be_true(m.add_vertex(C), "maze.add_vertex")
should_be_true(m.add_vertex(D), "maze.add_vertex")
should_be_true(m.add_vertex(E), "maze.add_vertex")
should_be_true(m.fix_edge(A, B), "maze.fix_edge")
should_be_true(m.fix_edge(B, C), "maze.fix_edge")
should_be_true(m.fix_edge(C, D), "maze.fix_edge")
should_be_true(m.fix_edge(D, E), "maze.fix_edge")
# Example 1: find_path A, E, 2 => returns [A, B, C, D, E]
check_path_should_match(
m.find_path(A, E, 2),
[A, B, C, D, E],
)
# Example 2 - find path k=1, should return None!
should_be_true(
m.find_path(A, E, 1) is None,
"maze.find_path",
"Returned not `None` path when no valid path exists"
)
# Example 3 - large K
check_path_should_match(
m.find_path(A, C, 4),
[A, B, C],
)
def test_exists_path_sample_comments(self):
"""
Checks that the example in the comment can be run.
"""
# *
# A -- B -- C -- D -- E
A = Vertex(False)
B = Vertex(False)
C = Vertex(False)
D = Vertex(False)
E = Vertex(True)
m = QuokkaMaze()
should_be_true(m.add_vertex(A), "maze.add_vertex")
should_be_true(m.add_vertex(B), "maze.add_vertex")
should_be_true(m.add_vertex(C), "maze.add_vertex")
should_be_true(m.add_vertex(D), "maze.add_vertex")
should_be_true(m.add_vertex(E), "maze.add_vertex")
should_be_true(m.fix_edge(A, B), "maze.fix_edge")
should_be_true(m.fix_edge(B, C), "maze.fix_edge")
should_be_true(m.fix_edge(C, D), "maze.fix_edge")
should_be_true(m.fix_edge(D, E), "maze.fix_edge")
# Example 1 - A E 2 0
should_be_false(
m.exists_path_with_extra_food(A, E, 2, 0),
"maze.exists_path_with_extra_food",
"Cannot reach path with extra food, should be false."
)
# Example 2 - A E 2 1 -> true
should_be_true(
m.exists_path_with_extra_food(A, E, 2, 1),
"maze.exists_path_with_extra_food",
"Able reach path with extra added food, should be true."
)
# Example 3
should_be_true(
m.exists_path_with_extra_food(A, E, 1, 6),
"maze.exists_path_with_extra_food",
"Able to reach path with extra added food, should be true."
)
if __name__ == '__main__':
unittest.main()
Vertex Sample:
import unittest
from vertex import Vertex
def should_be_equal(got, expected, func, message="Incorrect result returned"):
"""
Simple Assert Helper Function
"""
assert expected == got, \
f"[{func}] MSG: {message} [Expected: {expected}, got: {got}]"
def should_be_true(got, func, message="Incorrect result returned"):
"""
Simple assert helper
"""
assert got is not None, \
f"[{func}] MSG: {message} [Expected True, but got {got}]"
assert got is True, \
f"[{func}] MSG: {message} [Expected True, but got {got}]"
def should_be_false(got, func, message="Incorrect result returned"):
"""
Simple false checker
"""
assert got is not None, \
f"[{func}] MSG: {message} [Expected False, but got {got}]"
assert got is False, \
f"[{func}] MSG: {message} [Expected False, but got {got}]"
class TestSampleVertex(unittest.TestCase):
def test_can_add_single_edge(self):
"""
Can we add a simple edge to a vertex?
"""
A = Vertex(True)
B = Vertex(True)
A.add_edge(B),
should_be_equal(
len(A.edges),
1,
"vertex.add_edge"
)
should_be_true(
B in A.edges,
"vertex.add_edge"
)
# Should not be able to add same edge.
A.add_edge(B),
should_be_equal(
len(A.edges),
1,
"vertex.add_edge"
)
def test_can_we_rm_edge(self):
"""
Can we remove the edge?
"""
A = Vertex(True)
B = Vertex(True)
C = Vertex(True)
A.add_edge(B),
A.rm_edge(B)
should_be_equal(
len(A.edges),
0,
"vertex.rm_edge"
)
# Shouldn't be able to remove an edge that doesn't exist
A.add_edge(C)
A.rm_edge(B)
should_be_equal(
len(A.edges),
1,
"vertex.rm_edge"
)
if __name__ == '__main__':
unittest.main()