Sorting with registers

Previous post was about sorting with no advanced functionality, which robot Emil also provides. I tried to rewrite it using memory registers and functionality for checking the height of stack of bricks in front of the robot. The result is terse and almost look like any procedural programming language. Take also a note to function CheckLength which returns value in special register called Counter (only register which can be used for function return value).

Bubble sort in Robot Emil which uses memory registers

Hey robot, sort this!

How to sort in Robot karel? Sorting algorithms are necessary part of any beginner programming lessons. Robot karel is educational programming language in which you control an robot, which can turn left, right, do steps, place bricks from nowhere and pick them up. The robot can also check if there is a wall or brick in front of him. Program structure contains repeating, checking for condition and repeating while some condition is met. So robot is only something like the Turing machine with two dimensional finite tape. The inner state of robot is only represented by instruction position in robot program. I have used extended version robot Emil which is able to stack brick on the floor, so it is possible to more easily organize memory.

In standard programming language bubble sort is quite easy algorithm e.g. in python it can be expressed like.

a = [3, 7, 6, 5, 1, 2, 0]
N = len(a)
while True:
  is_sorted = False
  for x in range(N-1):
    if a[x] > a[x+1]:
      a[x], a[x+1] = a[x+1], a[x]
      is_sorted = True
  if not is_sorted:
    break
print(a)

Robot Karel is nothing like standard programming languages even x86 assembler is more advanced (processor has registers and a lot more instructions). So how to sort in it?

What are basic operations?
Comparing numbers, Swapping them..

The environment has two biggest disadvantages:
All memory is global and you have to make sure that some util will not overwrite something.
All addressing is relative, it is possible to store where have you been (usually by placing brick on some possition and going to a corner of a room, but it takes time).

Biggest strugles
Swithing columns is quite easy. Comparing columns is not. Because robot can see only if is a brick in front of him or not, but not their count. Comparing columns of bricks has to be done by removing brick from them so it is destructive. So we have subtask of cloning columns. Also all conditions in the program are atomic, therefore robot has to go to the right place to test it and even if the condition will fullfill the robot has to return back. So there is lot of moving. Program contains procedures, but there are no parameters and return values, so everything has to be stored on the room floor.

Cloning columns
Checking the height of column is also destructive operation, therefore robot has to enlarge two columns for each removed brick and one column move back to the original position.

Column comparsion
Robot removes bricks from each column until one column is empty according which it will clean used space and put or not put the brick on the floor. Then it only checks if the brick is on the floor and if so, it will swap columns.

Testing of ending condition
If the whole sequence was gone trough and no columns were swapped the algorihtm should end. Therefore if there was some column swapping robot will pull the brick on the floor and after each checking it will check if there is some brick from the previous step and moves it to the next position. When the robot reach the end of sequence it can decide according the brick by him if in the whole cycle was some swaping or not.

Memory representation
The sequence is in the first row the sequence is long as the floor minus one. One column at the end of room has to be free, because the robot cannot travel trough columns heigher then two so it has to goes arround them (and thanks to memory our representation has to have place trough which can go around for the last item in the cycle). Second row is used for robot movement and placing the bit brick, for checking if some swapping was done. Third row is sometimes used for storing result of comparsion and othertimes with other columns for other operations like for swapping and comparing columns. The robot uses columns in these rows relative to his own position.

The program source code