Belgium
Whats all this about
An algorithm to convert a n-size 3 color (Black, Yellow, Red) flag into
the Belgian flag.
To accomplish this, we can use a robot who can:
-
Swap two fields of the flag
-
Inspect a color of a given field resulting in Black, Yellow or Red
There is another limitation: The algorithm mustn't use arrays or something
like that.
We've developped two algorithms for this task and you can try them
out using the following Applet !
The Applet
The Tommy algorithm was written by Tom
Huybrechts (I know it's the best one in this Applet...)
Number of swaps for a size 3 flag
We compare 3 different algorithms on every possible size 3 flag.
-
Opt = The optimal algorithm (for this case equal to the optimized devide
algorithm)
-
Lin = The linear algorithm
-
Div = The devide algorithm without the size 3 flag optimisation
| Flag |
Opt |
Lin |
Div |
Flag |
Opt |
Lin |
Div |
Flag |
Opt |
Lin |
Div |
| ZZZ |
0 |
0 |
0 |
GZZ |
1 |
2 |
1 |
RZZ |
1 |
2 |
1 |
| ZZG |
0 |
0 |
0 |
GZG |
1 |
1 |
1 |
RZG |
2 |
2 |
2 |
| ZZR |
0 |
0 |
0 |
GZR |
1 |
1 |
1 |
RZR |
1 |
1 |
1 |
| ZGZ |
1 |
1 |
1 |
GGZ |
1 |
1 |
2 |
RGZ |
1 |
3 |
3 |
| ZGG |
0 |
0 |
0 |
GGG |
0 |
0 |
0 |
RGG |
1 |
2 |
1 |
| ZGR |
0 |
0 |
0 |
GGR |
0 |
0 |
0 |
RGR |
1 |
1 |
1 |
| ZRZ |
1 |
1 |
1 |
GRZ |
2 |
2 |
2 |
RRZ |
1 |
1 |
2 |
| ZRG |
1 |
1 |
1 |
GRG |
1 |
1 |
1 |
RRG |
1 |
1 |
2 |
| ZRR |
0 |
0 |
0 |
GRR |
0 |
0 |
0 |
RRR |
0 |
0 |
0 |
Statistics
Number of experiments: 100
Average number of swaps:
| Algorithm |
Size 6 |
Size 12 |
| Linear |
3,32
|
8,7
|
| Divide |
|
10,0
|
| Optimized divide |
2,95
|
9,7
|
| Tommy |
2,03
|
4,76
|
Back to Study page
Back Home