Development Blog on software and related things

Helping King Leonidas drive a chariot

So my 14-years-old niece came and asked to help with her home work. “Sure, bring it on!” I said, expecting something along the lines of one starts sooner, another goes faster. What followed surprised me, and leaded to the gist as well to the rest of this article.

The home work assignment

The expected one starts sooner, another goes faster stuff instead turned out to be:

King Leonidas drives his chariot on a rectangular field of size H × W (1 ≤ H, W ≤ 1000). The chariot is a special model that can only drive forward and needs some help to make a turn. The help usually comes in the form of a few strong spartan warriors who lift the chariot and rotate it in one of the 8 directions (vertically, horizontally, or diagonally). King Leonidas wants to keep his warriors fresh for upcoming fight with Xerxes, and therefore needs to make least amount of turns possible. The terrain around Sparta is rocky and some of the cells are impassable. The coordinates origin is in the lower left-hand corner of the field. The starting position differs from the end, the start and end cells are not impassable.

aa

“Hmmm… Are you sure it’s your home work??”, I asked.

“Yep. I’ve already tried BFS and Dijkstra but run into some problems, can you help?”

“Oh, time flows… What language do you need to do it with?”

“Well, C++ would be good for speed.

“Uhmm… How about Swift? It’s kind of cool and pretty fast, you know…”

“That new javascript-like language?”

“Javascript-like what??”

“OK, OK I got the coolness. But sorry, not for this one. They also accept Python though…“

So no Swift allowed. But Python… Deal then.

BFS to the rescue

The task looks like a classical shortest path problem, and since there are no notion of weights for the edges a standard BFS should do the job.

Using a plain python list to represent the queue of paths, this translates into:

class PathFinder:
    def shortest_path(self, start_point, end_point):
        # the queue of paths
        queue = []
        visited = set()
        queue.append([start_point])
        while queue:
            # the first path from the queue
            path = queue.pop(0)

            # the last point from the path
            current_point = path[-1]

            # path found?
            if current_point == end_point:
                return path

            #### adjacent points for the current point
            for adjacent_point in self._adjacent_points(current_point):
                if adjacent_point not in visited:
                    visited.add(adjacent_point)
                    # construct a new path and add it to the queue
                    new_path = list(path)
                    new_path.append(adjacent_point)
                    queue.append(new_path)
        # no path found
        return []

The field and the points

Now that the algorithmic part is done, let’s add some flesh to specific terms of the task. The Point class represents a point in the field’s coordinate system.

class Point:
    def __init__(self, x = 0, y = 0):
        self.x = x
        self.y = y

The field itself can be represented as a matrix, where obstacles can be visualized as 'o' while usable cells will be displayed as ' ' :

[' ', ' ', 'o', ' ', ' ']
['o', ' ', 'o', ' ', 'o']
['o', 'o', ' ', ' ', 'o']
['o', 'o', 'o', ' ', 'o']
[' ', 'o', ' ', 'o', ' ']
['o', ' ', 'o', ' ', 'o']
['o', 'o', 'o', ' ', ' ']

For internal implementation, let’s use more standard 0 to represent an obstacle and 1 to indicate a free space.

We will need to generate a field of any reasonable size, which in python can be done with the following comprehension:

import random
range_X, range_Y = 15, 12  # change these as needed for the test
test_field = [[random.randrange(2) for _ in range(range_X)] for _ in range(range_Y)]

To enable comparison between points as well as to support putting them into the set of visited nodes, let’s beef up our Point class some more:

class Point:
    def __init__(self, x = 0, y = 0):
        self.x = x
        self.y = y
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    def __hash__(self):
        return hash((self.x, self.y))
    def __str__(self):
        return '({0}, {1})'.format(self.x, self.y)

Making the chariot’s wheels turn

To make our chariot move in the field, we need to define some appropriate rules while at the same time giving our BFS search code a list of adjacent points to work with:

    def _adjacent_points(self, point):
        ''' given a point, finds all adjacent points that are not obstacles
        '''
        adjacent_points = []
        # can take a step into either directions
        # x-1 | x+1 | y-1 | y+1
        for x in range(-1,2):       # -1 <- x -> +1
            adj_x = point.x + x
            adj_x = adj_x if adj_x >= 0 else 0
            adj_x = adj_x if adj_x < self.max_x else self.max_x - 1

            for y in range (-1,2):    # -1 <- y -> +1
                adj_y = point.y + y
                adj_y = adj_y if adj_y >= 0 else 0
                adj_y = adj_y if adj_y < self.max_y else self.max_y - 1

                if adj_x == point.x and adj_y == point.y:
                    continue
                adjacent_point = Point(adj_x, adj_y)
                if self.is_obstacle(adjacent_point):
                    continue
                # all checks passed
                adjacent_points.append(adjacent_point)
        return adjacent_points

    @property
    def max_y(self):
        return len(self._field)
    @property
    def max_x(self):
        return len(self._field[0])

    def is_obstacle(self, point):
        return self._field[point.y][point.x] == 0

That will allow required movement into either of 8 possible directions, while checking on all relevant constraints of the given field.

At that point, most of the task code should be ready and the only thing remaining is to see whether it actually does something useful.

Visualizing results

As it goes in real life, no job is complete till it is proven to be complete. The gist test code goes all the way there, allowing to define any reasonable field size and then randomly generating the field with obstacles as well as choosing random start and end points.

A successful shortest path search is visualized as:

[' ', ' ', ' ', ' ', ' ', 'o', ' ', 'o', ' ', ' ', ' ']
[' ', 'o', 'o', 'o', 'o', 'o', 'o', 'S', 'o', ' ', ' ']
[' ', 'o', 'o', ' ', ' ', ' ', ' ', 'o', '*', ' ', 'o']
['o', ' ', 'o', 'o', 'o', 'o', 'o', 'o', '*', ' ', 'o']
['o', 'o', ' ', 'o', ' ', ' ', 'o', '*', 'o', 'o', 'o']
['o', ' ', ' ', ' ', ' ', ' ', 'o', '*', 'o', ' ', ' ']
['o', ' ', 'o', 'o', 'o', 'o', '*', 'o', ' ', 'o', ' ']
[' ', 'o', 'o', 'o', 'o', ' ', 'o', '*', ' ', 'o', 'o']
['o', ' ', 'o', 'o', 'o', 'o', 'o', '*', 'o', 'o', ' ']
[' ', 'o', 'o', 'o', ' ', ' ', '*', ' ', 'o', ' ', 'o']
['o', 'o', 'E', ' ', 'o', '*', ' ', ' ', ' ', ' ', 'o']
['o', 'o', ' ', '*', '*', 'o', 'o', ' ', ' ', 'o', 'o']
[' ', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o', ' ', ' ']
['o', 'o', ' ', 'o', 'o', 'o', ' ', ' ', 'o', ' ', ' ']

Shortest path from (7, 12) to (2, 3)):
  (7, 12)->(8, 11)->(8, 10)->(7, 9)->(7, 8)->(6, 7)->
  (7, 6)->(7, 5)->(6, 4)->(5, 3)->(4, 2)->(3, 2)->(2, 3)

Found path with distance 12 in: 0.2527sec

Where 'o' represents an obstacle, 'S' is the start point, 'E' is the end point and the '*'s show the actual shortest path.

The results for non-existent paths are visualized as:

[' ', ' ', 'o', ' ', ' ', ' ', 'o', ' ', ' ', ' ', 'o']
['o', 'o', 'o', 'o', 'o', ' ', ' ', ' ', ' ', ' ', ' ']
['o', 'o', ' ', ' ', 'o', ' ', 'o', 'o', ' ', ' ', ' ']
['o', ' ', 'o', 'o', ' ', 'o', 'o', ' ', ' ', ' ', ' ']
['o', 'o', ' ', 'o', ' ', ' ', 'o', 'o', 'o', 'o', ' ']
['o', ' ', 'o', 'o', 'o', ' ', 'o', 'o', ' ', 'o', 'o']
['o', 'o', 'o', 'o', ' ', 'o', 'o', ' ', 'o', 'o', ' ']
['o', ' ', 'o', 'o', ' ', 'o', 'o', 'o', 'o', 'o', ' ']
[' ', 'o', 'o', 'o', 'o', 'o', ' ', 'o', ' ', 'o', 'o']
['o', 'o', ' ', 'o', ' ', ' ', 'o', ' ', 'o', ' ', ' ']
['o', ' ', 'o', 'o', 'o', ' ', 'o', 'o', ' ', ' ', 'o']
['o', ' ', 'o', 'o', 'o', ' ', ' ', 'o', 'o', 'o', 'o']
['o', 'o', ' ', 'o', 'o', 'o', ' ', 'o', ' ', 'o', 'o']
['o', 'o', 'o', 'o', 'o', ' ', ' ', ' ', ' ', 'o', 'o']
No path from (2, 1) to (8, 0) (distance: -1)
No path from (6, 1) to (9, 12) (distance: -1)

Conclusion

The gist looks good”, she said. “Could be a bit faster for a field of boundary size 1000x1000, but when I re-write it in C++ it might actually be OK. Or maybe we could do some sort of bi-directional BFS or something?

“Well, bi-directional BFS definitely sounds fun. But it’s gotta be Swift this time, young lady. Come back when you are ready!”