*Hobbyist blog about all things software. Any correspondence of this blog's name to names of individuals, organizations, companies, products or other blogs is pure coincidence.*

## Sunday, September 22, 2013

### Musings on the disaster-formerly-known-as-worldwide-market-leader Microsoft

(also see this older post)

## Friday, August 2, 2013

### can Pyjamas rise from its ashes?

Given that the hijacked project, while it has seen some contributions from different people, seems to have slowed down considerably since the debacle (although it's possible that people are developing awesome stuff in their forks), I'm curious to see what this intiative - if anything - will do to make pyjamas more popular again.

Here are two screenshots comparing the recent git histories.

recent git history of the hijacked project at pyjs.org |

recent git history of the reinstated pyjamas at pyj.be |

## Saturday, July 13, 2013

### Solving the towers of Hanoi using Lindenmayer systems

## 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 ;)**## Monday, July 8, 2013

### Automatically create a GUI for your argparse based command line tool

## Problem

You are asked to create small tool in python to help someone out. Someone else comes along who wants to reuse the tool, but needs a minor variation on the theme. No problem, you think, I'll just add a command line option using python's argparse module.Fast forward one month. The tool proves to be a success, but everyone wanted something slightly different, leading to 15 command line options. Now people start to complain that they lose oversight over the command line options. Other people see the potential in your tool but they are afraid of command lines altogether...

You realize you could please your users by giving them a UI to set up the command line options. But creating a UI is a lot of work... What now?

## Argparseui to the rescue!

If you think you may get away with a zero-effort but ugly auto-generated UI, perhaps argparseui (python2.7 and python3, GPLv3) can be of use. Argparseui depends on PyQt.As of yet it doesn't support all of argparse, nor does it officially support python3 (although basic use cases seem to work with python3), but it seems to scratch my itch.

## Example code?

Using argparseui is very similar to using argparse. Here's an example:## Screenshot?

This is a screenshot made on Linux, IceWm. On windows, the dialog will look like a windows dialog, and on Mac OsX it should look like a Mac OsX dialog...## Sunday, April 21, 2013

### Algorithmic composition with python, rtmidi, yoshimi, linuxsampler

# What?

Generating real-time midi events from python!# Why?

For fun! Dabbling with python and algorithmic composition.# How?

Unpolished code available from github: Twenty five shades of random.# Eh?

Ok, ok, here's the manager's summary. Really, you should check out the code for all the details.

A score is made by scheduling activation and deactivation of score generators in time.

Score generators consist of a strategy (e.g. pick random notes and add random octaves to them, and choose random velocities, and ...) and constraints (e.g. the notes must come from a given list of allowed notes, the durations have to be a multiple of pi, ...).

There's a scheduler class that for any given time can tell you what score generators are supposed to be running or stopped. More philosophy and background information for this piece can be found on my music blog: A Touch of Music.

Youtube movie with the result of running the program once:

Each time you rerun the program, you get a different composition in a very similar style.

Creation of this piece was heaps of fun! For further experiments in algorithmic composition (if any!) I probably owe it to myself to check out in some detail the promising supercollider environment.