Helping King Leonidas drive a chariot
26 May 2016
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.
“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…”
“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:
The field and the points
Now that the algorithmic part is done, let’s add some flesh to specific terms of the task.
Point class represents a point in the field’s coordinate system.
The field itself can be represented as a matrix, where obstacles can be visualized as
'o' while usable cells will be displayed as
' ' :
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:
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:
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:
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.
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' 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:
“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!”