Alternative phone number conversions

The problem was converting lowercase letters (and blanks) to numbers, following the rules used by the phone keypad. In a previous post I gave a possible C++ solution, and I got as feedback a couple of alternative solutions. It is interesting to compare them, to see different approaches taken by different programmers.

Arthur's solution is on github. In a few words, he loops on the input string, calling for each character a support function named encodeChar() that returns a pair where first is the resulting number, and second the number of needed repetition.

The encodeChar() function delegates to the compiler the task of generating a string that maps the valid character to the relative expected position, filled with underscores for invalid positions. Then find() is used to get requested character and its multiplier.

Interesting features of this solution:

- C++11 range-based for loop. Code is more compact and readable.
- Use of STL data structure and algorithms.
- The lookup table is ingeniously mapped to a single string.

Some more chatting could be done on:

- C++11 use of the auto keyword. Using it when it is not a necessity (or a nice shortcut that improve readability) just makes code less clear. For instance, the C++11 std::stol() always return a long int, there is no advantage in assigning its returned value to an auto variable.
- Mapping the lookup table to a single string full implies that we should use find() to get converted character and its multiplier. We should be aware that find() has O(n) time complexity, against O(1) of a lookup table.

I couldn't help to rewrite the function main loop to get rid of the temp variable used to keep track of the last inserted key. Admittedly, it is just a minimal improvement, still, I nerdly fill better to see the code changed in this way:

for(char c : input)
{
  Token token = encodeChar(c);
  if(!output.empty() && token.first == output.back())
    output += ' ';
  output += std::string(token.second, token.first);
}

Anonymous put his solution on ideone, compiled on C++11 (gcc-4.7.2). I guess he is a fan of generic programming, and his job is a cool example of this technique. The main issue here is that there is no reason, beside the fun of writing it, to come out with such a complex piece of code to solve this problem. So it sorts make sense that he named his lambda function that determines the associated key for the current letter "magic", because it takes a while to understand it, and at first sight it looks really as it works for a kind of magic.

It is difficult to summarize the good stuff we could see in that piece of code, nice use of templates, decltype, auto declarations, and a static assertion to check at compile time the generic function actual correctness. I think it could be used as an introductory example to generic programming.

There is only a (minor) issue in the code, it does not manage consecutive blanks. In the t9_transform() main loop, there is a "else" that covers the blank case (assuming nothing else than lower case letters and blanks are in the input string). There we should add a check on the previously checked character, as we do in the "if".

More interestingly, I spent some time understanding how "magic" actually works. To show how it works, I think it could be useful to see the original one-liner lambda converted to an equivalent "normal" longish function. For sake of simplicity, I sacrificed the genericity of magic(), writing a char2rep() that works only for plain chars:

auto magic = [](decltype(*f) i) { return '2' + std::min(7, (i - (i >> 4)) / 3); };

char char2rep(char input)
{
  if(input == 'z')
    return '9';

  int shift = input > 'r' ? 1 : 0;
  int code = input - 'a';
  return '2' + (code - shift) / 3;
}

To understand how magic() works, we have to think about what it wants to achieve. Any number in the keypad, starting from 2, is the result of the conversion of three consecutive letters. If the number of letters was a precise multiple of three, the function would have been trivial. But there are two keys, 7 and 9, that should map four, and not three letters. So we have to plan for a couple of adjustment.
If the input letter is bigger that 'r', we need to shift one position, and the last character, AKA 'z', should follow a special rule. For magic() the trick is done maximizing the shift to 7, alternatively, we could just say that 'z' is converted to '9'.

So, after all it was no magic, just an obscure piece of code ;)

Go to the full post

Prime number checker

Writing a general algorithm to check if a (positive integer) number is a prime is a too complicated matter to be discussed here (and to be asked as a interview question for a programmer position). Have a look at the Manindra Agrawal, Neeraj Kayal, Nitin Saxena document where they "present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite", friendly known as AKS algorithm, to see what I mean.

Still, if our requirements are not very strict, and we are happy enough with a function that has reasonable performance only for small numbers, it is a different matter.

A couple of thousands years ago, a very smart guy named Eratosthenes of Cyrene had prime numbers among his many interests. He devised the algorithm known as the sieve of Eratosthenes that could still make sense to use.

The algorithm is designed to return all the prime numbers in an interval, so using it to check just a single number is a kind of an overkill. About the same of what happens for similar algorithm to calculate factorial or Fibonacci numbers.

I want to write a function following this declaration and passing the below stated test case:

bool isPrime(unsigned long long value); // 1

TEST(TestPrime, Eratosthenes)
{
    EXPECT_FALSE(isPrime(42));
    EXPECT_TRUE(isPrime(977));
    EXPECT_TRUE(isPrime(4987));
    EXPECT_FALSE(isPrime(999999997));
    EXPECT_TRUE(isPrime(32416190071));
    EXPECT_TRUE(isPrime(99494896918097));
    EXPECT_TRUE(isPrime(997080383502859));
    EXPECT_TRUE(isPrime(2305843009213693951)); // 2
}

1. I'd like my function to be able to manage very big numbers. It should accept a not negative huge integer in input and answer with a boolean.
2. This 19 digits integer is known as Mersenne M61, or Pervushin's number, we know it is a prime number since 1883, and I could consider myself happy if my function could check it in a reasonable time.

Here is how I implemented the solution:

bool isPrime(unsigned long long value)
{
    if(value < 2) // 1
        return false;
    if(value < 4)
        return true;
    if(value % 2 == 0)
        return false;

    long max = static_cast<long>(std::ceil(std::sqrt(static_cast(value)))); // 2

    for(long i = 3; i <= max; i += 2) // 3
        if(value % i == 0) // 4
            return false;

    return true;
}

1. Get rid of trivial cases. Zero and one are not considered prime numbers; two and three are OK; all the even number bigger than two are not prime.
2. Optimization. If we want to check if 101 is a prime number, we don't have to check all the previous number till 100, we can stop checking an awful long before. It is enough to check till the next integer after its square root (and if you think about it, you should understand why).
3. Let's loop. We need to check for all the possible odd divisors starting from three. Actually, we don't really need to check a lot of them, like nine (being a multiple of three), but there is no cheap way of keeping track of which one has to be checked and which not. It is easier doing in this way.
4. Divide our input number for the current candidate. It could be the end of our job, otherwise try the next one.

Go to the full post

T9 spelling

The third part from the Code Jam Qualification Round Africa 2010 was pretty easy to solve. Basically, we have to write a translator that converts a string that could include only lowercase standard English characters and blanks, to a sequence of numbers (and blanks that act as special characters), following rules similar to the ones that we use when composing text messages on a basic mobile phone.

For instance, for an "f" we get three 3, and for "oo", we get "666 666". As you can see, the pause we have to do to enter a character based on the same coding number is represented by a blank.

As usual, I'm using C++ as implementing language, and here I report only the core of the solution, the definition for a function declared as here below. I let the development be driven by test cases, here I show just one of them:

std::string t9(const std::string& input)

TEST(TestT9, Case4)
{
    std::string input = "hello world";
    std::string expected = "4433555 555666096667775553";

    std::string output = t9(input);

    EXPECT_EQ(expected, output);
}

I couldn't think of any smart solution to this question, so I played safely, using a lookup table to convert each possible input character to an output sequence. The English alphabet has 26 letters, in the table I will put as 27th element the translation for blank, a zero:

const int NR = 26;
char* CONVERSION[NR + 1] = { "2", "22", "222", "3", "33", "333", 
    "4", "44", "444", "5", "55", "555", "6", "66", "666",
    "7", "77", "777", "7777", "8", "88", "888",
    "9", "99", "999", "9999", "0"
};

The array reads: An 'a' becomes "2"; 'b' "22"; ...; 'z' "9999"; and ' ' "0".

Now I should write a piece of code to loop on all the letter in the input string (no error handling required, still would be better to spend at least a few minutes thinking to a more robust solution), convert each letter in an index for the conversion table (blanks require a bit of caution), put the resulting sequence in the output string. And remember to put the blank separator where required:

std::string t9(const std::string& input)
{
    std::string output;
    std::for_each(input.begin(), input.end(), [&output](char letter) // 1
    {
        int index = letter == ' ' ? NR : letter - 'a'; // 2

        if(!output.empty() && *output.rbegin() == CONVERSION[index][0]) // 3
            output += ' ';
        
        output += CONVERSION[index];
    });

    return output;
}

1. To implement the loop, I combined the standard algorithm for_each() with a lambda function (how could I live without them). In the lambda capture specification I put the string output, so that it can be seen inside the function body. The parameter passed to lambda is the letter currently selected by the for_each() algorithm.
2. Convert the input letter to an index for the lookup table. "Normal" characters, in the range a-z, require a subtraction by 'a', so that for 'a' I have the index 0, up to z that has index 25. What for blank? Twenty six. Or, as I put it, the last element in the array. But what happens if an unexpected character is in the input string? A catastrophe. A real piece of code should avoid it (throwing an exception, maybe).
3. Before appending the selected sequence to the output string, we check if we need a blank, to signal that we are entering a new sequence using the same number code as the previous one. To do that, we check the last character we have already appended to the output. This is a two-step condition. Firstly, we check that the string is not empty, otherwise there is nothing to check. Secondly, we get the last character in the output string, and we check if it is the same of a character in our current sequence. It could be worthy to spend a few extra words on the way I used to extract the last character from the output string:

*output.rbegin()

In plain C, this simple job is a pain. The trouble is that good old C-string is just a pointer to the beginning of the memory block occupied, and to get its last character we are forced to get its length first. The STL C++ version of a string is much more smarter that this. It knows where it begins, and ends. To get the first character of a string, assuming it is not empty, we could simply dereferencing the iterator to its begin, something like *output.begin(). But here we want the last character. One way to get it, is dereferencing the iterator to the reverse begin of the string.

As Arthur pointed out (see comment below), output.back() is more compact and expressive than *output.rbegin(), and leads to the same result. Why don't use it instead? No reason at all, if you use a recent enough C++ compiler. The element access function back() has been added to the STL string class interface in C++11, like front(), and a few other useful methods. Be at least prepared to see it in legacy code.

Go to the full post

Reverse words

The second problem proposed in the Google Code Jam Qualification Round Africa 2010, asks to revert the words in a number of strings given in input. It is a simpler request than the first one in the round, but still there are a couple of points worth of spending some thinking.

The core of the question is defining a function like this (if you solve it in C++):

std::string revert(const std::string& input)

I have written a few test cases to drive the development, like this one:

TEST(TestRevert, Case1)
{
    std::string input = "this is a test";
    std::string reverted = "test a is this";

    std::string output = revert(input);

    EXPECT_EQ(output, reverted);
}

Then I spent some time asking myself how to actually implement the function. My first idea has been to use an input string stream to extract the words from the string, put them in a container, and then, via an output string stream, generate the output string.

It is not the best solution that one could came out with, in term of efficiency, but it has the advantage of being clean, easy to write, and event kind of fun.

Let's see it:

std::string revert(const std::string& input)
{
    std::vector<std::string> words;
    std::istringstream iss(input);
    std::string item;
    while(iss >> item)
        words.push_back(item); // 1

    if(words.empty())
        return ""; // 2

    std::ostringstream oss; // 3
    std::for_each(words.rbegin(), words.rend() - 1, [&oss](const std::string& cur) // 4
    {
        oss << cur << ' ';
    });
    oss << words[0]; // 5

    return oss.str(); // 6
}

1. I loop on the input string stream until there is something in it. By default, all blank characters are discarded by the put-to operator, so I just have to push back any word I get in the buffer container.
2. What if nothing was in the input string? I simply return an empty one.
3. Otherwise, I want to loop backward on all the collected words, putting in the output stream any single word followed by a blank. With the noticeable exception of the last one, that has no following blank.
In C++ you could do that using the for_each() STL algorithm, delimiting the range with the reverse iterators rbegin() - pointing to the last element in the collection - and the decremented rend() - pointing to the first one (remember that the "end" element in a iteration is the first out of the selection).
4. As functional to be executed on each element in the range, I defined a lambda function (I love them). If your compiler do not support them, I am sorry to say you have to rearrange the code, probably using a functor, or a plain for loop. In the capture clause I specified the above defined output string stream, passed by reference, so that we can use it inside the lambda body.
5. The first word in the collection is the last element sent to the output stream.
6. Finally, I extract the string from the stream, and I return it.

I like this code, still it has a couple of issues. Most importantly, it could be too expensive. If we have to process lots and lots of input lines, creating and using all those string streams could be easily become a pain.

This second version is stream-free, as this means faster. You could even get rid of STL strings, but you will pay this extra performance gain with an extra code readability loss. For our requirements, I assumed this is enough:

std::string revert(const std::string& input)
{
    std::vector<std::string> words;

    size_t beg = 0; // 1
    size_t end = 0;
    do {
        end = input.find(' ', beg); // 2
        std::string word(input.begin() + beg, (end == std::string::npos ? input.end() : input.begin() + end)); // 3
        words.push_back(word);
        beg = end + 1; // 4
    } while(end != std::string::npos); // 5

    std::string output;
    output.reserve(input.length()); // 6
    std::for_each(words.rbegin(), words.rend() - 1, [&output](const std::string& cur) // 7
    {
        output += cur;
        output += ' ';
    });
    output += words[0];

    return output;
}

1. I use a couple of variables to keep track of the beginning and end of a single world in the input.
2. Search the end of the word starting on beg (first iteration, beg is zero). If there is no blank after beg, find() return string::npos to signal it.
3. Let's build a word, starting from begin() + beg, and ending to end(), if no blank is found, or to the actual blank position.
4. The new beg value is the next one after the current end, meaning, the first character after the last used blank. Actually, it doesn't much sense to assign to beg string::npos + 1, how it happens in case no blank has been found, but it is harmless (see next point for the reason).
5. We loop until end is string::npos, that means, we have already scanned the complete input line.
6. Let's generate the output string. I know its size (same as input), so I (possibly) save some time specifying it.
7. The output construction loop is almost the same as in the previous version. What changes is that I work on the actual STL string, and not on the string stream.

Go to the full post

TopCoder Username

Another common source of interview questions is TopCoder, a site that hosts a huge variety of developer competitions. They have a standard format for tests, presented in their How to dissect a TopCoder problem statement page.

As example, they provides a few questions they have used in the past. First of them is the UserName problem. In a handful of words, we have to write a function that ensures the chosen username is available or, if not, propose a viable alternative.

I simplified a bit the required interface, tailoring it for C++. Now, my requirements are that we should write a function respecting this prototype:

std::string check(const std::string& input, const std::vector<std::string>& existing);

Where input is the username submitted by the user and existing is the list of already taken usernames. The function has to return a valid username, preferably the one chosen by the user. If the requested username is already taken, we will return it with a concatenated number - the smallest, the better.

As usual, before start coding, I have written a few testcases. Here is just one of them:

TEST(Username, Case0)
{
  std::string input("MyUsername");
  std::vector<std::string> existing = { "Taken", "Someone", "Hello", "Nickname", "User" }; // 1 

  ASSERT_EQ(input, check(input, existing)); // 2
}

1. I have written this code on a recent GCC compiler, so I took advantage of C++11 initialization for STL vectors.
2. The passed username is not among the list of already existing ones, so I expect to get it back as result of function call.

And here is my solution:

std::string check(const std::string& input, const std::vector<std::string>& existing)
{
  std::set<std::string> orderedNames(existing.begin(), existing.end()); // 1
  if(orderedNames.find(input) == orderedNames.end()) // 2
    return input;

  for(int i = 1; ; ++i) // 3
  {
    std::string candidate = input + boost::lexical_cast<std::string>(i); // 4
    if(orderedNames.find(candidate) == orderedNames.end())
      return candidate;
  }

  // we should never reach here
  throw new std::exception();
}

1. Seeing the requirements, the expected code complexity is not an issue, still I reckoned it was wise to be prepared for a huge vector of existing usernames. In that case, it is worthy to create a set so that we have them ordered, and looking for an element has a cheap O(log n) cost.
2. If the input is not among the existing items, return it.
3. We check until we find a good alternative candidate - so, I used an open ended for loop.
4. Username candidates are build concatenating the user input with a integer, starting from 1. Among the many possible ways of converting an int to a string, I've chosen the boost lexical cast.

Go to the full post

Store credit code jam

I have found out that a common source of interview questions is Google Code Jam. You can practicing for this contest seeing what they did in the past editions, and there you can find interesting problems. The other day I have played with the first one proposed, part of the Qualification Round Africa 2010.

The core of the job is writing a function that gets in input an integer, representing an amount that we want to spend, and an array of integers, representing the cost of any single item that we could buy.

We know for sure that exists one and only one pair of values in the array respecting the condition:

total = first + second

Total is given, our task is returning the indexes in the array for first and second.

I avoid discussing the code around the function, that is pretty boring. It deals about reading from the input file provided by Code Jam and creating the relative output file in the expected format. Being C++ the language that I used, it was a matter of opening an ifstream, calling getline() on it a few times, converting strings to int (atoi sufficed), and extracting integers from a string (istringstream came handy). Then I created a ofstream, and put to it the results.

I should handle couples of values, so I am going to use std::pair, that I typedef'ed it Choice, to make it a bit more expressive. The function itself takes in input the total and the available values, and gets back the pair of indexes:

typedef std::pair<int, int> Choice;

Choice getChoice(int total, const std::vector<int>& input);

Before let my program work with the actual input data, I have written a few test cases, that I used to drive my code development. Here is just one of them:

TEST(TestCredit, Case1)
{
    const int TOTAL = 100;
    const int VALUES[] = {5, 75, 25};
    std::vector<int> values(VALUES, VALUES + sizeof(VALUES) / sizeof(int));

    Choice choice = getChoice(TOTAL, values);

    EXPECT_EQ(2, choice.first);
    EXPECT_EQ(3, choice.second);
}

And here is how I implemented the function:

Choice getChoice(int total, const std::vector<int>& input)
{
    typedef std::vector<int>::size_type ST;
    for(ST i = 0; i < input.size() - 1; ++i) // 1
    {
        if(input[i] >= total) // 2
            continue;

        for(ST j = i + 1; j < input.size(); ++j) // 3
        {
            if(input[i] + input[j] == total)
                return Choice(i+1, j+1);
        }
    }

    return Choice(); // 4
}

1. Admittedly, this implementation is quite brutal. Still, we didn't get tough requirements on time complexity, and we need to produce some working code quickly. So, I reckoned this plain Oh-n-square algorithm should be enough.
2. We need two values, so the first one should be smaller than the total. If this is not true, we skip to the next iteration.
3. Let's check all the values after the current one. If we found the happy couple, return it.
4. We should never get it, accordingly to the requirements. So I return the "bad" pair (0, 0). I could have thrown an exception, to make things more clear.

My test cases OK'd it, so I ran my application against the data provided by Code Jam (Oh-n-square performance was not a problem at all), submitted the results, and got the confirmation that all works alright.

In the comment to the post, Arthur passes a link to a github page with his two solutions to this problem. As Arthur says, one is quite similar to the one I have already presented, the other one it looks to me overly complicated, and probably an example of premature optimization (root of all evil!). I found more interesting the simple one, that makes uses of STL and C++11 features. On its dark side, it abuses of the C++ meaning for the auto keyword, and it loops by while, in a way that seems to me less natural than by for.

Using the Arthur suggestions, I'll rewrite the getChoice() in this way:

Choice getChoice(const int total, const std::vector<int>& values)
{
  typedef std::vector<int>::const_iterator IT;
  for(IT it = values.begin(); it != values.end() - 1; ++it) // 1
  {
    int first = *it;
    if(first >= total)
        continue;

    IT it2 = std::find_if(it + 1, values.end(), [first, total] (const int second) { // 2
      return first + second == total;
    });
    if(it2 != values.end()) // 3
      return { it - values.begin() + 1, it2 - values.begin() + 1 };
  }

  return { 0, 0 }; // 4
}

1. Instead of a plain old for loop, a loop on an iterator interval is more expressive.
2. The internal loop could be rendered with a call to the STL find_if() algorithm couple with a lambda. This line could be read: return the iterator to the element in the vector in the interval starting from the next to the current element, ending to the natural end of the range, that satisfies the requested relation (first plus second equals total).
3. If find_if() fails, it returns the end() iterator to the container.
4. Using the new C++11 notation to create a Choice (that is, a std::pair) could actually result more natural.

Go to the full post

Palindrome string

You know what a palindrome is, right? For instance, SOS by ABBA, is a song with a palindromic title played by a pop group with a palindromic name.

It is easy to write a function that detects if a string is a palindrome, so an interviewer sometimes asks it as a first question, just to break the ice.

Here is a no-frills implementation in C:

int cPalindrome(const char* input)
{
    if(input == NULL) // 1
        return 1;

    int len = strlen(input); // 2
    for(int i = 0; i < len / 2; ++i) // 3
    {
        if(input[i] != input[len - i - 1]) // 4
            return 0;
    }

    return 1; // 5
}

1. If the caller pass a NULL, should we consider it a palindrome or not? It is questionable, at it should be a matter of a little chat to decide what the expected behavior should actually be. I voted for the most permissive option.
2. Painfully, we have to loop on the string once, just to get its length. But we have no choice, we can't even start checking the string if we don't know where is its end.
3. We check each couple of elements, moving from the extremes to the center.
4. As soon as we detect a mismatch, we return a "No, sir, this is not a palindrome!".
5. All string checked (notice that it could be even an empty one), no difference spotted, we claim it is a palindrome.

We can rewrite it in C++, and the result is an amazing one-liner:

bool palindrome(const std::string& input)
{
    return std::equal(input.begin(), input.begin() + input.length() / 2, input.rbegin());
}

Right, one line, but an intense one. There are a few things to notice.

No check on NULL string. It is not possible to convert a NULL to a string object, so such test, when required, should be moved outside the function.

To compare the elements in the string, I used the STL equal() function (defined in the algorithm include file). First two parameters are the delimiter for the first sequence to be checked, third one is the begin of the second sequence. Notice that the third parameter is rbegin(), the "reverse begin" of the string, the iterator to the last valid element of the container (or, in this case, string) that, incremented, moves to the left, and not to the right, as we usually expect in an iterator.

A variation to this classical question, is asking to write it as a recursive function. Here is a possible C++ implementation:

bool rPalindrome(const std::string& input)
{
    if(input.length() < 2) // 1
        return true;
    if(input.front() == input.back()) // 2
        return rPalindrome(input.substr(1, input.length() - 2)); // 3
    return false; // 4
}

1. Empty strings, or single-character ones, are palindrome, without need of any other test.
2. The current string has more that two characters, let's check the one to the extreme left with the one to the extreme right. If they are the same, the string is a palindrome if and only if the internal string is (recursively) a palindrome.
3. So we check the internal string, that is extracted from the current one using the STL string::substr() method.
4. Otherwise the current string is not a palindrome.

Go to the full post

Reading about ZeroMQ

I have just got this book, ZeroMQ - Use ZeroMQ and learn how to apply different message patterns, written by Faruk Akgul for Packt Publishing, and I about to read it. Some more substantial feedback in the near future.

It is a bit under my level, since it is thought for C developers at their first experience with ZeroMQ, but it is a while I don't actually work with this fine framework, and I felt it would be nice to have a refresh of the basic concepts starting from a different perspective.

Browsing the index, you could see how the book is structured to provide an introduction to ZeroMQ, letting you know how to write a simple C client-server application, describing how it works. Chapter two is mainly dedicated to a couple of messaging patterns, pub-sub and pipeline, and there is also a section dedicated to Valgrind, and how to use it to detect memory leaks on 0MQ. Chapter three gives more details on what a ZeroMQ socket is, and how to use it. In its second part, an introduction to CZMQ, the high(er) level C wrapper to the standard ZeroMQ library, is given. Chapter four delves a bit more on some more advanced topics.

The code in the book has been written for ZMQ version 3.2, and CZMQ 1.3.1; for what I have seen, the building instruction are provided only for the GCC compiler (version 4.7.2 is cited, I quite confident the newest 4.8 would be alright).

On Windows, Visual C++ is the suggested compiler. I couldn't see any detail on how to set MSVC for ZeroMQ in the book, still I could assure you that it is very easy to build a ZMQ solution in that environment too. If you need an hint, have a look at this ancient post of mine, that should be still valid.

Go to the full post

Matching bracket

Think of a string (it could be very long) composed exclusively by round brackets (aka parentheses). We want to check if it is correct, in the sense that each open bracket should have a matching close one. So, a string starting with a ")" is considered wrong, while the "()()()" string is a good one. Nested brackets are allowed, so "((()())(()()))" is a good sequence.

It is not difficult to think to a solution, still, you should not forget that unharmful looking hint on the possible large input size.

I bumped into this problem when having a coffee-break with colleagues. We were talking about interview questions, and someone remembered this one. In a few minutes we envisioned a couple of possible solutions, neither of them looked satisfactory. After a bit more of talking, and we found out a third candidate, that looked quite good.

First attempt

Naively, we could iteratively remove each "()" from the input string, until we could not find anymore such pattern. After that, we simply check if the string is empty. The good thing about this solution is that is easy to describe and implement. Less convincing is that we should copy the input to a buffer, and then perform on it a lot of splitting and splicing of substrings.

Let's see a possible C++ implementation of this idea:

bool simpleChecker(const std::string& input)
{
  std::string buffer(input);

  if(buffer.empty()) // 1
    return true;

  if(buffer.length() % 2) // 2
    return false;

  while(true)
  {
    std::string::size_type pos = buffer.find("()"); // 3
    if(pos == std::string::npos)
      break;

    buffer.replace(pos, 2, ""); // 4
  }

  return buffer.empty(); // 5
}

1. The requisites do not say if an empty string should be considered valid or not. Let's assume it should.
2. If we have an odd number of elements, the string is obviously invalid.
3. We stop looping if we can't find a "()" element.
4. When we find a "()", we replace it with an empty string (i.e., we remove it).
5. If the string is empty, the validation succeeded.

This code works fine, even for moderately large strings. In the best case, a monotonous sequence of "()()()()", the standard string replace() function is so nicely written that on my machine it takes a handful of millisecs to check an input of thousands characters. On the other side, it is easy to spot a sequence that gives troubles to replace(). The test case here below takes me something around one second on a 50K string:

TEST(CPPSimple, FiftyKWorstCase)
{
  const int SIZE = 50 * 1024;

  char buffer[SIZE + 1];
  for(int i = 0; i < SIZE / 2; ++i)
    buffer[i] = '(';
  for(int i = SIZE / 2; i < SIZE; ++i)
    buffer[i] = ')';
  buffer[SIZE] = '\0';

  EXPECT_TRUE(simpleChecker(buffer));
}

And his bigger brother, 250K sized, takes something like half a minute.

Recursive approach

The main issue of the first try is that it modifies the string. A better approach would be checking the string for each matching parenthesis, without doing any change. We read the first character in the passed string, it should be an '(', if the next one is a ')', cool, we have completed a sequence, we can move to the third character. Otherwise, we call recursively the same function, to extract a subsequence. It should return the length of the found sequence, or zero, if the subsequence is not valid. The caller would check the returned value, and move in the string accordingly, to see if the next character closes its sequence, or if it has to call again itself to check if we have another subsequence.

As you can see, this solution is more contrived, but promises to be more performant. Still, it has a big issue. In the same worst case as seen above, we have such a huge number of recursive function calls that it could easily lead to corruption in the memory stack.

Just count them

Yes, just count the brackets. After all, what we want is having the same number of open and close parenthesis.

Actually, we have also to take care that we don't want to see a close bracket when there is nothing to close, but it is easy to take care of it. Each time we have an open bracket, we put it on a stack, and we pop out one of them as we get a close bracket. If we get a closing bracket before any opening one has been scanned, the stack is empty, and so we know the string is not correct.

Here is how I have implemented this solution:

bool stackChecker(const char* input)
{
  int tracker = 0; // 1

  for(int i = 0; input[i] != '\0'; ++i)
  {
    switch(input[i])
    {
    case '(': // 2
      ++tracker;
      break;
    case ')': // 3
      if(tracker)
        --tracker;
      else
        return false;
    } // 4
  }

  return tracker ? false : true; // 5
}

1. I use this integer as the stack I talked above. Since I am not interested in the actual position of the brackets, I don't need a real stack, I just need to keep track of how many open brackets have been read.
2. I see an open bracket in the string, put it in the stack, and go to the next character.
3. Close bracket. If the stack is not empty, it matches with the last open bracket in the stack, I pop it and I am ready to check the next one. If the stack is empty, the input string is not valid.
4. What if the string contains anything else? I assumed a "don't care" behavior, but possibly the string could be considered invalid. If that is the case, a default section should be added to the switch, to always return false.
5. The complete string has been scanned, if no open bracket is left in the stack, we consider it valid.

Go to the full post

Redis client testing

I am a TDD guy. If I don't write some test cases, even for simple stuff, I feel uneasy. So, when I wrote the unique and the shared Radis wrappers for the previous posts, I let some (very basic) tests drive my code development. I guess it could be useful to have a look to them. The full C++ code is on github, you would need Google Test, Redis and its hiredis plugin, and a C++11-compliant compiler to build it. It won't be difficult to refactor the code for a different test framework (better if xUnit-based), and for a less modern C++ compiler, using Boost (or another library) for smart pointer support.

Firstly, I have written a tiny wrapper class to Google Test, just to make the code less messy, in Tester.h:

class Tester
{
public:
    Tester(int argc, char** argv) { testing::InitGoogleTest(&argc, argv); } // 1

    int run() { return RUN_ALL_TESTS(); } // 2
};

1. Before running any test, we should initialize the environment. What a better place than a constructor to do that?
2. I am happy with a very basic usage of Google Test, I would simply run all the tests.

Then I have written a simple main function, that creates an object Tester, and run it:

Tester(argc, argv).run();

I don't even use the return value from run(), I rely on the output generated by Google Test to let the user understand how the testing behaved.

Finally, I put in a source file all the tests I want to be performed. Here are some of them:

TEST(TestConnectShared, BadPort) // 1
{
    TTR::SharedRedis redis(1234); // 2
    ASSERT_FALSE(redis.isConnected()); // 3
}

TEST(TestConnectShared, Vanilla) // 4
{
    TTR::SharedRedis redis;
    ASSERT_TRUE(redis.isConnected());
}

TEST(TestCopyShared, Copy) // 5
{
    TTR::SharedRedis redis;
    ASSERT_TRUE(redis.isConnected());
    TTR::SharedRedis r2 = redis;
    ASSERT_TRUE(r2.isConnected());
}

1. The TEST() macro requires a test case name (here is TestConnectShared) and a test function name (BadPort). These names should make clear what we are testing here. In this case, I want to check the shared Redis connection behavior when I pass a wrong port number. Notice that the prerequisite is that the Redis server is up and running on localhost, default port.
2. I have put SharedRedis in a namespace named TTR (short for ThisThread Redis), that's way I use that prefix here.
3. I expect isConnected() to return false, so I assert it. If, unexpectedly, I get a valid connection to Redis, this test would fail.
4. The vanilla test on a shared Redis connection would try to create a default connection to Redis. If isConnected() does not return true, I should assume the test has failed.
5. A simple test to check if I can actually copy a shared Redis connection, and if the copy is still connected to Redis.

If you run those tests when a Redis server is not running on your localhost (and accepting connections on its default port), you should expect a number of failures. Actually, it would (wrongly) succeed only the tests expecting a failure, as the shown TestConnectShared-BadPort. Otherwise I would expect an all green lights scenario.

Go to the full post

Connecting to multiple Redis servers

In the previous post, I have showed how I designed a simple C++ wrapper class that uses a standard C++11 unique_ptr to help working with the hiredis context in such a scenario. My solution has a few limitation, first of them, it doesn't allow to connect to more than a Redis server. Often this is "as designed", still sometimes it is just a nuisance. In any case it is not difficult to redesign the code to allow connections to many Redis servers.

I have written a class named SharedRedis that wraps the hiredis functionality, storing the Redis connection in a C++11 standard shared_ptr smart pointer. You could find the full include file on github.

typedef std::shared_ptr<redisContext> SharedContext; // 1

class SharedRedis
{
    enum { DEFAULT_PORT = 6379 }; // 2
public:
    SharedRedis(const std::string& server, int port = DEFAULT_PORT); // 3
    SharedRedis(int port = DEFAULT_PORT) : SharedRedis("localhost", port) {}

    // ...
private:
    // ...
    SharedContext spContext_;
};

1. To keep the code more readable, I typedef'ed the shared pointer to the Redis context.
2. In this implementation, the user should specify host and port for the Redis server, by default the standard Redis port is used.
3. The only substantial difference to the UniqueRedis implementation (beside the usage of a different smart pointer) is that the object is freely built by the user. No static initializer, but just normal ctors are called to create a new object.

There is not much to say about the implementation, that is very close to what we have seen for the UniqueRedis version. You could see the full source code on github. Maybe it could be worthy to spend a few words on the shared smart pointer construction/destruction.

SharedRedis::SharedRedis(const std::string& server, int port)
{
    // ...
    spContext_ = SharedContext(context, std::bind(&SharedRedis::free, this)); // 1
}

void SharedRedis::free() // 2
{
    redisFree(spContext_.get());
}

1. In the class constructor, the context smart pointer is initialized passing the raw context pointer (we have ensured before that it is a valid value) and the function that has be called on its destruction. Here I use a method of the same class, I could have passed the native radisFree() function, but I wanted to add some stuff to its implementation (actually, just some logging, but I guess it is interesting to show the idea). That's way I had to bind the SharedRedis::free() function to the this pointer, so that the SharedContext destructor could be able to call the right function on the right object.
2. Here is the function that we want to be called on the SharedContext destruction.

There is still something missing. Probably, if we have many Redis connection we want to play with, we should think of storing them in a collection (maybe a map, using as key the host/port), so to have a centralized place to manage them consistently. But I guess this could be seen in another post.

Go to the full post

A unique Redis connection

I need to connect to Redis from a C++ application, and I plan to use hiredis, the Redis official C client, to do it. I want to use just one Redis connection, so I designed my C++ wrapper as a singleton. I would connect once, as I get the first request to Redis, and I would disconnect at the end of the application run.

The environment setup is done in a previous post, including the Makefile description, that you could download from github.

The access to Redis is ruled through a class, UniqueRedis, that has a minimal public interface. There is a static method to get the unique connection instance, a utility method to check if currently the connection is available, and a getter/setter couple. The full source code for the header file is on github:

typedef std::unique_ptr<redisContext, std::function<void(redisContext*)>> UniqueContext; // 1

class UniqueRedis
{
public:
    static UniqueRedis& instance() // 2
    {
        static UniqueRedis redis; // 3
        return redis;
    }

    bool isConnected() { return spContext_ ? true : false; } // 4

    void set(const std::string& key, const std::string& value); // 5
    std::string get(const std::string& key);
private:
    UniqueRedis(); // 6
    void free(); // 7

    UniqueRedis(const UniqueRedis&) = delete; // 8
    const UniqueRedis& operator=(const UniqueRedis&) = delete;

    UniqueContext spContext_; // 9
};

1. I don't want to manage directly the Redis context, I delegate instead a C++11 smart pointer to do the dirty job for me instead. I have chosen unique_ptr because I don't want it to be copied around, and I am giong to use it in the flavor that let the user passing a deleter to it, so that the smart pointer could also take care of calling that cleanup function when needed.
2. The user of this Redis wrapper, should call this static method to gain access to its unique object.
3. If you are using a compiler supporting the C++11 standard, as GNU GCC, initializing a local static variable is implicitely thread-safe.
4. This method returns true if the private smart pointer has been initialized, meaning that a connection to Redis has been already estabilished.
5. Setter and getter. The code is shown below.
6. A UniqueRedis object could be created only through the static initializer defined above.
7. Utility function to cleanup the Redis connection.
8. Copy ctor and assignment operator are explicitely deleted from the class interface.
9. The standard unique_ptr for the Redis context.

The source code for the cpp file is on github, too. Here are some stripped down and commented parts of it:

const std::string REDIS_HOST = "localhost"; // 1
const int REDIS_PORT = 6379;

UniqueRedis::UniqueRedis()
{
    redisContext* context = redisConnect(REDIS_HOST.c_str(), REDIS_PORT);

    if(context->err) // 2
    {
        redisFree(context);
        return;
    }

    spContext_ = UniqueContext(context, std::bind(&UniqueRedis::free, this)); // 3
}

void UniqueRedis::set(const std::string& key, const std::string& value) // 4
{
    void* reply = redisCommand(spContext_.get(), "SET %b %b", key.c_str(), key.length(), value.c_str(), value.length());
    if(reply)
    {
        freeReplyObject(reply);
        return;
    }
}

std::string UniqueRedis::get(const std::string& key)
{
    redisReply* reply = static_cast<redisReply*>(redisCommand(spContext_.get(), "GET %b", key.c_str(), key.length()));
    if(!reply)
        return "";

    std::string result = reply->str ? reply->str : "";
    freeReplyObject(reply);
    return result;
}

1. It would be a smarter idea to have Redis host and port in a configuration file, and fetch the actual values from there. But for the moment having them defined as constants will do.
2. If the hiredis function redisConnect() can't create a good connection to Redis using the passed host and port, I simply cleanup the context and return. You could decide to implement a more aggressive behavior (typically, throwing an exception).
3. We store the valid Redis context in the class private smart pointer. We pass as deleter the address to the member function that would free the context (not shown here, it boils down to call redisFree() for the raw Redis context pointer).
4. The call to redisCommand() is wrapped by set() and get(). As you can see, they work in a very similar way. Notice that I use the binary flag (%b) so that I could pass whatever comes from the user without troubles.

Go to the full post