Codility Challenge “Argon 2015” solution

Codility might not be the best way to assess a candidate (especially if it is the only one!), but there is definitely something in it that I like. The idea of my solution to a programming task being automatically evaluated after I deem it ready is not unfair—after all, programs are run by machines and have to be correct, efficient (more or less, depending on the context), and handle corner cases.

But the thing I like most of Codility are, of course, the challenges. I find them both difficult (I envy those who can solve them in 15 minutes at the first attempt) and fun. For me they are more workable than Project Euler’s problems, which are indeed interesting but difficult to understand if you don’t hold a degree in mathematics.

Good solutions for Codility challenges are not easy to find, and when you find one, in most cases it’s a huge blob of code with no explanation. Let’s try to solve Argon 2015 step by step. Read more...


Boost coroutines instead of state machines? Maybe...

If you are reading this post you are probably already familiar with the concept of coroutine.

If you are not, let’s say coroutines are a way to have cooperative (non pre-emptive) multitasking, possibly on a single thread. You can have multiple flows of execution that yield control to each other without being pre-empted, and without using threads, semaphores, and condition variables. In simple terms, coroutines are an extension to the concept of function: while functions cannot be resumed after “returning,” coroutines can be resumed from where they were suspended when “yielding” to another coroutine.

There is no language support in C++ for coroutines, but some libraries are available, that use some platform-specific code and a few ingenious hacks to make coroutines possible in C++. A noteworthy one is Boost.Coroutine, based on Boost.Context, a low-level library capable of doing the “magic” of a userspace context switch.

I had problems myself understanding coroutines when I saw them for the first time, and I consistently find it difficult to explain them to other developers, however smart and experienced. I think that parsing stream data is a good case study that makes it immediately understandable what coroutines can give you in real-world applications. When you parse data coming from a stream you have limited control on (e.g. a socket), you often end up coding a state machine that consumes one byte at a time, as the data you are parsing may be coming to you chunked in various ways. In this post, I will introduce a simple C++ example of a coroutine-based parser, present a few benchmarks, and try to cause in you mixed feelings about Boost.Coroutine by showing you a few pros and cons of using it. Read more...

Tags: cpp, boost

Variadic C++ functions for packing and unpacking bits

Shall you need variadic C++11 functions for packing and unpacking (a few) bits, here is what I have done for myself.

In most cases it's probably better to use std::bitset or any other container, but these two functions may provide a quick and easy way to pack some bits into an integer and the other way around, without using any specific class or container. Read more...

Tags: cpp, cpp11

Avoiding code duplication between const and non-const methods

Sometimes const and non-const methods in C++ classes share the same name, body, and return type (except for the const keyword), thus causing code duplication.

The problem is described in this StackOverflow topic, and somewhere else on the Internet. The obvious solution is to refactor the code in order to avoid duplication while preserving const-correctness and semantics, but sometimes this is not possible or not convenient. A popular (and effective) solution requires a const_cast and a static_cast. In this post, I suggest an alternative (and I think safer) solution. Read more...

Tags: cpp, cpp11

Another (iterative) technique for enumerating permutations

The idea of writing this post came up by reading Programming Interview Questions 11: All Permutations of String by Arden Dertat. The author proposes a simple and elegant recursive algorithm that finds all the permutations of a given string.

If any of you is interested in an alternative (iterative) solution, here is one. I think it has a couple of features you may find interesting.

The starting point is to define an order among all the permutations and then write a procedure that, given a permutation, returns the following one. The order is simply the lexicographic order and the procedure is the following. Read more...

Tags: algorithms, cpp
Fork me on GitHub