1 Location Optimisation
(4 marks + 1 mark for documentation)
Your company is planning to open a kiosk in a new city and want to find the perfect location for
it. The streets of that city form a perfect grid and it is only possible to move along the streets.
You are given a set of n relevant points (x1, y1),(x2, y2),...,(xn, yn), which are all intersections
in the grid. Your goal is to compute the coordinates (x, y) of an optimal intersection to open
your kiosk such that Pn
i=1(|x
xi| + |y
yi|) is minimal.
In the example below, if the relevant points are painted in blue, then the red point is one
optimal solution, and the total distance from it to all relevant points is 35.
1.1 Input
Your ideal place finder is a Python function ideal_place(relevant), where relevant =
[[x1, y1], [x2, y2], [x3, y3],..., [xn, yn]] contains the coordinates of the n relevant points.
5
1.2 Output
Your algorithm should output a single pair of coordinates x and y such that Pn
i=1(|x
xi| +
|y yi|)
is minimal. The output should be in the following format: [x, y]. If there are multiple
optimal solutions, your algorithm can output anyone of them (but should output exactly one).
1.3 Examples
In the example depicted above the input/output behaviour of your algorithm would be the
following:
# Example
# The relevant points given as input
relevant = [[5,8], [7,5], [9, 1], [0,7], [1,9], [2,1]]
>>> ideal_place(relevant)
[5, 6]
1.4 Complexity
You can assume addition, subtraction, modulus and comparison as basic operations. You cannot
assume an upper bound on the coordinates. For a list of n relevant points, your algorithm for
finding an ideal place should have a deterministic worst-case time complexity of O(n) basic
operations.
6
2 On The Way
(4 marks + 1 mark for documentation)
You live life efficiently – no wasted movements, highly sustainable. If you are to head out to a
destination, you would try to squeeze in a chore along the way:
• Going to campus? Let’s grab a coffee along the way.
• Going back home? Let’s grab dinner on the way back.
• Going to visit a friend? Let’s fuel up my car along the route.
But of course, there could be multiple options for your chores. You could grab coffee from any
local cafe or Starbucks. Likewise, dinner could be from McDonald’s, Hungry Jack’s or Subway.
In the name of efficiency, your decision is made based on whichever is the closest to your direct
route.
Given your FIT2004 study, you have come to the realization that it is possible to model your
travels using the Graph data structures.
• The RoadGraph class implementation is as described in Section 2.1. An example of the
graph structure is provided below.
• You can then calculate the optimal routes for your commute while doing a chore along the
way using a function in the Graph class called routing(self, start, end, chores_location)
detailed in Section 2.2.
class RoadGraph:
def __init__(self, roads):
# ToDo: Initialize the graph data structure here
def routing(self, start, end, chores_location):
# ToDo: Performs the operation needed to find the optimal route.
7
2.1 Graph Data Structure (1 mark)
You must write a class RoadGraph that represents the roads in the city. The __init__ method
of RoadGraph would take as an input a list of roads roads represted as a list of tuples (u, v, w)
where:
• u is the starting location ID for a road, represented as a non-negative integer.
• v is the ending location ID for a road, represented as a non-negative integer.
• w is the distance along that road, represented as a non-negative integer.
• You cannot assume that the list of tuples are in any specific order.
• You cannot assume that the roads are 2-way roads.
• You can assume that the location IDs are continuous from 0 to |V |
1 where |V | is the
total number of locations.
• You can assume that the maximum number of roads |E| is significantly less than |V |
2.
Consider the following example for the roads in a city, are stored as a list of tuples:
# The roads represented as a list of tuples
roads = [(0,1,4), (0,3,2), (0,2,3), (2,3,2), (3,0,3)]
• 4 locations in the city with the id of 0 to 3.
• 5 roads total in the city connecting the locations.
• There is a road from location 0 to location 1 with a distance of 4.
• There is a road from location 0 to location 3 with a distance of 2.
• There is a road from location 0 to location 2 with a distance of 3.
• There is a road from location 2 to location 3 with a distance of 2.
• There is a road from location 3 to location 0 with a distance of 3.
• Since you can’t assume the roads are 2-way roads, we observe only location 0 and location
3 are connected through a 2-way road although there is a difference in the distance.
Running the following code would create a RoadGraph object called mygraph, which is then
visualized below:
# Creating a RoadGraph object based on the given roads
mygraph = RoadGraph(roads)
Based on the information above, you would need to implement the RoadGraph class using either
an adjacency matrix or adjacency list representation. Do note that one implementation is less
efficient than the other in both time and space complexity. Thus, consider your implementation
carefully in order to achieve full marks.
8
2.2 Optimal Route Function (3 marks)
You would now proceed to implement routing(self, start, end, chores_location) as a
function within the RoadGraph class. The functions accepts 3 arguments:
• start is a non-negative integer that represents the starting location of your journey. Your
route must begin from this location.
• end is a non-negative integer that represents the ending location of your journey. Your
route must end in this location.
• chores_location is a non-empty list of non-negative integers that stores all of the location
where your chores could be performed.
• Do note that it is possible for the locations in chores_location to include the start
and/or end as well.
• Do note that the locations in chores_location is not sorted.
• Do note that all locations in chores_location are valid locations in the roads list.
The function would then return the shortest route from the start location to the end location,
going through at least 1 of the locations listed in chores_location.
• If such route exist, it would return the shortest route as a list of integers. If there are
multiple such routes, return any one of these shortest routes.
• If no such route going from the start location to one of the locations in chores_location
and proceeding next to the end location is possible, then the function would return None.
Several examples are provided in Section 2.3.
# Example 1
# The roads represented as a list of tuples
roads = [(0,1,4), (0,3,2), (0,2,3), (2,3,2), (3,0,3)]
# Creating a RoadGraph object based on the given roads
mygraph = RoadGraph(roads)
Starting from location 0, you are looking to end at location 1. Your chores can be completed
at both location 2 and location 3. The optimal route for you is to travel going through location
3 to complete the chore, then going back to location 0 before ending at location 1. This route
would only travel a total distance of 9. The alternative route of going through locations 0, 2,
3, 0 and then 1 would give you a total distance of 12 1.
# Example 1.1
# the route inputs
start = 0
end = 1
chores_location = [2,3]
>>> mygraph.routing(start, end, chores_location)
[0, 3, 0, 1]
In another example below, you now start at location 0 but look to end in location 3. Your
chore can only be completed in location 2 only. Thus the optimal route is to go from location
0 to location 2 to complete your chore and directly to location 3 that is your destination. Your
total travel distance is 5.
# Example 1.2
# the route inputs
start = 0
end = 3
chores_location = [2]
>>> mygraph.routing(start, end, chores_location)
[0, 2, 3]
1Updated on 1st April 2022 13:28 Malaysia time; old value of 10 is wrong.
10
The next 2 examples below shows when routes are not possible; with the function returning
None.
# Example 1.3 Chores can’t be done
start = 2
end = 0
chores_location = [1]
>>> mygraph.routing(start, end, chores_location)
None
# Example 1.4 Can’t reach end
start = 1
end = 2
chores_location = [0,3]
>>> mygraph.routing(start, end, chores_location)
None
In the following graph example, we look at a bigger, longer and more complex graph.
The graph above is generated through the following code.
# Example 2
# The roads represented as a list of tuples
roads = [(0, 1 ,4), (1, 2 ,2), (2, 3 ,3), (3, 4 ,1), (1, 5 ,2),
(5, 6 ,5), (6, 3 ,2), (6, 4 ,3), (1, 7 ,4), (7, 8 ,2),
(8, 7 ,2), (7, 3 ,2), (8, 0 ,11)]
# Creating a RoadGraph object based on the given roads
mygraph = RoadGraph(roads)
11
In the example below, we start at location 0, end at location 3, and your chores can be completed
at locations 5, 7, 8 and 4. There are a few possible routes possible such as 0, 1, 5, 6, 3 with a
distance of 13 or route 0, 1, 7, 3 with a distance of 10. We would choose the smallest distance.
# Example 2.1 Possible Route
start = 0
end = 3
chores_location = [5,7,8,4]
>>> mygraph.routing(start, end, chores_location)
[0, 1, 7, 3]
Similarly, if we were to start at location 1 we observe that despite the location 5 would be the
closer location to us to perform the chore at a distance of 2 compared to location 7 with a
distance of 4; the route after that would be further. Thus, we cannot make be short sighted in
our path selection based on the nearest chore.
# Example 2.2 Possible Route, despite nearest chore
start = 1
end = 3
chores_location = [5,7,8,4]
>>> mygraph.routing(start, end, chores_location)
[1, 7, 3]
In the next example, we saw multiple routes with the same shortest distance – with route
0, 1, 5, 6, 4 for a distance of 14 and route 0, 1, 5, 6, 3, 4 for a distance of 14. Returning either
would be accepted. Do note that route 0, 1, 7, 8, 7, 3, 4 has a longer distance of 15 and should
not be returned.
# Example 2.2 Possible Route, despite nearest chore
start = 0
end = 4
chores_location = [6,8]
>>> mygraph.routing(start, end, chores_location)
[0, 1, 5, 6, 4]
12
For the final example, we have an even more complicated network of roads.
# Example 3
# The roads represented as a list of tuples
roads = [(0, 1 ,4), (1, 2 ,2), (2, 3 ,3), (3, 4 ,1), (1, 5 ,2),
(5, 6 ,5), (6, 3 ,2), (6, 4 ,3), (1, 7 ,4), (7, 8 ,2),
(8, 7 ,2), (7, 3 ,2), (8, 0 ,11), (4, 3, 1), (4, 8, 10)]
# Creating a RoadGraph object based on the given roads
mygraph = RoadGraph(roads)
The following are 4 cases that were not highlighted by the earlier examples.
# Example 3.1 Best chore location is after end location
start = 1
end = 3
chores_location = [4,5,6,8]
>>> mygraph.routing(start, end, chores_location)
[1, 2, 3, 4, 3]
# Example 3.2 Best chore is before start location
start = 7
end = 4
chores_location = [5,6,8]
>>> mygraph.routing(start, end, chores_location)
[7, 8, 7, 3, 4]
13
# Example 3.3 Best chore is alone the shortest route already
start = 0
end = 4
chores_location = [1,3,4,5,6,8]
>>> mygraph.routing(start, end, chores_location)
[0, 1, 2, 3, 4]
# Example 3.4 There is chore at the start and/ or end location
start = 0
end = 4
chores_location = [0,4,5,6,8]
>>> mygraph.routing(start, end, chores_location)
[0, 1, 2, 3, 4]
There could be other cases not covered in the examples provided. Do have a think about what
are the other possible scenarios related to the question.
14
2.4 Complexity
The complexity for this task is separated into 2 main components.
The __init__(raods) constructor of RoadGraph class would run in O(|V | + |E|) time and
space where:
• V is the set of unique locations in roads. You can assume that all locations are connected
by roads (i.e a connected graph); and the location IDs are continuous from 0 to |V |
1.
• E is the set roads.
• You can make an assumption that the number of roads |E| is significantly less than |V |
2.
Thus, you should not make the assumption that |E| = ⇥(|V |
2).
The routing(self, start, end, chores_location) of the RoadGraph class would run in
O(|E|log|V |) time and O(|V | + |E|) auxiliary space where:
• Note that the chores_location is not stated in the complexity. At worst, the size of
chores_location is |V |.
2.5 Hint(s)
In order to do so, you would utilize algorithms and concepts that you have learnt from FIT2004,
namely:
• Graph data structure.
• Graph algorithms.
Firstly, ensure a suitable graph representation is chosen to meet the complexity requirement for
__init__(roads) constructor of RoadGraph class. A suitable representation would also ensure
the complexity requirements for routing(self, start, end, chores_location) is met as
well.
The complexity for routing(self, start, end, chores_location) can be met by running
a certain algorithm once (approach 1) or twice (approach 2) at most 2. Do take note that this
complexity remains the same irregardless of the number of locations in chores_location; thus,
the solution shouldn’t scale in complexity to that.
You are allowed to process the graph data structure/representation in __init__(roads) as part
of the pre-processing for routing(self, start, end, chores_location). Doing so as you
seen in some of the studio questions could greatly improve the complexity for routing(self,
start, end, chores_location).
2There can be other approaches that would meet the complexity requirements as well.