Verslag Coding Dojo TSP

08-01-2011

Travelling Salesman Kata - Devnology 5 January 2011

This report is written by Paul Spencer(@paul_spencer) . Thanks a bunch Paul!

  • Mr Miyagi / Sensei: Stefan Nijenhuis
  • Weapons of choice: C# and a BDD style supported by the StoryQ library.
  • Fighting style: Randori Kata, supported by Stefan’s Randori Timer app.

My limited experience of TDD had taught me that driving design by tests was OK in general but in creating good design and in specific hard mathematical problems a bit more forethought was required. The Traveling salesman problem is a hard problem. I know it’s a hard problem, because in reading the Wikipedia article on it, my brain started punching my eyes to make them stop reading. So going into the dojo I was sure this could not be done.

After niceties were dispensed, the first slide was displayed and as Saul on the road to Damascus, scales fell from my eyes and the the answer to my TDD vs Hard Mathematical Problems was answered. We were not going to be gods creating the solution perfect in the first try, we were going to be as nature, brute forcing the answer with (to misquote Terry Pratchet) “[Algorithms doing] their own evolving, making it up as they go along, which is the way Nature intended. … there’s nothing like millions of [CPU Cycles] of really frustrating trial and error to give a species moral fiber and, in some cases, backbone.” We were going to use Genetic Algorithms to solve the problem. The ‘TDD leading to mediocre design’ problem, as described by the TDD Apostate, was being partially solved by having a template of objects and a few libraries for calculating distances between cities etc.

I am not going to go into length describing genetic programming, mainly because, although the principles rang true with me I seemed to misunderstand the practical in-code implementation side of it. This will probably be explained further in next months blog post, (the following Devnology get-together is solely about genetic programming - one more seat available at time of writing - gen pro workshop). In short there is a pool of data (genes) that are grouped into a finite group of solutions (chromosomes), of which the best/fittest n are selected. If any of these solve the problem then the answer is found, else the elite chromosomes are crossed, gene sequences mixing and matching with the odd mutation thrown in here and there. From these crossings and mutations the best survive and the rest become extinct. This repeats itself for generation after generation until an answer is found.

After a presentation explaining all of the above and more we got down to it. We had two laptops attached to beamers. Each laptop had two chairs in front of it, one for the driver (coder), one for the navigator. There was also a Whiteboard upon which the moderators, Stefan and Tjeerd Hans, kept a running note of what was planned for each coding pair. I will spare the details of each iteration, and not only because I am unable to read the notes, but the basics were the groups tried to apply the specification of the problem to the methodology, e.g., towns to genes, chromosomes to lists of towns, fitness to total distance between towns. These were approached in baby steps all precursor-ed (sometimes after cajoling) with tests and within the seven minutes presented by the timer (also sometimes requiring cajoling for the driver to leave the keyboard). Often there was refactoring (or just plain fixing) of the previous steps. Occasionally there was a bit of confusion as to how to deal with the BDD style, but otherwise it seemed to go swimmingly.

We didn’t finish the problem, but this was never a goal, time was too limited and there was so much new to learn. But we did learn much, and a ‘gezelig’ evening was had by all.

[So proud I managed to make it all the way through this blog post without once mentioning that, following a miscommunication with my diary, I arrived 24 hours early for this event, and in the process learned that the Devnology meetings are on the first Wednesday - and NOT the first Tuesday of every month. Needless to say the members of Devnology were very kind and didn’t mention this fact more than a few hundred times]

**[Devnology Coding Dojo 05-01-2011](http://www.slideshare.net/devnology/devnology-coding-dojo-05012011 "Devnology Coding Dojo 05-01-2011")**
View more [presentations](http://www.slideshare.net/) from [Devnology](http://www.slideshare.net/devnology).

News @devnologynl

There you have it: Devnology predicts 2027. Thanks all for sticking with us over the years! https://t.co/pMmr5PCztx

19-04-2017 at 20:01

Nerds talking the last 8 years, and making predictions for the next. https://t.co/VGT8XIFQ0j

19-04-2017 at 18:37

@_angelos opening the last Devnology meeting with a tweet of the first one he attended https://t.co/ufAYScx3cn

19-04-2017 at 17:08

Qwan 5dff39510bacfcefb54e89f953eddfc1a7a21185b7128d96ff6b466f56acb6d9
Macaw 06e9331a5321067b592bf45ea39db7df6792dc976000d24d3ee4043d99203514
Finalist e304343cdbeb0996cc1e7a26527993a5fa2db87ca53a81fb15dca22a35d7f28c

Devnology is a non-profit organisation and thus depends on sponsors. Thanks to our wonderful sponsors all Devnology events are free!