Merge sort

Typical example of a divide and conquer approach applied to the sorting problem. It's O(n lg n) time complexity makes it interesting for large enough data collections.

This algorithm's idea is that we could split recursively the problem until we have a tiny subproblem so simple that is trivial to solve it. Than we just have to merge the partial results to get the actual solution.

Here is the "divide" part, implemented in C++:

typedef std::vector<int> Data;

void mergeSort(Data& data, int left, int right) // 1
{
    if(left < right) // 2
    {
        int center = (left + right) / 2;
        mergeSort(data, left, center); // 3
        mergeSort(data, center + 1, right);
        merge(data, left, center, right); // 4
    }
}

1. The function expects in input the collection to sort and the first/last indexes to consider.
2. If there is just one element to sort, there is nothing to do.
3. Split the problem it two parts and recursively call the divide function on them.
4. Merge the partial solutions.

As one would expect, large part of the job is done by the merging function:

typedef std::queue<int> Queue;

void merge(Data& data, int left, int center, int right)
{
    Queue low; // 1
    Queue high;

    for(int i = left; i <= center; ++i) // 2
        low.push(data[i]);
    for(int i = center + 1; i <= right; ++i)
        high.push(data[i]);

    int i = left;
    while(!low.empty() && !high.empty()) // 3
    {
        if(low.front() <= high.front())
        {
            data[i++] = low.front();
            low.pop();
        }
        else
        {
            data[i++] = high.front();
            high.pop();
        }
    }

    while(!low.empty()) // 4
    {
        data[i++] = low.front();
        low.pop();
    }
    while(!high.empty())
    {
        data[i++] = high.front();
        high.pop();
    }
}

1. A couple of queues are used to temporary store the data while processing them.
2. Fill the queues with the data coming from the input collection.
3. Compare the data on the two queues, rearranging them in the original container.
4. Ensure all the possible elements left in the temporary queues are copied back to the input data.

Full code is on github. As bonus you will also find there a simple xUnit test for GoogleTest.

Go to the full post

Insertion sort

It's a simple sorting algorithm that, even if asymptotically expensive, O(N**2), it results to be cheap for small data set.

Its idea is comparing each element starting from the second up to the last one with its predecessor. While we found smaller items on its left, move those ones to the right, to make room to it.

Here is my C++ implementation:

void insertionSort(std::vector<int>& data)
{
    for(unsigned i = 1; i < data.size(); ++i) // 1
    {
        int value = data[i]; // 2
        int j = i - 1; // 3
        while(j >= 0 && data[j] > value)
        {
            data[j+1] = data[j]; // 4
            --j;
        }
        data[j+1] = value; // 5
    }
}

1. Loop on all the elements after the first one.
2. Cache the current element.
3. Loop backward on the elements on the left of the current one until we found something smaller, or there is nothing more to check.
4. Make room to the current element.
5. Place the element in order.

Full code is on github. As bonus you will find there also a basic GoogleTest test.

Go to the full post

Longest Common Subsequence by Dynamic Programming

Given two strings, find their longest common subsequence.

This is a well known programming problem (to read more about it, you could go to this wikipedia page) that is commonly used as introduction to the dynamic programming solving method.

Its simpler version requires to return just the size of the subsequence. Determining the actual result is a bit more complicated.

I have written a few test cases to clarify to myself what the problem is about, and to get driven in the software development. Here are a couple of them (written for the C++ GoogleTest framework):

int lcsSize(const std::string& first, const std::string& second);
std::string lcsStr(const std::string& first, const std::string& second);

TEST(Lcs, CaseSize)
{
  EXPECT_EQ(2, lcsSize("AGCAT", "GAC"));
  EXPECT_EQ(3, lcsSize("ABCDGH", "AEDFHR"));
  EXPECT_EQ(4, lcsSize("AGGTAB", "GXTXAYB"));
}

TEST(Lcs, CaseStr)
{
  EXPECT_EQ("GA", lcsStr("AGCAT", "GAC"));
  EXPECT_EQ("ADH", lcsStr("ABCDGH", "AEDFHR"));
  EXPECT_EQ("GTAB", lcsStr("AGGTAB", "GXTXAYB"));
}

As you would have already get, lcsSize() is the simpler one, and lcsStr() the more complete. Both functions require to generate a matrix where all the subproblem results are stored. If we want to get just the result size, we would just peak the result of the last one (the most right-below element). Otherwise we'll need to navigate the matrix to build the string up:

std::vector<std::vector<int>> lcs(const std::string& lhs, const std::string& rhs)
{
  const unsigned rows = lhs.size() + 1; // 1
  const unsigned cols = rhs.size() + 1;

  std::vector<std::vector<int>> buffer(rows); // 2
  for(unsigned i = 0; i < rows; ++i) // 3
    buffer[i].resize(cols);

  for(unsigned i = 1; i < rows; ++i) // 4
    for(unsigned j = 1; j < cols; ++j)
      buffer[i][j] = (lhs[i-1] == rhs[j-1]) ? // 5
          buffer[i-1][j-1] + 1 : std::max(buffer[i-1][j], buffer[i][j-1]);

  return buffer;
}

1. The matrix is going to have an extra row and column. This is not a strict necessity, but it makes the code more readable.
2. A simple way to implement a matrix is making it a vector of vectors. Notice the double '>' sign, it is legal in C++11 but it would confuse older compilers.
3. The vector of vectors ctor in the line above creates "rows" zero-sized rows. Here I assign them the right size. Remember that each element is initialized with the default value, that is zero.
4. Loop on all the "real" elements to solve the problem using the previous results.
5. To determine the current value, I check if the relative letters in the input string are the same (notice the "-1", it is due because of the fake top/left elements in the matrix). If it is the case, I have found another matching character, so I increase the value. Otherwise the lcs is not increasing, check the current biggest value and use it.

Now it is trivial to get the common subsequence size, it is the value stored in the last visited cell in the matrix:

int lcsSize(const std::string& lhs, const std::string& rhs)
{
  std::vector<std::vector<int>> buffer = lcs(lhs, rhs);
  return buffer[lhs.size()][rhs.size()];
}

Returning the actual subsequence requires some more code:

std::string lcsStr(const std::string& lhs, const std::string& rhs)
{
  std::vector<std::vector<int>> buffer = lcs(lhs, rhs);

  std::pair<unsigned, unsigned> cur { lhs.size(), rhs.size() }; // 1
  std::vector<char> result; // 2
  while(unsigned size = buffer[cur.first][cur.second] > 0) // 3
  {
    if(buffer[cur.first-1][cur.second] < buffer[cur.first][cur.second] &&
        buffer[cur.first][cur.second-1] < buffer[cur.first][cur.second])
    { // 4
      result.push_back(rhs[cur.second-1]);
      --cur.first;
      --cur.second;
      --size;
    }
    else if(buffer[cur.first][cur.second-1] == buffer[cur.first][cur.second]) // 5
      --cur.second;
    else
      --cur.first;
  }

  return std::string(result.rbegin(), result.rend()); // 6
}

1. The starting point is the matrix right bottom.
2. Each time I find a subsequence character, I'll push it here.
3. We know the subsequence length, we can use it to stop looping when we find all its elements.
4. This cell is marked as being relative to a matching character. Save its value and move up and to the left.
5. Otherwise, move in the matrix (to the left or up), until we find another border character.
6. Now is just a matter of building a string that revert the sequence stored in the resulting vector.

Go to the full post

Double square numbers

A number that is the sum of two perfect squares is called a double square. Notice that any perfect square number, since it could be expressed as the sum of its square root and zero squared, is a double square:

16 = 4**2 + 0**2

Beside the trivial case showed before, we could think of cases like 50, were more than one couple of integer could generate it:

50 = 1**2 + 7**2 = 5**2 + 5**2

We want to write a function that could check if any positive integer up to a couple of billion (so that we could store it in a signed 32 bit int) is such a number.

I have found this problem on CodeEval, under the name Double Squares however, they credit the Facebook Hacker Cup 2011 as their source. They suggest of not even thinking about a brute force approach, and trying to be smarter than that.

When working on this post, I found nicer to change slightly the requisites, asking the function to return the collection of couples that generates the number as double square. If the passed number is not such, the function would return an empty collection.

Here is a few test cases (GoogleTest for C++) that show what I want from this function:

typedef std::vector< std::pair<int, int> > Generators; // 1

Generators doubleSquares(int value); // 2

TEST(DoubleSquares, Sixteen) // 3
{
    Generators output = doubleSquares(16);

    ASSERT_EQ(1, output.size());
    EXPECT_EQ(0, output[0].first);
    EXPECT_EQ(4, output[0].second);
}

TEST(DoubleSquares, Fifty) // 4
{
    Generators output = doubleSquares(50);

    ASSERT_EQ(2, output.size());
    EXPECT_EQ(1, output[0].first);
    EXPECT_EQ(7, output[0].second);
    EXPECT_EQ(5, output[1].first);
    EXPECT_EQ(5, output[1].second);
}

TEST(DoubleSquares, BigOne) // 5
{
    Generators output = doubleSquares(5882353);

    ASSERT_EQ(1, output.size());
    EXPECT_EQ(588, output[0].first);
    EXPECT_EQ(2353, output[0].second);
}

1. As container for the generators I am going to use a vector of pairs.
2. My function prototype.
3. Passing 16 in, I expect as output a single pair, (0, 4).
4. Both (1, 7) and (5, 5) generates 50.
5. A (relative) big number, 5882353, generated by (588, 2353).

Here is how I have implemented the function:

Generators doubleSquares(int value)
{
    Generators result;
    for (int i = 0; i <= std::sqrt(value / 2); i++) // 1
    {
        double j = std::sqrt(value - std::pow(i, 2)); // 2
        if (std::floor(j) == j) // 3
            result.push_back( { i, static_cast<int>(j) } ); // 4
    }
    return result;
}

1. I am checking if value has a couple of generators. Each of them should be a non-negative integer, the biggest one can't be bigger than the square root of the half of value. To clarify this point think to a real case, 64 for instance. It is easy to see that 9 can't be among its generators.
2. Let's assume i is a generator for value, the other generator should concur with all the missing slice to reach the result. So I extract the square root from the difference between value and the square of i.
3. I am still not sure I can accept j as second generator for value, I should check it is an integer. This is probably the fastest way to do it. The standard math function floor() returns the nearest integer not greater than its input. We state that its returned value is exactly equals to the j original value.
4. I am using this very handy C++11 way to build a STL pair on the fly. If your compiler does not support it, I am sorry you have to fallback to the less immediate make_pair() function template. Notice also that I should say to the compiler that I am aware I am casting a double to an int. I am sure of what I am doing, thanks to the check on the previous line.

Go to the full post

Dominator by golden leader

I want to check if in a collection of integers there is a value that occurs more than half the times. I have already given a solution to this problem in the previous post, but I need something smarter, linear in time and constant in space complexity.

To achieve this result I am about to implement an algorithm based on the discussion that you can read in a paper available on Codility. Look at the end of that document, for a Python function named goldenLeader.

In a few words, the idea is that if a dominator exists, we could discard couples of different elements, and in the end, we should ends up with having spared at least one dominator element. If no dominator exists, we'll find out we have throw away all the elements looking for it.

However, our function should not return just the dominant value, but an index of the original vector that refers to an element with such a value. So we need to twist a bit that algorithm.

typedef std::pair<unsigned, int> ValInd; // 1

int solution(const std::vector<int>& input)
{
    int count = 0; // 2
    ValInd candidate; // 3
    for (unsigned i = 0; i < input.size(); ++i)
    {
        if (count == 0) // 4
        {
            count = 1;
            candidate.first = input[i];
            candidate.second = i;
        }
        else // 5
        {
            count += (candidate.first == input[i]) ? 1 : -1;
        }
    }

    if (count == 0) // 6
        return -1;

    if (std::count(input.begin(), input.end(), candidate.first) > (int) input.size() / 2)
        return candidate.second;

    return -1;
}

1. I need to remember the current value and the index where I have found it.
2. I am going to count how many elements, supposedly being dominators, I have found that are not yet matched with non-dominator. I could have pushed them on a stack, but it is obviously cheaper doing in this way.
3. Here I am going to store the current candidate.
4. No previous candidate survived the looping, the current element is chosen.
5. I have a candidate, I compare it against the current element. If they have the same value, I increase the counter, otherwise I decrease it.
6. If there is no pending candidate, I am sure there is no dominant value. Otherwise I count how many elements with the candidate value are in the input collection. If they are enough, bingo.

Go to the full post

Dominator

We have a collection of integers (whichever 32 bit signed int is possible, and up to one million of them), we want to know if there is a dominant value in it. Meaning, a value that occurs more than half the times. If so, the index of one of such item (anyone would do) should be returned. Otherwise a -1 would mean "no dominant value".

To make things a bit more spicy, linear time and constant space complexity is required.

I found this problem in the Codility train page, section Leader, under the nickname Dominator. There you would find more details and the free words description of the test case I have here translated for C++ and GoogleTest:

int solution(const std::vector<int>& input);

TEST(Domi, Given)
{
    int h[] = { 3, 4, 3, 2, 3, -1, 3, 3 };
    std::vector<int> input(h, h + 8);

    ASSERT_EQ(3, input[solution(input)]);
}

More than half the elements in the collection have value 3, so I expect as output the zero-based index of an element whose value is 3.

Not considering the space complexity requirement, is not difficult to find an (almost) suitable solution.

What I would do, is creating a map where the values of the input vector are associated to a counter that keep track of their sequence. Or better, since we want to know also the index of one of such elements, besides the counter I am going to store also the first index I get.

Then it would be just a matter of scanning the map.

Here is a possible C++98 implementation:

typedef std::pair<unsigned, unsigned> CountInd; // 1
typedef std::map<unsigned, CountInd> Counter; // 2

int solution(const std::vector<int>& input)
{
    Counter counter;
    for (unsigned i = 0; i < input.size(); ++i)
    {
        Counter::iterator pos = counter.find(input[i]);
        if (pos != counter.end()) // 3
            ++pos->second.first;
        else
            counter[input[i]] = std::pair<unsigned, unsigned>(1, i);
    }

    for (Counter::const_iterator it = counter.begin(); it != counter.end(); ++it)
    {
        if (it->second.first > input.size() / 2)
        {
            return it->second.second;
        }
    }

    return -1;
}

1. The value in the map would be a pair of frequency and index in the original vector.
2. I don't care about keeping the elements in the map ordered. If I were allowed to use C++11, the STL unordered_map would have been a much better choice. I am paying in term of time complexity something that I am not using. On the other hand, defining a custom hash map for this problem would be kind of an overkilling.
3. If I have already added an element in the map for the current value, I have just to increase its counter. Otherwise I add a new element where the key is the current input value, and the value is a pair having as first the current counter for this element (one), and as second the index to the current element in the input vector.

This solution scores full marks on Codility, but we know that is not the right answer. Time complexity is so close to be linear that their tested didn't detect the logarithmic multiplicator caused by the STL map. The real issue is the space complexity (even though not detected, too) that is linear instead of constant.

To achieve this result, we could apply an astute algorithm that you could see described in this linked document from Codility, where is given in a Python implementation in a function called goldenLeader.

I am going to use this hint to refactor my solution.

Go to the full post

Fish eat fish - linear solution

A bunch of cannibal fishes move up and downstream in a narrow river following the rules that I explained in the previous post. There I also showed a few test cases (C++ and GoogleTest) and a suboptimal first solution. Here I present a better algorithm that achieves an asymptotic linear time complexity even in the worst case.

The previously shown solution has the issue of repeating on and on checks on the same couple of fishes. We can avoid this delaying the comparison until it becomes a strict necessity.

The trick that I use here is avoid doing anything with any fish going downstream but storing them in a stack. The real job is done for each fish going upstream. If there is no one coming from the other direction, it survives for sure, otherwise it should decide its fate with a comparison against all the fishes previously stored in the stack, starting from the one closest to it (that's why a stack is a good choice as container).

Here is how I implemented this algorithm:

int solution(std::vector<int>& sizes, std::vector<int>& directions)
{
    int count = 0; // 1
    std::stack<int> goingDown; // 2
    for (unsigned i = 0; i < sizes.size(); ++i)
    {
        if (directions[i] == 1) // 3
        {
            goingDown.push(sizes[i]);
            continue;
        }

        if (goingDown.empty()) // 4
        {
            ++count;
            continue;
        }

        while (!goingDown.empty()) // 5
        {
            if (sizes[i] > goingDown.top()) // 6
                goingDown.pop();
            else
                break;
        }
        if (goingDown.empty()) // 7
            ++count;
    }
    return count + goingDown.size(); // 8
}

1. I don't need anymore to store the state of each fish, I could just keep track of the number of fishes going upstream that survived.
2. Here I push each fish that is going downstream.
3. The current fish is going downstream, I just have to push it in the stack and go to the next iteration.
4. The current fish is going upstream. If there is no previous fish moving in the other direction, he made it. I increase the counter and go to check the next one.
5. Otherwise, the current fish has to prove to be bigger than any fish in the stack to survive.
6. If the current fish is bigger that the current top in the stack, pop it (that is, eat it). Otherwise, it is the one to be eaten, and I should stop looping on the stack.
7. If the stack of downwards-going fishes is empty, this means that the current fish has eaten them all up (or it was so lucky to find no traffic). So I can increase the counter.
8. In "count" I have the number of all the upwards-going fishes that made it. I just have to add to it the numbers of the downwards-going fishes to get their current total number.

The C++ source code for both solutions and relative test cases is on github.

Go to the full post

Fish eat fish

We have a bunch of fishes (there could be up to 100,000) in a very narrow river, each of them with a different weight (represented by a non negative integer up to one billion). Any single fish move upstream or downstream (0 means up, 1 down). If two fishes meet (one moving up, the other moving down) the smaller one is eaten by the bigger. How many fishes are going to survive?

You can find this problem in the Codility train page, under the Stacks and Queues section, nickname Fish.

To better think about a solution, I have taken the one proposed in the problem description and converted it to a GoogleTest for C++, then adding the ones that looked interesting to me. Here is a selection of them:

int solution(std::vector<int>& sizes, std::vector<int>& directions);

TEST(Fish, Given) // 1
{
    int a[] = { 4, 3, 2, 1, 5 };
    std::vector<int> sizes(a, a + 5);

    int b[] = { 0, 1, 0, 0, 0 };
    std::vector<int> directions(b, b + 5);

    ASSERT_EQ(2, solution(sizes, directions));
}

TEST(Fish, SameDirection) // 2
{
    int a[] = { 4, 3, 2, 1, 5 };
    std::vector<int> sizes(a, a + 5);

    std::vector<int> directions(5);

    ASSERT_EQ(5, solution(sizes, directions));
}

TEST(Fish, Mixed) // 3
{
    int a[] = { 4, 3, 2, 1, 5 };
    std::vector<int> sizes(a, a + 5);
    int b[] = { 0, 1, 0, 1, 0 };
    std::vector<int> directions(b, b + 5);

    ASSERT_EQ(2, solution(sizes, directions));
}

TEST(Fish, NoMeeting) // 4
{
    int a[] = { 4, 3, 2, 1, 5 };
    std::vector<int> sizes(a, a + 5);
    int b[] = { 0, 0, 0, 1, 1 };
    std::vector<int> directions(b, b + 5);

    ASSERT_EQ(5, solution(sizes, directions));
}

TEST(Fish, Pilot) // 5
{
    int a[] = { 1, 5, 3, 4, 2 };
    std::vector<int> sizes(a, a + 5);
    int b[] = { 1, 1, 0, 0, 0 };
    std::vector<int> directions(b, b + 5);

    ASSERT_EQ(2, solution(sizes, directions));
}

1. All the fish is going upstream but the second one, that weights 3. It is going to eat the third and forth, but it is going to be eaten by the fifth. In the end just two fishes are going to survive, the first and the last one.
2. The fish is compactly moving upstream, all of them should survive.
3. Mixed situation, only two fishes are going to survive.
4. The school is parted in two groups that are not meant to cross.
5. This is the one I found most interesting. The first two fishes are moving downwards, against the other three ones. The first one is so thin that would usually have no chance to survive, but it has just after it a big brother that is going to shield it to any attack. So, against all odds, it survives too.

Then I have written my first solution, based on the idea of checking each element against any other fish it is going to meet, keep track of their status in a vector of boolean and then sum up all the surviving fishes.

int solution(std::vector<int>& sizes, std::vector<int>& directions)
{
    std::vector<bool> alive(sizes.size(), true); // 1

    for (unsigned i = 0; i < sizes.size(); ++i) // 2
    {
        if (directions[i] == 0) // 3
        {
            for (int j = i - 1; j >= 0; --j)
            {
                if (directions[j] == 1)
                    alive[sizes[i] < sizes[j] ? i : j] = false;
                if (sizes[i] < sizes[j])
                    break;
            }
        }
        else // 4
        {
            for (unsigned j = i + 1; j < sizes.size(); ++j)
            {
                if (directions[j] == 0)
                    alive[sizes[i] < sizes[j] ? i : j] = false;
                if (sizes[i] < sizes[j])
                    break;
            }
        }
    }

    return std::accumulate(alive.begin(), alive.end(), 0); // 5
}

1. Initially, are the fishes are alive.
2. I am checking any fish against the ones that are upwards or downwards, accordingly to its moving direction.
3. My current fish is moving upstream. Let's compare it against each fish on its left, starting from the closest one. I break the loop in case it gets eaten by a bigger fish.
4. Same as above, but the current fish has to fight against all the other guys downstream.
5. Finally it is just a matter of counting how many of them are still alive.

Normally this solution works fine, however in the worst case scenario the internal loop involves a number of fish in the order of the collection size, leading to an O(N**2) time complexity that makes this algorithm unacceptably slow.

Think for instance to this innocuous-looking test case:

TEST(Fish, Big)
{
    std::vector<int> sizes(100000);
    for(unsigned i = 0; i < sizes.size(); ++i)
        sizes[i] = i + 1;
    std::vector<int> directions(100000);

    ASSERT_EQ(100000, solution(sizes, directions));
}

One hundred thousand fishes, all of them going in the same direction. A human being could give the answer in the blink of an eye. The above solution, however, painfully check all the right elements to any fish in the school.

Can we do better than this? Yes. As you would see in the next post, it is just a matter of adding a bit of intelligence to the algorithm to get, even in the worst cases, a linear(ish) time complexity.

Go to the full post

Narcissistic numbers

You could find a thorough description of narcissistic number, also known as Armstrong number, perfect digital invariant, plus perfect number, on Wolfram Mathworld. In a few words, a narcissistic number is an n-digit numbers that equals the sum of all its digits at the nth power.

We want to write a function that checks if a given number respects this definition.

It is easy to see as any positive one-digit number is narcissistic, and the Wolfram page I linked above provides a list of other narcissistic numbers. I used them to write these test cases (in C++ for GoogleTest):

bool isNarcissistic(const std::string& input);

TEST(Narcissus, Simple)
{
  ASSERT_TRUE(isNarcissistic("2"));
  ASSERT_FALSE(isNarcissistic("42"));
}

TEST(Narcissus, Three)
{
  ASSERT_TRUE(isNarcissistic("153"));
  ASSERT_TRUE(isNarcissistic("370"));
  ASSERT_TRUE(isNarcissistic("371"));
  ASSERT_TRUE(isNarcissistic("407"));
  ASSERT_FALSE(isNarcissistic("497"));
}

TEST(Narcissus, Eight)
{
  ASSERT_TRUE(isNarcissistic("24678050"));
  ASSERT_TRUE(isNarcissistic("24678051"));
  ASSERT_TRUE(isNarcissistic("88593477"));
  ASSERT_FALSE(isNarcissistic("88583475"));
}

Here is a possible implementation for such function:

bool isNarcissistic(const std::string& input)
{
  assert(!input.empty()); // 1
  if(input.size() == 1) // 2
    return input[0] != '0';

  int powered = 0; // 3
  for(unsigned i = 0; i < input.size(); ++i)
    powered += std::pow((input[i] - '0'), input.size());

  return powered == std::atoi(input.c_str()); // 4
}

1. This should never happen. It should be user code responsibility ensure that the passed input parameter is not empty. Production code should also ensure that the input strings contains only decimal digits.
2. All one-digit numbers are accepted, with the noteworthy exception of zero.
3. Each digit in the number are elevated to the expected power (third, if there are three digits in the number) and the result is summed up.
4. Compare the original value with the calculated one, and return true if they are the same.

Go to the full post

Self-descriptive numbers

Write function that check if its input represents a self-descriptive base-10 integer.

A number is said self-descriptive if its digit at the i-th position is the counter for the i-digit in the number itself.
21200 is self-descriptive, since it has 2 zeros, 1 ones, 2 twos, 0 threes, and 0 fours.

Here is a possible C++ implementation:

bool isSelfDescr(const std::string& input)
{
  if(input.empty() || input.size() > 10) // 1
    return false;

  for(unsigned i = 0; i < input.size(); ++i) // 2
    if(std::count(input.begin(), input.end(), '0' + i) != input[i] - '0')
      return false;

  return true;
}

1. I am expecting a 10-based number, that means it can't have more than 10 digits - and it shouldn't be empty.
2. For each digit in the number, I count how many of them are in the string, using the STL algorithm count(), and I compare the result against the number in that position.

Go to the full post

Happy numbers

In the Doctor Who episode "42" (the seventh of the third modern series), the tenth Doctor explains that a (natural positive) number that reduces to one when you sum up the square of its digits and continue iterating it until it yields one is said to be happy. If this description doesn't look so descriptive to you, there is a page about happy numbers on wikipedia that looks interesting.

We can check if a number is happy with a C++ function like this one:

bool isHappy(unsigned value)
{
  std::set<unsigned> numbers; // 1
  numbers.insert(1); // 2
  while(numbers.find(value) == numbers.end()) // 3
  {
    numbers.insert(value); // 4
    int next = 0;
    while(value > 0)
    {
      int digit = value % 10;
      next += std::pow(digit, 2); // 5
      value /= 10;
    }
    value = next;
  }

  return value == 1; // 6
}

1. A sad number would enter in a hopeless infinite loop. To detect it, we should keep memory of the states it has already passed, so that we can check them.
2. We could stop transforming the input number when we get a value that we have already seen (sad), of when we get 1 (happy).
3. If the current value is not in the buffering set, we iterate once again.
4. Add the current value to the "already seen" set, and calculate the next state.
5. Each digit is squared and added.
6. If value has reached 1, we have a happy number.

Go to the full post

String tolower()

The problem here is converting an entire C++ string to lower (or upper) case.

The raw part of the job is done by the toupper/tolower ctype functions in the standard library. The point is that those functions work on a single character, we should find a way of iterating on the entire string.

We could just loop from the beginning to the end of the string, applying tolower() to each element in the sequence. Something like this:

for(std::string::iterator it = line.begin(); it != line.end(); ++it)
  *it = std::tolower(*it);

This implementation is alright, still we could avoid to explicitly do some work that nothing add as a value to our code, as declaring the iterator and a for-loop block.

We could use instead the STL transform() algorithm, that hides the for-block and its loop variable, asking as input the begin-end iterators for the input sequence, the begin iterator to the output one, and the operation it has to apply to transform it.

Here we are doing an in-place transformation, so input and output are the same.

Nice and plain. There is a tiny nuisance, though. There could be a name-clash on tolower/toupper, since besides the ctype version, there is also a localized version, defined in the locale include. So we can't simply say to the compiler we want to use the standard tolower function, we need to specify which tolower is needed. In our case, the one that expects an int as both input parameter and return value:

std::transform(line.begin(), line.end(), line.begin(), static_cast<int(*)(int)>(std::tolower));

Go to the full post