Python Graph Implementation Exercise – Plan a delivery route

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.

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:

• 1 represents an accessible area
• 0 represents a non-accessible area
• 2 represents the order destination

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.

Solution

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.

• Build a graph with the area information like the one below
• Start on position (0,0)
• Keep checking if you got to the destination. If not, move to the next accessible cell.

Write Python Graph Implementation

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

Keep moving to your destination

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

Conclusion

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!

More Interesting Articles

Fun projects for beginners using python

Automate your youtube downloads using python

Face Detection using python and opencv – less than 10 lines of code