The Art of Programming

If ten years from now, when you are doing something quick and dirty, you suddenly visualize that I am looking over your shoulders and say to yourself: ‘Dijkstra would not have liked this’, well that would be enough immortality for me.

Edsger Dijkstra

 

 

The above quote is one of many from Edsger W. Dijkstra, a Dutch computer scientist and former professor at my university. It was prof. Dijkstra who introduced me to the Art of programming.

 

I don’t think that any of us students knew how famous he already was or, for that matter, that he had received the prestigious Turing Award in 1972. I remember him as a humorous and slightly cynical man. Even a bit arrogant perhaps, and definitely unreachable (always shielded by his assistant Wim Feijen).

Actually, the full name of the course he taught was:  “A Short Introduction to the Art of Programming” (the original lecture notes can be found here). By calling it “a short introduction”, he made it perfectly clear that, even in the unlikely case you would ever pass the exam with good result, you would still be a ‘noob’.

More important, though, was the deliberate use of the word Art. For him, elegance and control were keywords when writing an algorithm. He showed us that, almost by nature, elegant algorithms are not only easily verifiable, but often the shortest and most efficient solution to the problem as well.

My first attempt to pass the exam earned me a 3 (out of 10). That was actually quite good, because it meant: 1. Although not elegant, your algorithm works; 2. You proved that it works; 3. You did not use Go To statements (Dijkstra would kill you for that).

My second attempt earned me a 9! Such a high score was quite exceptional, because it meant something like: 1. Damn, your solution is even more elegant than mine (i.e. corrector Wim Feijen’s, definitely not Dijkstra’s); 2. I’m not going to grade it a 10 because that would only draw prof. Dijkstra’s attention. Guess it was one of my brighter days…

In hindsight, I now realize how much influence Edsger Dijkstra’s Short introduction to the Art of Programming actually had on me. Not only in the way I approach algorithmic problems, but even more so in the pleasure I get from finding elegant solutions. I don’t mind him looking over my shoulders now and then.

 

 

 

Game of Life

Conway’s Game of Life is a nice demonstration of how simple rules can generate complex structures. It’s also a great introduction to the fascinating world of Cellular Automata.

see also: Game of life (revisited)

The Game of Life, or simply ‘Life’, takes place on an infinite 2-dimensional grid, populated by cells. In every next generation, the new state of each cell depends on the current state of the eight surrounding cells (its ‘Moore neighborhood’), following this simple set of rules:

  1. Living cells die if they have less than 2, or more than 3 living neighbors.
  2. Dead cells are brought to life if they have exactly 3 living neighbors.

The initial state of the system completely determines the further process, in which order and chaos can easily get involved in a continuous arm wrestling game.

Mathematicians and Life enthusiasts have found some incredible patterns like the Gosper Glider Gun, the Puffer Train and the Breeder. This video starts on a grid with ~25% of the cells ‘alive’ (randomly chosen).

The main challenge of running a simulation of ‘Life’ on an Arduino Uno lies in its limited RAM memory size (2K only!). Since the rules are applied to all cells simultaneously, we need to store both the old and the new state of the grid.

First I used Booleans to store cell states, but since every boolean claims a full byte (8 bits), the largest grid that Uno could handle was about 17×17 in size. The trick was to use bytes instead, where each byte now holds the state of eight consecutive LEDs in one of the rows, thus replacing eight boolean bytes!

With this new approach, Arduino Uno can simulate a 64×32 cell grid on my 128×64 pixels monochrome I2C Oled display (using 89% of Uno’s precious RAM). In that configuration, cells are represented by 2×2 LED squares, lit when alive and unlit when dead.

Note that you can define the initial state of the grid within the seed() function of the sketch. I used a simple border rule for the video: neighbor cells outside the grid are considered dead.