Scribe: ? (Hugo Corbucci)
Kata: The Settlers of Catan (acm.uva.es/problemset/v5/539.html) in Ruby
20:15 ~ 20:30 Choosing and Discussing the Problem (as Usual)
20:30 ~ 22:00 Coding Session
The problem started as a RandoriKata with FabricioSousa presenting the start of his solution and the audience involving on it later on, switching every 7 minutes as usual. The problem evolved until we reached a test where the greedy solution wouldn’t solve anymore. Then we stopped coding to explain what was the problem (longest path search) and why it is a NP-complete problem. This leaded to the discussion about what was the brute force solution to it and MarianaBravo wrote down a pseudocode on the board with the audience that seemed to solve the problem. We didn’t have time to code it. However the code produced is available at groups.google.com/group/dojo_sp/files.
22:00 ~ 22:15 Retrospective
Some of the lessons learned from the session were: shortest path is easy, longest path is not. NP-complete problems are usually solved by brute force recursively (resulting in a neat small code).
Action Items for the Future
- Implementing the pseudocode inRuby