Splitting a string in plain C++

To split a string I would normally use the Boost tokenizer function. Sometimes I can't. For instance when I am having fun in solving some online programming problem, where no extra library could be used. In this case I fall back to this homemade split function.

boost::tokenizer() is smarter, however this bare version is usually enough for what I need:

std::vector<std::string> split(const std::string& input, char sep) // 1
{
    std::vector<std::string> tokens;
    std::size_t beg = 0, end = 0; // 2
    while ((end = input.find(sep, beg)) != std::string::npos) // 3
    {
        if(beg < end) // 4
            tokens.push_back(input.substr(beg, end - beg));
        beg = end + 1; // 5
    }
    if(beg < input.size()) // 6
        tokens.push_back(input.substr(beg));

    return tokens;
}

1. It accepts in input a constant reference to the string we want to split and the unique character expected as separator. As output we get the found tokens in a vector of strings.
2. I am going to loop on the input string, putting in beg and end the delimiter positions for each token.
3. Find the next position for the separator, until one of them is available at all.
4. If the token is not empty, extract it from input and push it in the tokens vector.
5. The next token would start after the current separator position.
6. Push the last token, not considering a possible empty one at the end of the input string.

As example, see how I have used this split() function to solve the Swap Numbers codeeval problem, that asks to swap the first and last character in each word in a blank separated string:

std::string solution(const std::string& input)
{
    std::vector<std::string> words = split(input, ' '); // 1
    for(std::string& word : words) // 2
        std::swap(word.front(), word.back());

// ...

1. Using the above defined split() function on the input string for the blank separator.
2. Each word in the vector has its first and last character swapped.

Go to the full post

CodeEval magic numbers

We have to detect all the numbers in a given interval that are "magic".

You could find the full description of the problem, and input your solution, on CodeEval.
The most interesting part is the description of the numbers we consider as magic:

* No digits repeat.
* Beginning with the leftmost digit, take the value of the digit and move that number of digits to the right. Repeat the process again using the value of the current digit to move right again. Wrap back to the leftmost digit as necessary. A magic number will visit every digit exactly once and end at the leftmost digit.

6231 is magic because there is no duplicate digit and:
* in position 0 there is a 6, move to position 2 -> (0 + 6) % 4 = 2
* in position 2 there is a 3, move to position 1 -> (2 + 3) % 4 = 1
* in position 1 there is a 2, move to position 3 -> (1 + 2) % 4 = 3
* in position 3 there is a 1, move to position 0 -> (3 + 1) % 4 = 0

Stripping down all the less interesting code, here is how implemented this algorithm in C++.

Firstly ensure there is no duplicated digit in the number:

for(auto it = number.begin(); it != number.end(); ++it)
{
  if(std::find(it + 1, number.end(), *it) != number.end())
    return false;
}

Then loop on the digits until we land on a digit that we have already visited:

std::vector visited(number.size(), false);
int pos = 0;
while(!visited[pos])
{
  visited[pos].flip();
  int cur = number[pos] - '0';
  pos = (pos + cur) % number.size();
}

Finally return success if we ended at the beginning of the string and all the digits have been visited:

return pos == 0 && std::find(visited.begin(), visited.end(), false) == visited.end();

Go to the full post

CodeEval knight moves

Given the position of a knight on the chessboard, return all its possible moves. In alphabetical order.

You could solve this problem as a CodeEval easy challenge.

It came natural to me to solve it in a functional way, still writing C++11 code.

My solution function would put the result in a string using a local lambda function:

std::string result;

auto push_back = [&result] (char x, char y)
{
  result.push_back(x);
  result.push_back(y);
  result.push_back(' ');
};

Nothing of much interest here. My push_back() lambda captures the result string, and push back to it its parameters, adding a blank at the end as separator for the possible next element.

More interesting this other lambda. It captures the string passed as input parameter, that would contain the current knight position in a format like "g2", and the above defined push_back lambda. As parameter it gets the column where I want to move the knight and how many squares I could move up or down:

auto add = [&input, &push_back](char x, int step)
{
  if (input[1] > '0' + step)
    push_back(x, input[1] - step);
  if (input[1] < '9' - step)
    push_back(x, input[1] + step);
};

If the knight does not fall off the chessboard, I push back the resulting positions using the push_back lambda. Now I just have to call add() for each meaningful column. I can do that in this way:

char x = input[0];
if (x > 'b')
  add(x - 2, 1);
if (x > 'a')
  add(x - 1, 2);
if (x < 'h')
  add(x + 1, 2);
if (x < 'g')
  add(x + 2, 1);

Just for readability, I introduced the x variable that should contain the name of the column where the knight is placed. If it is to the right of the 'b' column, I could move two steps to the left, and then call the add() lambda to verify if it could be moved one square more up or down. And so on. Full C++ code is available on github. As well as a few test cases.

Go to the full post

CodeEval string permutations

Given in input a string that could contains letters and numbers, we should output all its permutations comma separated and alphabetically ordered according to the usual conventions.

This is a CodeEval sponsored challenge, so I'll just write here a few hints and not the full solution.

There is a very useful C++ STL function that does all the job for us, namely std::next_permutation(). It assumes the collection it works on has been in the initial state, and it modifies it to the next permutation, until there is anything to permutate. When there is nothing more to do, it returns false.

So we would std::sort() our collection - that should be modifiable, and then std::next_permutation() it in a loop, storing the permutations in a temporary buffer, or maybe directly outputting it to standard output.

std::sort(s.begin(), s.end());
// ...
do {
  // ...
} while (std::next_permutation(s.begin(), s.end()));

The only minor nuisance left now is the comma. We should add it to each permutation but the last one. There are a number of ways to address this point, for instance you could see it in a different perspective. Each permutation has a comma before it, but the first one. Or maybe you could blissfully ignore the point when you build the solution, and simply remove the last character before returning your solution. If you are following this strategy, the C++11 pop_back() std::string method could be useful.

If pop_back() is not available yet on your compiler, here is an alternative solution:

s.erase(s.size() - 1, 1); // s.pop_back();

In any case you should remember to check the size of your input string. If it is empty or consisting of just one character there is nothing to do. Otherwise you are safe in assuming there is something you could erase in the resulting output.

Go to the full post