Verslag Coding Dojo TSP
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]
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