## Introduction

What I'm about to describe is a funny side result of a technique to transform recursion to iteration, derived mathematically in my PhD thesis "*Platform-independent*

*source code transformations for task concurrency management*", written 10 years ago. Time flies!

Funny how after so many years I consider exactly this little side-result to be the most intriguing result of my thesis. The mathematical proof of how it works is best left to the thesis itself, but I will try to demonstrate you how you could calculate the j-th move in an N-disk Hanoi problem using a Lindenmayer system.

##
Solving *what* with *what*?!

### towers of Hanoi

The towers of Hanoi are a puzzle in which one is asked to move disks from the rod on the left to the rod on the right according to the following rules:- move only one disk at a time
- Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
- No disk may be placed on top of a smaller disk.

#### Lindenmayer systems

A Lindenmayer system (or L-system as it's often called) consists of a series of symbols, called an alphabet (think: A,B,C,...) and a set of rules that transform sequences of symbols into new sequences of symbols. Here's an example:- alphabet
*A, B, C*. - rule 1: ACB -> AB
- rule 2: AB ->

Rule 1 can be read as:

*whenever you encounter the sequence ACB, replace it with AB*.

Rule 2 can be read as:

*given sequence AB, remove it*(or: replace it with an empty string, if you like fancy words :) )

We could apply the rules to the following start sequence: ABAABCBA

- first, use rule 2:
**AB**AABCBA becomes AABCBA - then, use rule 2: A
**AB**CBA becomes ACBA - then, use rule 1:
**ACB**A becomes ABA - then, use rule 2:
**AB**A becomes A

## How are both things related?

The following drawings show the solution of the Hanoi problem with three disks:- Move 1 goes from rod A to rod C
- Move 2 goes from rod A to rod B
- Move 3 goes from rod C to rod B
- Move 4 goes from rod A to rod C
- Move 5 goes from rod B to rod A
- Move 6 goes from rod B to rod C
- Move 7 goes from rod A to rod C

And the answer, of course, is

*yes we can*!

## Recipe

For the mathematical details of why the following recipe works, you will need to read chapter 6 in the thesis, but if you just want to apply a recipe and marvel at the wonders of science (ahem!), keep reading...First the recipe itself, then I will illustrate using an application. If you want to calculate the j-th move (where j can go from 1 to 2^N-1) in an N-disk problem, do the following:

- take j and write in binary representation
- reverse the binary representation
- pad with 0's on the right side until you've used N bits
- remove everything coming before and including the first 1-bit
- Now we have a sequence of 0 and 1 which we consider the alphabet of a Lindenmayer system and we apply the following rules (in any order you like) until no more rules can be applied:

00 -> <empty>

11 -> <empty>

1010 -> 01

0101 -> 10 - eventually you end up with one of the following sequences. The sequence we end up with directly tells us the j-th move in the N-disk towers of Hanoi problem:

Sequence | Move from to |
---|---|

0 | A->B |

1 | B->C |

01 | B->A |

10 | C->B |

101 | C->A |

010 | C->A |

<empty> | A->C |

### Example

Recall our N=3-disk Hanoi problem. Let's see if we can calculate the j=2nd move using the method shown above.- take number 2 and write it in binary representation: 10
- reverse the binary representation: 01
- pad with 0's to the right until we have used N=3 bits: 010
- chop off everything before and including the first 1-bit: 0
- apply the rules until you hit one of the cases in the table: no rules can be applied here, since we are already in the case 0. According to the table, ending up with 0 indicates a move from A->B
- Double-checking in the solutions that were displayed before, we indeed see that the 2nd move goes from A->B.

Move no. | Binary | Reverse | Pad | Chop | L-system simplifcation | Move according to the table |
---|---|---|---|---|---|---|

1 | 1 | 1 | 100 | 00 | <empty> | A->C |

2 | 10 | 01 | 010 | 0 | 0 | A->B |

3 | 11 | 11 | 110 | 10 | 10 | C->B |

4 | 100 | 001 | 001 | <empty> | <empty> | A->C |

5 | 101 | 101 | 101 | 01 | 01 | B->A |

6 | 110 | 011 | 011 | 1 | 1 | B->C |

7 | 111 | 111 | 111 | 11 | <empty> | A->C |

### Example for N=5

Now let's apply the recipe to the 5-disk problem. The 5-disk problem takes (2^5-1) = 31 moves to solve.Move no. | Binary | Reverse | Pad | Chop | L-system simplifcation | Move according to the table |
---|---|---|---|---|---|---|

1 | 1 | 1 | 10000 | 0000 | <empty> | A->C |

2 | 10 | 01 | 01000 | 000 | 0 | A->B |

3 | 11 | 11 | 11000 | 1000 | 10 | C->B |

4 | 100 | 001 | 00100 | 00 | <empty> | A->C |

5 | 101 | 101 | 10100 | 0100 | 01 | B->A |

6 | 110 | 011 | 01100 | 100 | 1 | B->C |

7 | 111 | 111 | 11100 | 1100 | <empty> | A->C |

8 | 1000 | 0001 | 00010 | 0 | 0 | A->B |

9 | 1001 | 1001 | 10010 | 0010 | 10 | C->B |

10 | 1010 | 0101 | 01010 | 010 | 010 | C->A |

11 | 1011 | 1101 | 11010 | 1010 | 01 | B->A |

12 | 1100 | 0011 | 00110 | 10 | 10 | C->B |

13 | 1101 | 1011 | 10110 | 0110 | <empty> | A->C |

14 | 1110 | 0111 | 01110 | 110 | 0 | A->B |

15 | 1111 | 1111 | 11110 | 1110 | 10 | C->B |

16 | 10000 | 00001 | 00001 | <empty> | A->C | |

17 | 10001 | 10001 | 10001 | 0001 | 01 | B->A |

18 | 10010 | 01001 | 01001 | 001 | 1 | B->C |

19 | 10011 | 11001 | 11001 | 1001 | <empty> | A->C |

20 | 10100 | 00101 | 00101 | 01 | 01 | B->A |

21 | 10101 | 10101 | 10101 | 0101 | 10 | C->B |

22 | 10110 | 01101 | 01101 | 101 | 101 | C->A |

23 | 10111 | 11101 | 11101 | 1101 | 01 | B->A |

24 | 11000 | 00011 | 00011 | 1 | 1 | B->C |

25 | 11001 | 10011 | 10011 | 0011 | <empty> | A->C |

26 | 11010 | 01011 | 01011 | 011 | 0 | A->B |

27 | 11011 | 11011 | 11011 | 1011 | 10 | C->B |

28 | 11100 | 00111 | 00111 | 11 | <empty> | A->C |

29 | 11101 | 10111 | 10111 | 0111 | 01 | B->A |

30 | 11110 | 01111 | 01111 | 111 | 1 | B->C |

31 | 11111 | 11111 | 11111 | 1111 | <empty> | A->C |

So now you can calculate the optimal move in a N-disk Hanoi puzzle with 3 poles at any moment in time without having to know any of the previous or future moves.

### Order of rule application in the L-system simplifications

From the N=5 case, it becomes clear that the L-system has more work to do, and the work to be done by our L-system increases as N increases.One thing I'd like to show you in more detail is how the order of application of the rules doesn't influence the end result. This is not as obvious as it might seem.

First consider a different L-system with the following rules:

- alphabet: 0,1
- rule 1: 001 -> 0
- rule 2: 00 -> <empty>

- If you first apply rule 1, you get
**001**-> 0 - On the other hand, if you first apply rule 2, you get
**00**1-> 1

**Clearly, in general the order of rule application matters!**

But interestingly enough, this is not the case in our towers of Hanoi move simplification L-system. While the proof is in the thesis, I will just demonstrate on a few values.

Consider the 45th move in an 9-disk problem.

- 45 binary: 101101
- reversed: 101101
- padded to 9 bits: 101101000
- chopped after first 1 bit: 01101000

- 0
**11**01000 ->**00**1000 -> 1**00**0 -> 10 -> move C->B - 01
**1010**00 ->**0101**00 -> 10**00**-> 10 -> move C->B - 011010
**00**-> 01**1010**->**0101**-> 10 -> move C->B - 011010
**00**-> 0**11**010 ->**00**10 -> 10 -> move C->B - ...

**There you have it. L-systems solving the towers of Hanoi problem. Who would have thought ;)**
## No comments:

## Post a Comment