Bubble sort of one cacti column in TFWR

Bubble sort of one cacti column in TFWR

This game provides quite a nice opportunity to see how different sorting algorithms work. In this post, let's discuss the famous bubble sort.

You can check the code on github.

Let's check how it is built.

best_move is a helper function for nav. nav allows us to move the drone to any given coordinates on the field.

Then, in the script I set the farm size to 16, just to test moving the drone to the point (6, 6). Till the soil, so we can plant cacti. Then - plant cacti. And, finally, lines 32-36 - bubble sort.

For me, here it's interesting to clearly set variables and their physical sense. I don't want to do unnecessary work and I want to correctly handle corner cases. So:

• y_upper - is the last cell we want to swap cacti with

Let's stop here and think, what we can derive from this statement. It means that y_upper moves from (n-1) to 1 inclusive. So, small subtask - to set range for y_upper correctly. It's range(n-1, 0, -1).

After that, everything is simple. The inner cycle, which sets the drone's position, just loops from 0 to y_upper - 1, which gives a simple range(y_upper). Basically, that's it. The measure() function from the game is very handy for this task, comparison with the upper cell is just

measure() > measure(North)

as well as swapping with this cell

swap(North)

One more interesting thing. The map is on the torus, so in the beginning of sorting the drone "rotates" in one direction. But when more than half of the column is sorted, it starts to move back and forth.