The video shows a theoretical problem in computer science and a solution for it.
Trying to solve it yourself?
First note it’s not easy.
Next, here are some additional comments to clarify the rules as explained in the video:
- You can define any finite set of states you want. You don’t have to use the sample states shown in the first part of the video. You can choose, for example, a set with 100 states.
- Once you choose a set you can’t change it. You can’t say for 1000 robots I’ll use this set, and for 2000 robots that set, and so on. You need to find one finite set of states with an accompanying set of transition rules that will always work.
- The transition rules have the form (A,B,C)->D. That is if you are B and you see A and C to your sides, switch to D. You can also use wildcards. E.g., (*,B,*)->D means if you are B switch to D without minding your neighbors.
If you find something else confusing please write in the video’s youtube comment section.
SPOILERS BELOW
.
.
.
.
SPOILERS BELOW
Shown solution: number of states
The solution shown in the video uses the following states:
1. Idle
2-3. General: Left and right.
4-5. Hand signal: Left and right.
6-11. Leg signal: Left and right, 3 steps each.
12. Fire
And a few additional states to handle the case of an odd number of robots:
13. Double general
14-15. Double leg signal: last 2 steps (the first step is always part of a double general)
16-17. Double hand signal: front and back
So it’s a total of 17 states.
It’s easy to reduce to 15, because in fact there’s no need for three different general states. The robots can deduce the type of the general based on their neighbors. A general with two non-general neighbors is always a double general. A general whose left neighbor is a general and right neighbor a non-general – it must be a right general, and vice versa.
This 15 state solution was the first published solution for this problem (Minsky, Marvin Lee. Computation. Englewood Cliffs: Prentice-Hall, 1967.)
Shown solution: time performance
The hand signal takes n steps to cross the squad, and then another n/2 to get back to the middle, so that’s a total of 3n/2 steps. That’s exactly what it takes the leg signal to reach the middle too. They collide, and the whole thing repeats itself on squads of size n/2.
On a squad of size n/2 it takes 3n/4 steps until the signals collide again, and then 3n/8, 3n/16, …
The sum of this series converges to 3n, since 1/2+1/4+1/8+1/16 . . . converges to 1.
Therefore the time performance of this algorithm is approximately 3n steps.
Optimal solution
The fastest solution to this problem uses 2n-2 steps. There’s a proof this is the best possible time.
It uses also only 6 states. It is not known whether this is optimal or not.
Cellular Automaton
The strange limitations imposed upon the robots in the video are according to a model called “cellular automaton”. In this model there’s an array of cells, and each cell can be in one of a finite set of states. The cells change states simultaneosly, based on their current state and that of their neighbors.
A more famous example of this model is Conway’s game of life. There the cells are in a 2-dimensional grid, and they have only two states: “live” or “dead”. A simple set of transition rules allows a vast range of interesting patterns.