Software developer blog

The Bowling Game Kata with commentary

I have just released a code cast in which I do Bob Martins version of the bowling game kata in php, but take it further with a refactoring.

Web app crash course (Part 4)

In the previous part we have built a very simple chat application, but it stored messages in memory. Every time it was restarted, all messages were gone forever. In this part of the series we will look at MongoDB, a document database. There are many other database technologies, some of them are more frequently used than MongoDB, but for our purposes it is the best choice.

If you haven't read the previous parts, click here.

Web app crash course (Part 3)

In the first two parts we have examined how to create web pages using Sinatra and Mustache templates. In both cases we fed a small amount of data through the url, and then we returned something that was based on that data. However having to type input data into a url is not necessarily a good user experience, especially if we wish to send a larger chunk of data. In this part we will learn how to send user inputs properly.

Another problem we haven't addressed yet, is storing that data, so that we can show it later, and show it to other users, but that will be the topic of the 4th and final part of this series.

If you haven't read the previous parts, click here.

Web app crash course (Part 2)

In the previous part we dipped our toe into git, bundler, sinatra and mustache. In this part we will first explore how to add some interesting logic to our web application, while keeping that logic unaware of the very existence of the web. In fact we will go as far as to create a web app and a command line application that will do the same thing through different user interfaces. In the process of creating these applications we will also explore the realm of test driven development, a practice that can lead us to better software.

If you haven't read the previous part, click here.

Web app crash course (Part 1)

This is a beginner tutorial that shows you how to build a Ruby app using a certain set of technologies that I prefer to use. It will not make you a web developer right away, but it will show you the basics, and serve as a starting point for further reading. I assume that you already have basic knowledge ruby, HTML and CSS, or at least have read a tutorial that introduced you to them. If not, visit Codecademy. Another assumption I make, is that you are using Ubuntu (or possibly another Debian derivative) as an operating system. If not, you can download it free, and install it next to your existing operating system.

The approach I have taken is to show you most of the tools at once at a very low level, so that first you get the big picture, and then we will drill deeper later. This may be overwhelming at first, but bare with me, slowly everything will unfold.

By the end of the first part we will have a web page, that can say hello. Not much, but it's not the the goal we reach that will be of importance, but the way we get there. I will show you the tools developers use from day to day. We will look at how we manage gems, the building blocks of software development. Then we will look at some of those gems, most importantly Sinatra, that is designed to respond with web pages for requests of web browsers. We will also take a quick look at git, a tool, that is designed to store source code, and keep several versions of it around, so we can go back, when something goes wrong. Finally we will look, at how you can make your page look better with a Mustache.

Dynamic vs. Static types: the final battle!

On the first day of NDC London 2013 there was a cage match between Gary Bernhardt of Destroy All Software - known for the WAT talk, and Useing You're Type's Good - and Jon Skeet of Google - known for his "C# in Depth" book, and his activity on Stack Overflow. They were discussing the topic of dynamic versus static typing.

Jon Skeet started by asking, what is it that Ruby can do and C# can't. In response Gary tried to show stuff that seems idiomatic in Ruby, and relies heavily on the dynamic nature of Ruby. Where the discussion went a bit south was when Jon Skeet tried to do all that in C#, and did the ugliest hacks just to make it work, while relying on C# features that are explicitly there to make C# a bit more similar to dynamically typed languages. All that proves to me, is that C# is trying really hard to be Ruby, and sucks at it. So what? Besides, we all know that it's not true at all.

I personally have changed back and forth between statically typed and dynamically typed languages quite a lot, and both hated and loved them every time I did. After a while I started to have very exciting discussions between the left and right side of my brain. (Rest assured: we are not schizophrenic, although the rest of this blog entry may suggest differently.) The odd thing is that both of me seem to have realized that the other has interesting points to support his beliefs, but neither of me is willing to give up any of it. Instead I kind of became the devil's advocate on the matter. (And that's really funny if you know what my last name - Ördög - means in Hungarian.) Whenever I meet anyone who seems to strongly believe in one or the other, I try my best to convince them that they are completely wrong and total idiots. So if you came here with the intention of finding out which one is better, here is a final clue: you won't! However I promise there is an interesting conclusion at the end.

Let's give a name to my brains, just to make the rest more fun: Steve is a firm believer in static typing, while Dan is this ruby / nodejs fan boy.

If you wish to read a transcript of the video click here.
@ //

SQL on steroids

Few weeks ago we held an internal Coderetreat at Emarsys for all programmers within the company. When the business intelligence team heard about it they started to joke around, that they should drop by and implement Conway's Game of Life in SQL. I'm not much of an SQL wizard, but I rose to the challenge. First I tried it in MySQL, since that's the dialect I have the most experience with:

CREATE TABLE generations (`id` INT UNSIGNED, `x` BIGINT, `y` BIGINT);
INSERT INTO generations VALUES (0, 0, -1), (0, 1, 0), (0, -1, 1), (0, 0, 1), (0, 1, 1);
CREATE TABLE offsets (`x` BIGINT, `y` BIGINT);
INSERT INTO offsets VALUES (-1,-1),(-1, 0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1);
INSERT INTO generations 
  SELECT id, g.x+o.x x, g.y+o.y y
    FROM generations g 
      INNER JOIN offsets o 
    WHERE MAX(id) FROM generations)
    GROUP BY g.x+o.x, g.y+o.y
      HAVING (MAX(o.x=0 AND o.y=0) = 1 AND COUNT(1) - 1 BETWEEN 2 AND 3)
        OR (MAX(o.x=0 AND o.y=0) = 0 AND COUNT(1) = 3);

It works, and it's not even that complicated. First we join the last population with an offset table to generate the set of living cells and their neighbors. Grouping by the cell coordinates plus the offsets we can get all necessary information. The expression max(o.x=0 and o.y=0) is one exactly if the cell was alive in the previous generation, otherwise it's zero. Using that we can count the number of neighbors too: count(1)-max(o.x=0 and o.y=0). The having clause utilizes that knowledge to filter the grouped rows to contain only the cells in the next generation.

@ //

How to find maximal cliques

Facebook used to have this awesome list of programming puzzles that were freely available. One of them was peak-traffic, which can be rephrased as the maximal cliques problem pretty easily. Unfortunately a graph can have exponential number of maximal cliques, so it's not surprising that we can not find a polynomial algorithm for listing all possible maximal cliques in a graph. However there are output sensitive algorithms: as long as the number of maximal cliques is relatively low each can be reported in a short time.

A complete sub-graph of a graph is called a clique, much like we call a group of friends a clique if they all know each other.

I knew that I was looking for such an algorithm, but it was kind of hard to find a detailed enough description on the Internet.  At the time of writing Wikipedia does provide a short description of the algorithm devised by Tsukiyama et al. but there are a number of details omitted, making it kind of hard to come up with the right implementation.

My aim is to provide a simple to understand description of the algorithm (without proof that it works correctly) and share my implementation in C++. (Type `make smoke` to compile and test.) The source I've been using - apart from Wikipedia - was a 2004 paper written by Kazuhisa Makino and Takeaki Uno: New Algorithms for Enumerating All Maximal Cliques.

Unit test framework for C++ in about a 100 lines

Those who know me well are also aware of the fact, that I'm a very strong proponent of test automation and test driven development. Unfortunately there are times in our lives when installing an existing framework is not an option. So when I've been challenged to write a test framework that is so simple one can memorize it, and flush it out of their brain anytime needed, I was up to the task. The entire framework is 113 lines of C++ code, and using it is just as simple as using google test. Of course it doesn't come with all the features, it's fragile and has a good number of limitations, but it's good enough if you have absolutely no other option.

Here is how to use it, along with a sample output:

#include "TestBase.hpp"
class TestGroup : public TestBase {
Sample output

Sample output of a simple unit test framework

Game of Life on the GPU

Conway's Game of Life is one of the most popular code katas, and the one we will exercise on our next code retreat this Saturday. I have done this kata, quite a number of times, but this time there was a twist: I used the GPU on my Nvidia GTX 560 to calculate the steps of evolution, and to draw them as well. Here is how the result looks like:

Puffer train in Game of Life

Puffer train in Game of Life. Living cells are green, they increase the blue chanel by 1 in each generation, and leave a faiding red trail after they die.

The igniter of this exercise was that I read a book on CUDA programing, and it was quite a disappointment. The examples were really far from anything I would call clean code, or at least easy to understand: it was spaghetti with huge meatballs in it. That kind of examples require a lot of explanation, which basically took up most of the books volume, and there was little left for the useful stuff. So I got curious: is it CUDA that promotes bad code, or the writers of the book didn't care enough? I had a preconception that there was nothing wrong with CUDA  - and actually it's a pretty neat language - so I set out on a quest to code Game of Life in CUDA, and try to make it as clean as possible.  I don't claim, that my code is perfect, but I hope it's going to be an easy read for anyone who tries.

You can download the result of my quest by clicking here, or just browse it as HTML by clicking here. The rest of the blog entry - basically a retrospective of the project, and a few remarks on CUDA features - might not make much sense without looking at parts of the code. If you'd like to compile, than you will need the nvcc compiler for CUDA, the CUDA Toolkit, GLUT and GoogleTest to run my unit tests. Please note, that the code is not production quality: it may well throw exceptions at you, it's only tested on Ubuntu, and it is not performance optimized in any way. (Even the algorithm is the most naive one.)

@ //
Next Page »