Posted by Marta on February 1, 2023 Viewed 4432 times
This article will show how to use a python graph implementation for a real exercise that I have seen in many interview processes. Plus, it is an exciting and challenging problem to solve. Firstly I will introduce the problem itself and a possible way to solve it using python.
Here is the python assignment.
A delivery service company creates a system that will plan a route for a delivery truck to deliver customer orders. The planner will create a delivery area for each order, which is abstracted as a grid. The challenge is to write an algorithm to determine the distance required for the truck to deliver the order.
The delivery area is represented as a two-dimensional grid of integers where:
This problem is one of my favorite python assignments for practice. An excellent example of using the correct data structure can turn a seemingly complex problem into something much more straightforward.
Some stuff you should take into account. The truck can’t leave the grid and should get to the order destination through the accessible areas. And the truck can move one cell up, down, left, or right at a time.
Here are some examples of different cases with the inputs and the corresponding outputs:
Example 1 grid = [[1,1,0],[0,1,2][0,1,1]] Output: 5 Example 2 grid = [[1,1,1,1],[0,1,0,1],[0,1,0,1],[0,1,1,0],[0,1,2,1]] Output: 6
I will advise you to pause here and try to solve this problem yourself before checking the solution.
Warning. It is a challenging problem, so don’t worry if it takes you 1 or 2 hours to solve, or even more if you haven’t practiced solving coding problems for a while. That is entirely normal.
To give you a hint, the key to solve this problem is choosing the correct data structure. If you select a data structure, and your code starts becoming complex, that might be a sign; the data structure is not quite right.
The best solution to this problem is using a python graph implementation. In general, a graph is a right solution for any situation where you need to navigate a grid.
Plus, I will advise you to solve this problem following the test-driven approach, which means defining the function signature to do the calculation without writing the code. Then write some tests. And last, writing the code. Why writing tests? It will be much easier and quicker to check that things are working correctly.
Below is the function that will contain the algorithm, no implementation yet:
#Filename: delivery_route.py def find_route(area): return 0
And the test, containing sample inputs and the expected results:
# Filename: delivery_route_test.py import unittest from delivery_route import find_min_distance_route class DeliveryRouteTest(unittest.TestCase): def test_case2(self): min_distance = find_min_distance_route([[1,1,0],[0,1,2],[0,1,1]]) self.assertEqual(5,min_distance) def test_case3(self): min_distance = find_min_distance_route([[1,1,1,1],[0,1,0,1],[0,1,0,1],[0,1,1,0],[0,1,2,1]]) self.assertEqual(6, min_distance)
Now that we defined what the code should do let’s see an overview of the steps you could follow to solve the problem.
First, we will build a graph like the one below, where each graph node represents a grid cell, and the lists linked to the node represents the connected cells. This representation allows us to navigate the nodes that are connected quickly and ignore the empty cells.
To do so, I will loop through every cell, ignoring the cell containing 0, since they are not accessible. I will check if the cells around are accessible. Those cells will be the adjacent nodes. Then I will create a list containing all adjacent nodes and associated with the node itself.
See how to implement this in python below:
# Add this method to the delivery_route.py file class Cell: def __init__(self, row, col): self.row = row self.col = col def hashkey(self): return str(self.row)+str(self.col) def __eq__(self, other): return self.row == other.row and self.col == other.col def __str__(self): return str(self.row)+str(self.col) def build_graph(area): graph = {} #Loop through all cells for row in range(len(area)): for col in range(len(area[row])): if (area[row][col] != 0): current_cell = Cell(row, col) cell_doesnt_exist_on_graph = graph.get(current_cell.hashkey()) == None if(cell_doesnt_exist_on_graph): graph[current_cell.hashkey()]= [] # Check the top, left, down and right cells to get the cells that are connected adjacents = graph.get(current_cell.hashkey()) if(row-1>-1): # Don't check cells out of the grid if(area[row-1][col]!=0): adjacents.append(Cell(row-1,col)) if(col-1>-1): if(area[row][col-1]!=0): adjacents.append(Cell(row,col-1)) if(row+1<len(area)): if (area[row+1][col]!=0): adjacents.append(Cell(row+1,col)) if(col+1<len(area[row])): if(area[row][col+1]!=0): adjacents.append(Cell(row,col+1)) graph[current_cell.hashkey()] = adjacents return graph
Now that we build the graph, the truck can start moving to the destination!
The code will need to check if we got to our destination; in other words, check if the cell where the truck is positioned is equal to 2. If not, we will move to the next accessible cells, any of the connected nodes. To avoid moving in a circle or move to cells that we already visited, we will create a list to track the visited cells.
# Add this method to the delivery_route.py file def find_route(area): area_graph = build_graph(area) # Start at the 0,0 cell current_cell = Cell(0,0) already_visited_list = [current_cell] path =[current_cell] while(area[current_cell.row][current_cell.col]!=2): current_cell = find_next_accessible(current_cell,already_visited_list,area_graph) if(not current_cell): # the truck got to dead end, go back current_cell = already_visited_list[len(already_visited_list)-2] path.pop() else: already_visited_list.append(current_cell) path.append(current_cell) return len(path)-1
And here is the method to get the next accessible cell. In the case of no accessible cell, it will return None.
# Add this method to the delivery_route.py file def find_next_accessible(current_cell, alreadyVisitedCells, area_graph): for adjacent_cell in area_graph[current_cell.hashkey()]: if(not (adjacent_cell in alreadyVisitedCells)): return adjacent_cell return None
I hope this short article was useful and clarifies how to build a graph and navigate a graph. Keep in mind the graph structure fits well for any problem where there are entities and relationships between those entities. I encourage you to keep doing python assignments for practice and to develop your programming skills.
I hope you enjoy this tutorial, and thank you so much for reading and supporting this blog! Happy coding!
Steady pace book with lots of worked examples. Starting with the basics, and moving to projects, data visualisation, and web applications
Unique lay-out and teaching programming style helping new concepts stick in your memory
Great guide for those who want to improve their skills when writing python code. Easy to understand. Many practical examples
Perfect Boook for anyone who has an alright knowledge of Java and wants to take it to the next level.
Excellent read for anyone who already know how to program and want to learn Best Practices
Perfect book for anyone transitioning into the mid/mid-senior developer level
Great book and probably the best way to practice for interview. Some really good information on how to perform an interview. Code Example in Java