Another asynchronous wait on a steady timer

This is a new version of an oldish Boost ASIO example of mine about asynchronously waiting on a timer, keeping advantage of C++11 features. If you are looking for something simpler, there's another post on the same matter but more focused on the bare ASIO functionality. Or you could go straight to the original source, the official tutorial on Boost.

Five years later, I found out that this post requires some adjustments. You could follow the link to its March 2018 version.

The main function of this example is spawning a new thread, that runs a function that does something indefinitely. But before creating the new thread, it would set an asynchronous timer, calling a function on its expiration that would cause the runner to terminate.

It makes sense to encapsulate both function in a single class, like this:

class MyJob
{
private:
    MyJob(const MyJob&) = delete; // 1
    const MyJob& operator=(const MyJob& ) = delete;

    std::mutex mx_; // 2
    bool expired_;
public:
    MyJob() : expired_(false) {}

    void log(const char* message) // 3
    {
        std::unique_lock<std::mutex> lock(mx_);
        std::cout << message << std::endl;
    }

    void timeout() // 4
    {
        expired_ = true;
        log("Timeout!");
    }

    void operator()() // 5
    {
        for(int i = 0; !expired_; ++i)
        {
            std::ostringstream os;
            os << '[' << i << ']';

            log(os.str().c_str());
            std::this_thread::sleep_for(std::chrono::seconds(1));
        }
    }
};

1. I don't want an object of this class to be copyable, we'll see later why. So I remove from this class interface copy constructor and assignment operator, using the C++11 equals-delete marker.
2. There are two threads insisting on a shared resource (the standard output console), a mutex is needed to rule its access.
3. The shared resource is used in this function only. A lock on the member mutex takes care of protecting it.
4. When the timer expires, it is going to call this method.
5. This function contains the job that is going to run in another thread. Nothing fancy, actually. Just a forever loop with some logging and sleeping. The timeout is going to change the loop control variable, so that we can have a way out.

This is the user code for the class described above:

boost::asio::io_service io; // 1
boost::asio::steady_timer timer(io, std::chrono::seconds(3)); // 2

MyJob job; // 3
timer.async_wait([&job](const boost::system::error_code&) {
  job.timeout();
}); // 4

std::thread thread(std::ref(job)); // 5
io.run();
thread.join();

1. An ASIO I/O service is created.
2. I create a steady timer (that is just like an old deadline timer, but uses the C++11 chrono functionality) on the I/O service object.
3. An object that describes the job I want to run in another thread is instantiated.
4. When the timer expires, the passed lambda function is executed. It is an asynchronous call, so it returns immediately the control, that passed to the next instruction (5). The lambda would call the timeout() method on the job object, that has been captured by reference. Having defined the MyJob class as non-copyable, forgetting the ampersand, passing the job by value, results in a compiler error. Here I don't care about the error code parameter, that is set by ASIO to say if the timer has expired correctly or with an error. I just stop the job running. In a real-life usage a check would be expected.
5. Before running the I/O service, I create a thread on our job - again passed by reference, as the std::ref() shows. Again, trying to pass it by value would result in compiler errors.

Full C++ code for this example is on Github.

Go to the full post

All Your Base with unordered_map

The first problem in the Code Jam Round 1C 2009, All your base, is about converting a string to the smallest possible natural number.

It sounds a bit crazy, but think to the string "ZY", I could say that Z means 1, Y is 0, and that I am using the binary base, so it could be interpreted as 3. Any other valid conversion would lead to a bigger number, considering that I can't put a zero in the leading position.

As requisites, we have that the input size is in [1, 60], and that the ouput is an integer [1, 10^18], too big to be stored in a 32 bit. This is way I have declared my C++ function in this way:

long long allYourBase(const std::string& input)

Considering that a long long is an integer stored in at least 64 bit.

Then I wrote a few test cases, the first three of them were coming straight from the problem definition:

TEST(AllYourBase, Test1) // 1
{
    EXPECT_EQ(201, allYourBase("11001001"));
}

TEST(AllYourBase, Test2) // 2
{
    EXPECT_EQ(75, allYourBase("cats"));
}

TEST(AllYourBase, Test3) // 3
{
    EXPECT_EQ(11, allYourBase("zig"));
}

TEST(AllYourBase, TestBigDec) // 4
{
    EXPECT_EQ(1000000000023456789, allYourBase("1000000000023456789"));
}

TEST(AllYourBase, TestBigHex) // 5
{
    EXPECT_EQ(1162849439785405935, allYourBase("1023456789abcdef"));
}

TEST(AllYourBase, TestBigBinary) // 6
{
    EXPECT_EQ(1000000000000000000, allYourBase("bbabbbbaaaaababbabbababbaabbbabaabbbabbaabaaaaaaaaaaaaaaaaaa"));
}

1. We can assume the input is a binary representation of the actual number, so the conversion is very easy.
2. Here we are going to use base 4. The smallest number should have a 1 as most significative cipher, 0 as second, 2 as third, 3 as fourth. Leading to 1023 in base 4, that is 75 base 10 (64 + 0 + 8 + 3).
3. In base 3 is 102, converted to 11 in base 10.
4. Here I go a bit over the requirements, the generated number is a few millions (23) bigger than the expected top number.
5. Same as (4), but this is substantially over the expected limit.
6. Binary numbers are perfect to play with this problem, if we don't mind writing long sequences of characters.

The solution should be straightforward. Here is my version:

long long allYourBase(const std::string& input)
{
    if(input.empty() || input.size() > 60) // 1
        return 0;

    std::unordered_map<char, int> symbols; // 2

    int value = 1;
    for(char c : input) // 3
    {
        if(symbols.find(c) == symbols.end()) // 4
        {
            symbols.insert({c,value});

            if(value == 1) // 5
                value = 0;
            else if(value == 0)
                value = 2;
            else
                ++value;
        }
    }

    int base = symbols.size(); // 6
    if(base == 1)
        base = 2;

    long long result = 0;
    long long multiplier = 1;

    for(auto pos = input.rbegin(); pos != input.rend(); ++pos) // 7
    {
        result += symbols[*pos] * multiplier; // 8
        multiplier *= base; // 9
    }

    return result;
}

1. The requisites do not specify what should be do for unexpected input size. In the logic of the problem we could assume it just never happens. Here I decided to return zero (an invalid value), I could have thrown an exception that is a more expressive way of saying "this is unexpected".
2. My first job is determining in which base the number is expressed. I can do that scanning the input line and storing each value in a container. The number of such symbols represents the base (with an exception that we are seeing later on). Besides, I can already determine the value for each symbol. As we see discussing the test cases, we are going from the less significative all the way up, with the exception that the zero is in second position. So I need a pair to keep the relation symbol-value, and I can keep all the pairs in a hash table. Here comes handy the C++11 unordered_map. Using the old plain map is a bit of an overkill, since we don't care about the ordering maintained by a red-black tree.
3. Let's loop on the input string.
4. If I have already seen the current symbol, I have nothing to do. Otherwise I insert it using the value I have precedently set.
5. Assigning a value to each symbol would be a simple job if it wasn't for the glitch about the zero that should be in second position.
6. As said above, the base is assumed to be just the number of symbols in the string, with an exception. We expect at least a binary base to be used, so if we detect just one symbol we don't go for the unary one.
7. Let's calculate the result value looping on the string. It is easier to start from the less significative position (the rightmost one) and moving up to the left. So I am using the reverse iterator.
8. Dereferencing pos, I get the current symbol. I go to the hash table and get its associated value. I multiply it for the current positional value, and I add it to the current result.
9. If we are in base ten, the multiplier is 1 for the rightmost position, 10 for the one on its left, then 100, and so on.

Instead of writing my own converter based on position and multiplier, I could have used the standard pow() function declared in the cmath include file. Writing something like:

for(unsigned i = 0; i < input.size(); ++i)
{
    // ...
    result += value * std::pow((double)base, i);
    // ...
}

Notice that in this case we need to explicitly keep track of the current position in the string. So I would prefer to write the loop using a classic "i" index running on the size.
The weakness of this solution is that pow() is designed to work on floating numbers so we need to cast (explicitly) the base to double - or better, a long double - and then we have an implicit cast back to integer type when adding to result. Beside being unusefully expensive going to float and back to fixed, we risk (more importantly!) to have rounding problems due to the internal representation of a floating point number. Using long double should protect us about this issue, but there is no explicit guarantee.
In my case, Linux 64 bit, GCC 4.8, I had problem with pow() on "simple" double only for the test cases TestBigDec and TestBigHex, that are actually out of scope. Using the pow() version for long double all cases worked fine.
In any case, since floating point behavior is not standardized, you should check how it works on your actual configuration. The hand-made integer-based version has none of these issues, assuming long long represents at least a 64 bit integer.

Go to the full post

File Fix-it with unordered_set

The Code Jam Round 1B 2010 Problem A, File Fix-it, requires a solver who knows how a file system is organized, better if from the UNIX family. We provides the already existing directories (maybe zero), and the one or more directories that we want to create. For some reason you can't specify the useful -p parameter on mkdir, and you need instead to iterate on any new subdirectory you need to create. Our solution should give the number of required mkdir runs.

This is a problem that asks loudly to be solved using a trie (aka prefix tree). Unfortunately there is not such a beast in the STL (I am using C++ as implementing language), and using here a non standard library, or developing a simple version of a trie, could be seen as an overkill.

So I am about to use an hash table instead. Namely, the C++11 unordered_set.

The idea is pretty simple, I store each already existing directory in an hash table, then I call a function that adds the new directories, keeping track of the numbers. The code gets a bit cleaner when organized in a class, like:

using MySet = std::unordered_set<std::string>; // 1

class FileFixIt
{
private:
    MySet paths_; // 2

public:
    FileFixIt(const std::vector<std::string>& paths); // 3

    int insert(const std::vector<std::string>& paths); // 4
};

1. I typedef'ed (C++11 style) the container I am using. Remember that the old STL set is a tree-based container that stores its elements in a ordered way. Here we don't care about ordering, so I use instead the C+11 unordered_set based on hash table.
2. The existing paths are stored here.
3. The constructor will get a number of paths (maybe zero) and store all of them in the member variable.
4. Another bunch of directories that have to be added to the hash table, but here we need also to say how many adds have been performed.

As usual, before starting developing, I have written a few test cases. Here is some of them:

TEST(FileFixIt, TestNoNews2) // 1
{
    std::vector<std::string> paths {"/a/b/c", "/b/c/d"};
    FileFixIt ffi(paths);
    EXPECT_EQ(0, ffi.insert(paths));
}

TEST(FileFixIt, TestSimple) // 2
{
    FileFixIt ffi({"/a/b/c"});
    EXPECT_EQ(3, ffi.insert({"/b/c/d"}));
}

TEST(FileFixIt, TestBadInput) // 3
{
    std::vector<std::string> paths {"a"};
    FileFixIt ffi(paths);
    EXPECT_EQ(0, ffi.insert(paths));
}

TEST(FileFixIt, Test1) // 4
{
    FileFixIt ffi({});
    EXPECT_EQ(4, ffi.insert({"/home/gcj/finals", "/home/gcj/quals"}));
}

TEST(FileFixIt, Test2) // 5
{
    FileFixIt ffi({"/chicken", "/chicken/egg"});
    EXPECT_EQ(0, ffi.insert({"/chicken/egg"}));
}

TEST(FileFixIt, Test3) // 6
{
    FileFixIt ffi({"/a"});
    EXPECT_EQ(4, ffi.insert({"/a/b", "/a/c", "/b/b"}));
}

1. In this test I create a string vector containing a couple of paths, and I use it both to create my FileFixIt object and as parameter to the call to insert(). I do expect it would return 0.
2. Here I store a path, then I insert a completely different one. The new one is composed by three parts, So the insert() function should create these new elements in its hash table, "/b", "/b/c", "/b/c/d", and return three.
3. No error handling is required in this simple test, but I'd like at least no disaster happens in case of unexpected input. If this code was meant for production, the constructor would have probably thrown an exception, since the path format is not respected. Here I am happy enough if this code does not crash.
4. First test given in the problem. No path at the beginning, two new ones passed, having the first two components in common. We expect 4 as a return value.
5. Second official test case, nothing new passed to insert(), zero should be the result.
6. Last Code Jam test, a bit more complicated, four new elements should be inserted.

I implemented the insert method in this way:

int FileFixIt::insert(const std::vector<std::string>& paths)
{
    int added = 0;

    for(std::string item : paths) // 1
    {
        while(!item.empty()) // 2
        {
            if(paths_.find(item) == paths_.end()) // 3
            {
                paths_.insert(item);
                ++added;
            }

            MySet::size_type last = item.rfind('/'); // 4
            if(last == 0 || last == std::string::npos) // 5
                break;
            item = item.substr(0, last); // 6
        }
    }

    return added;
}

1. Loop on each string passed in input. Notice that the loop variable "item" is copied from the current element in the vector, so that we can modify it without change the original value. And this matches what we declared in the function interface, being the parameter passed by constant reference.
2. If the current item is empty there is nothing to do. Otherwise we loop on it, checking all its components.
3. Is the current item already in the hash table? If not insert it and increase the counter.
4. Find the last (actually, the first starting from the reverse beginning of the string) occurrence of a slash in the string.
5. If we have reached the root, represented by the first slash in the path name, there is nothing more to do. The second check is to give a minimum of robustness to the code. If the class client passes a malformed path name, and there's no leading slash, I simply stop looping on the string. Even this simple check is kind of an overkilling in this case, on the other side, for real code this is far too less.
6. I found a slash, truncate the string to get rid of the last part, and go to the next iteration. Notice that the first part of the check on (5) is almost duplicated here. For a slash in first position, the resulting substring is empty, so the loop check on (1) would make the break redundant. Still I wanted to guarantee a loop termination in case of malformed path name.

The class constructor should do almost the same job that the insert() method. The only variation is that we don't care about the counter. Duplicating code would be a pity, so I just reused that function:

class FileFixIt
{
// ...

public:

    FileFixIt(const std::vector<std::string>& paths)
    {
        insert(paths);
    }
// ...
};

Go to the full post

Waiting asynchronously

As a first approach to ASIO make sense to write a minimal program that performs a synchronous wait on an ASIO timer, as I did in a previous post. But more interesting is setting an asynchronous wait, as we are going to see here.

This post was written in 2013, and it is getting obsolete. Please refer to its March 2018 version instead.

What I want to do here is executing a couple of actions. One has to be delivered after a certain amount of time, so I set a timer on ASIO, and ask to its I/O service to run a function when it expires. The other can be executed right away, so I'll do it in the main code, after setting the timer on ASIO, but before asking the ASIO I/O service to run.

The function that I want ASIO to execute when the timer expires is:

void hello(const boost::system::error_code& ec) // 1
{
    std::cout << "delayed hello [" << ec.value() << ']'  << std::endl;
}

1. ASIO is going to pass to to function the timer exit status. Usually we should check it, and let our code to behave differently if the timer expired correctly or with an error. A zero error code means (as for the old C tradition) success. Here I simply output its value to the user.

And that's the code snippet where ASIO is set up and run:

boost::asio::io_service aios; // 1

boost::asio::steady_timer timer(aios, std::chrono::seconds(1)); // 2
timer.async_wait(hello); // 3
std::cout << "hello" << std::endl; // 4
aios.run(); // 5

1. Create the ASIO I/O Service
2. Create a one second timer on the service
3. Run the timer asynchronously, specifying that we want to run the hello() function when it expires.
4. Do something else.
5. Pass the control to ASIO. It would keep it until it has something to do. Here we have instruct it only to take care of the timer. As soon it is done with it, it would return the control back.

If we don't get first the hello message as by (4) and then the delayed hello message as by (3), we should start to worry.

Full C++ source code, with minor variations, is on github.

Go to the full post

Condition variable on a queue

It's a typical situation in a multithreaded scenario. We have a couple of tasks, and they should synchronize on a shared data structure. To keep things simple, one produces data, the other one consumes them. Here I write a solution to this problem using C++11 synchronization primitives, and a STL queue as data structure.

The important point in this post is how to use a standard condition variable to make a STL container safe for multithreading. I have already written a couple of post on the same theme. In the first one I write a threadsafe queue by extending the STL one, in the second one I use the same approach I am using here, creating a class that rule the access to a pure STL queue, ensuring a synchronized behavior.

The main difference is that two years are passed in the meantime, and now I am using GCC 4.8 that supports C++11 to the point that I could avoid any reference to Boost libraries. In any case it would pretty easy to adapt the code to a C++03 compiler and let Boost doing the job.

Still, remember that multithreading support is not enable by default on GCC. If you don't want to get a runtime exception (with a message like this: "Enable multithreading to use std::thread: Operation not permitted") you'd better say to the linker that you want the pthread library to be linked (by -l option).

How the thing works

I wrote this little class, that acts as a wrapper around a queue:

class Conditional
{
private:
    std::queue<int> queue_; // 1
    std::condition_variable cond_; // 2
    std::mutex mutex_;

public:
    void producer(); // 3
    void consumer(); // 4
};

1. The container that is shared between the two working task I am about to use.
2. As we'll see soon, the synchronization on the queue is performed using a condition variable and a mutex.
3. The producer task runs this method, that generates data and put them in the queue.
4. This is for the consumer task, it uses data in the queue.

A client code for this class would work in this way:

Conditional c;

std::thread tc(&Conditional::consumer, &c); // 1
std::this_thread::sleep_for(std::chrono::milliseconds(1)); // 2
std::thread tp(&Conditional::producer, &c);

tc.join();
tp.join();

1. Create and start the consumer task.
2. Before creating the producer, let sleep for a tad, so that we are sure the consumer starts first (and won't find anything to consume).

The sleep between the two thread creation makes sense (obviously?) only for an informal tester as this one. You wouldn't write such a thing in production code (again, obviously?).

Producer

The job that the producer task performs is pretty boring, just pushing ten elements in the queue. I follow the convention that a zero should be interpreted as an "end of transmission" message:

void producer()
{
    for(int i = 10; i >= 0; --i)
    {
        std::unique_lock<std::mutex> lock(mutex_); // 1
        std::cout << "producing " << i << std::endl;
        queue_.push(i);
        cond_.notify_one(); // 2
    }
}

1. Before accessing the shared resources, the task acquires a lock on the designed mutex. The cool thing about unique_lock is that we don't have to explicitly release the mutex, if we don't have any reason to do it. We can rely on its destructor to do this job (it follows the RAII paradigm). Notice that in this case the mutex protects both the queue and the standard output console. Usually it is cleaner to use a mutex for each resource.
2. Once the queue has changed, we notify (one single task pending on) the condition about it.

Consumer

The consumer job is a bit more interesting:

void consumer()
{
    while(true) // 1
    {
        std::unique_lock<std::mutex> lock(mutex_); // 2
        while(queue_.empty()) // 3
        {
            std::cout << "waiting queue" << std::endl;
            cond_.wait(lock); // 4
        }
        int message = queue_.front(); // 5
        queue_.pop();

        if(!message) // 6
        {
            std::cout << "terminating" << std::endl;
            return;
        }

        std::cout << "consuming " << message << std::endl;
    }
}

1. Loop "forever", waiting for elements to be pushed in the queue.
2. Try to acquire access to the queue. Notice (again) that the mutex is actually used to protect both the queue and the output console. This is not usually a good idea.
3. Before reading, we ensure there is actually anything in it.
4. The queue is empty. Let's wait on the condition. The lock sets the mutex free, until it gets a notification that something has changed. Notice that I put the wait in a while-loop, because we should beware of spurious wakeup. In a few words, it is possible (albeit not common) to get a false positive on a condition variable, putting a wait in a if-loop could lead to rare and unexpected failures.
5. We not the queue is not empty, get an element and remove it.
6. Following the convention that a zero element means "that's all folks"

Full C++ source code for this example is on github. I have added a couple of bonus commented variations there, in the consumer code:

• After the wait on the condition variable, I checked if the wakeup is real or spurious. I have never get a spurious one. But this is not a guarantee of anything, you should still beware of spurious wakeup. If you don't care about logging and checking, you can rewrite this block in a single line:
  

  cond_.wait(lock, [this] { return !queue_.empty(); });

  The while-loop now is hidden inside the condition variable wait() call.
  
• After consuming a message, just once in a while, I added a short sleep, to see what changed in the interaction between threads on the queue. You could have a relative fun playing with it too.
  

Notice that there is no guarantee on how the scheduler select a thread to run, you could get any time a different output from this program.

Go to the full post

Hello again, Boost Asio

Some time has passed since my last post on ASIO. I guess it is worthy to restart everything from scratch, with a cute tiny hello world example that shows how ASIO can work with C++11 features.

What I am going to do is just setting a one second synchronous timer on ASIO, and wait for its expiration. But using the new chrono C++11 library.

[This example is still working alright, however, five years later, I have reviewed the code, using Boost ASIO 1.66. Please, refer to updated post instead.]

Prerequisite

I am using GCC 4.8.1 on a Linux box. But I am confident that any C++11 compliant compiler will do, on any supported platform.

You would need to have Boost too, you should get it by some repository (of your Linux distribution), or you could get it directly form Boost.

If you are on Linux, and you have installed Boost through apt-get, you should have its header files in /usr/include/boost, and the libraries in /usr/lib. This would save you some time in setting up the makefile for your application.

ASIO has a strong low-level dependency to the boost_system library, you should remember to add it to your linking (-l, if you know what I mean) options, otherwise you would get some nasty errors at linker time, like this one:

/usr/include/boost/system/error_code.hpp:214:
  undefined reference to `boost::system::generic_category()'

Wait a minute ...

This example is based on the Timer.1 page of the official Boost Asio tutorial. What I changed is that I don't use the deadline_timer, that specifies periods defined as non-standard posix_time, but the basic_waitable_timer, or better its typedef steady_timer, that relies on the C++11 chrono library. By the way, this class could use also boost::chrono, if std::chrono is not available in your environment.

std::cout << "Starting ... " << std::flush; // 1

boost::asio::io_service aios; // 2
boost::asio::steady_timer timer(aios, std::chrono::seconds(1)); // 3
timer.wait(); // 4

std::cout << "done!" << std::endl; // 5

1. I do something, included some flushed output to the standard console, so that I can see that the program is working.
2. I create an Asio I/O Service
3. I start a steady timer, meaning a timer that uses the standard C++11 chrono steady clock, on the just created I/O service, passing as requested period one single second.
4. Synchronously wait until the timer expires. If the timer had already expired when the execution stream entered the wait() method, it would return immediately.
5. Back at work, I send some more feedback to the user.

I put on github the full code for this example, slightly edited. Here I used for sake of clarity the full namespace names any time it is required. On the github version, I make use of the handy C++ namespace alias capability to shorten them down like this:

namespace ba = boost::asio;
namespace sc = std::chrono;

And another thing. For this example, including the chrono standard header is not a necessity, since it is already implicitly included by the boost asio steady timer include. But I guess it makes the code clearer.

Go to the full post

Rope Intranet

Another simple Code Jam problem is the part A of Round 1C 2010. We are asked to count the number of intersections among a bunch of segments. They all start and end at the same x values (not specified which, say 0 and 1) and they all have different y values, ranging in [1, 10000]. In the Large Dataset version of the problem, we can expect up to one thousand segments. This is a reasonable number, so we can avoid sweating too much trying to find a smart solution.

As usual, I started thinking on the interface my code would produce to the user, and setting a few tests that would drive me in the actual development. C++11 is my target language, and as xUnit framework I use is Google Test (AKA gtest).

The problem is simple enough to be solved by a single (and short) free function:

int interRope(std::vector<std::pair<int, int>> input); // 1

TEST(RopeIntra, Test1) // 2
{
    std::vector<std::pair<int, int>> input { {1, 10}, {5, 5}, {7, 7} };

    EXPECT_EQ(2, interRope(input));
}

TEST(RopeIntra, Test2) // 3
{
    std::vector<std::pair<int, int>> input { {1, 1}, {2, 2} };

    EXPECT_EQ(0, interRope(input));
}

TEST(RopeIntra, TestEmpty) // 4
{
    std::vector<std::pair<int, int>> input;

    EXPECT_EQ(0, interRope(input));
}

TEST(RopeIntra, TestHugeEmpty) // 5
{
    std::vector<std::pair<int, int>> input;
    input.reserve(1000);

    for(int i = 1; i <= 1000; ++i)
        input.push_back({i * 10, i * 10});

    EXPECT_EQ(0, interRope(input));
}

TEST(RopeIntra, TestHugeFull) // 6
{
    std::vector<std::pair<int, int>> input;
    input.reserve(1000);

    for(int i = 0; i < 1000; ++i)
        input.push_back({i, 1000 - i});

    EXPECT_EQ((1000 * 999) / 2, interRope(input));
}

1. The function gets in input a vector of int pairs, representing the start and end of each segment, and returns the number of detected intersections. Notice that the vector is passed by copy and not by reference. It is not a design mistake, there is a reason for this, I will talk more about it later.
2. First test provided with the problem itself. The three passed segments have three intersections.
3. In this case the two passed segments have no intersections.
4. What if no segment are passed? No intersection would be detected.
5. To ensure performance are not an issue, I try the biggest bunch of segments we should expect. I build a set of one thousand of parallel segments, no intersection is expected.
6. Another test on the biggest set of segments. Here I build the set so that each segment is intersecting all the other ones. How many intersections are expected? Quite a number. Let's count them. The first gives us a 999 partial result. For the second one, we should remember we have already counted the intersection with the first, so we have a 998. The third gives a 997, and so on. That means, we have a summation from 1 to 999, if you remember from your math studies, this is 1000 * 999 / 2. I used this formula in the test case instead of the actual value, assuming it is more clear in this way.

And here is the function definition:

int interRope(std::vector<std::pair<int, int>> input)
{
    if(input.empty()) // 1
        return 0;

    std::sort(input.begin(), input.end()); // 2

    int intersections = 0;
    for(unsigned i = 0; i < input.size() - 1; ++i) // 3
    {
        for(unsigned j = i + 1; j < input.size(); ++j)
        {
            if(input[i].second > input[j].second) // 4
                ++intersections;
        }
    }

    return intersections;
}

1. Below in the code (point 3) I assume there is at least a segment. Here I ensure that assumption is true.
2. That's why I pass the input parameter by value. It's easier to count the intersections if know that the segments are ordered. But I don't want to modify the original vector, so I need to work on a copy.
3. For each segment (but the last one) I check how many intersection it has with all the other segments above it.
4. Being the vector sorted, I know that the right points next to "i" are higher than it. If the j-th segment has its left point lower than the i-th one, there is an intersection.

Admittedly, this is an acceptable solution only because we work on limited input. The two nested for loops lead to an O-Square-N time complexity.

Go to the full post

Alien language

Stripping out its colorful description, the Code Jam Qualification Round 2009 Problem A, better known as Alien language, is merely a matter of applying a pattern matching function. Given a vocabulary and a pattern list, we should say how many words match to each pattern.

The major issue is that I choose to implement the solution in C++, where the regular expressions had a complicated history, and only now, with C++11, we have a standardized regex library.

But this leads to another complication. The regex implementation by GCC is still incomplete, even on the most recent version (4.8.1, when I am writing this). So I fell back to the alway reliable Boost.

My idea is creating a class, that stores the vocabulary and makes available to the user a method to check a pattern on it:

#include <vector>
#include <string>

class LangCheck
{
private:
    std::vector<std::string> vocabulary_;

public:
    LangCheck(const std::vector<std::string>& vocabulary) : vocabulary_(vocabulary) {}

    int matches(std::string pattern);
};

Yeah, right. But why passing the pattern to the matches() function by value and not by reference?

The reason is that the pattern is produced in a slightly "wrong" way, so we have to adjust it before we can use it.

Here is the test case, as derived from the input provided by the original problem:

#include <gtest/gtest.h>

TEST(AlienLang, Test)
{
    LangCheck lc({ "abc", "bca", "dac", "dbc", "cba" }); // 1

    EXPECT_EQ(2, lc.matches("(ab)(bc)(ca)")); // 2
    EXPECT_EQ(1, lc.matches("abc"));
    EXPECT_EQ(3, lc.matches("(abc)(abc)(abc)"));
    EXPECT_EQ(0, lc.matches("(zyx)bc"));
}

1. I create a temporary vector of string object on the fly, using the new C++11 initializer list, that would be automagically moved to the LangCheck data member.
2. I call the matches() methods for all the passed cases. As you see, instead of squared brackets, round ones are used. We need to modify the input to adjust it to the standard regex format.

If you plan to use boost::regex too, remember that this library is not a "pure header" one, you need to link the opportune archive, or a shareable object, to your executable. Initially I forgot to do it, and I got a number of compiling errors like:

undefined reference to boost::re_detail::perl_matcher
undefined reference to boost::basic_regex

If you have installed boost on your linux box via apt-get, you should find them in the /usr/lib folder. Once I linked boost_regex, I could happily succeed compiling my tester.

Here is how I implemented the matches() function:

#include <algorithm>
#include <boost/regex.hpp>
// ...

int LangCheck::matches(std::string pattern) // 1
{
    std::replace(pattern.begin(), pattern.end(), '(', '['); // 2
    std::replace(pattern.begin(), pattern.end(), ')', ']');

    boost::regex re(pattern); // 3

    int matching = 0;
    for(std::string word : vocabulary_)
        if(boost::regex_match(word, re)) // 4
            ++matching;

    return matching;
}

1. For what I said above, the input string is passed by value.
2. Using the standard algorithm replace() function, that works on any STL container supporting forward iterator, I adjust the brackets in the pattern.
3. Create a boost regex object from the modified pattern.
4. Let's count how many words in the current vocabulary matches the pattern. Any success would increment the counter, that in the end would be returned.

Go to the full post

Minimum Scalar Product

In its small dataset input version, the 2008 Code Jam Round 1A problem A, known as Minimum Scalar Product, was solved by almost all the users. Still, the large dataset one was an harder nut to crack, with less than half the participant getting it right. This probably means that the real issue on this problem is about the time complexity of the solving algorithm, and the involved data type. That makes sense, because the question looks easy to solve, at least in its abstract form, but we need to put some attention on its special cases.

In few words, the problem boils down to this request: we have in input two vectors, we want to reorganize them so to minimize its scalar product.

Some theory

Your mathematical background should tell you what the scalar product of vectors is. It has a couple of other names, dot product and inner product, it takes two vectors having the same size, and gives back a single value (just a "scalar"). The result is calculate summing the products of all the elements in the same place on the two vectors (an "inner" product). If you wonder why its "dot" name, is just a matter of notation, a dot is traditionally used to represent the operation.

Your geometrical background could give you an hint to understand how to reorganize the vector. You should remember that a square is the rectangle with maximum area among the ones having the same perimeter. Here we want to minimize the result, so we'll try to stay away as much as we can from that case. We can easily do it sorting the vectors, one in the ascending order, the other descendingly.

Algorithms and data types

Following the large dataset requirements, we need to be prepared to accept input values up to 100,000 (positive or negative). This doesn't look much, but remember we are talking about multiplying, so we need to be able to work with operations like 100,000 * 100,000 and we know that 10,000,000,000 does not fit in a 32 bit integer. Meaning that we should work with 64 bit integers.

We should also be prepared to work with sequences of hundreds of values, meaning that we can't spend too much time looking for the minimal product among elements. But this point is already covered by the bit of theory I have given above. We'll sort the vectors, and this is costing O(N Log N) for each one, before multiplying, a linear O(N) operation.

Testing

For what I said above, I am going to define a function following this prototype:

int64_t minScalarProduct(std::vector<int64_t> x, std::vector<int64_t> y)

Actually, you could be smarter than me, and use cheaper "naked" int in input and more expensive 64 bit int only in output. But this sloppiness helps me to write code more concise, readable and elegant, as we'll see in a moment.

I used the explicit int64_t to avoid portability issues. I let the compiler to match it to long or long long, accordingly to the actual platform.

Some tests (for googletest) I wrote for my C++11 code:

#include <vector>
#include <stdexcept>
#include <gtest/gtest.h>

TEST(MinScalar, Test1) // 1
{
    std::vector<int64_t> x { 1, 3, -5 };
    std::vector<int64_t> y { -2, 4, 1 };

    EXPECT_EQ(-25, minScalarProduct(x, y));
}

TEST(MinScalar, Test2)
{
    std::vector<int64_t> x { 1, 2, 3, 4, 5 };
    std::vector<int64_t> y { 1, 0, 1, 0, 1 };

    EXPECT_EQ(6, minScalarProduct(x, y));
}

TEST(MinScalar, BiggestNegativeOne) // 2
{
    std::vector<int64_t> x(800, 100000);
    std::vector<int64_t> y(800, -100000);

    EXPECT_EQ(-8000000000000, minScalarProduct(x, y));
}

TEST(MinScalar, BadSized) // 3
{
    std::vector<int64_t> x { 1, 2 };
    std::vector<int64_t> y { 1 };

    EXPECT_THROW(minScalarProduct(x, y), std::range_error);
}

1. A couple of tests are provided in the problem descriptions. I have simply rewritten them here.
2. I wrote a few test for the extreme cases, here is probably the most demanding one. The max size expected is 800, and the biggest value expected is |100,000|. I create one all-positive vector, one all-negative, and then I ask for its minimal scalar product. I expect -8,000,000,000,000 as a result.
3. This check was not required by the problem, but I couldn't stop myself of being a bit paranoid and ask what happens if the input vector have different sizes. I decided to let the function throw a C++ standard range_error exception. It would have been cleaner to create a specific exception type.

Developing

In the end, I came up writing this code:

#include <vector>
#include <algorithm>
#include <numeric>
#include <stdexcept>

int64_t minScalarProduct(std::vector<int64_t> x, std::vector<int64_t> y)
{
    if (x.size() != y.size())
        throw std::range_error("check input sizes"); // 1
 
    std::sort(x.begin(), x.end()); // 2
    std::sort(y.begin(), y.end(), std::greater<int64_t>()); // 3

    return std::inner_product(x.begin(), x.end(), y.begin(), static_cast<int64_t>(0)); // 4
}

1. As specified by the BadSized test case, I throw an exception to signal a weird input.
2. Sort "naturally" (ascendingly) the first vector.
3. Sort the second vector descendingly.
4. The STL provides inner_function to calculate the scalar product, using it makes the code sleeker, still it brings a couple of nuisances. It multiplies the container values accordingly to their type, and this is usually what we want to do. That's way I forced the vector underlying type to be a 64 bit integer. The result of the product is added to the last value passed to the function, so its type is fundamental, too. If I don't cast it to int64_t, I'll still have the overflow issue.

Go to the full post

Triangle trilemma

The problem A of the Code Jam Beta 2008 sports a few interesting points. It could be considered a geometrical question, it boils down to knowing how to determine what kind of a triangle we have knowing its three vertices.

We are asked to say if the passed three points are actually a triangle (alternatively, they could be collinear, lying on the same line); if it is acute (all angles are less than 90 degrees), right (one angle is exactly 90 degrees), or obtuse (one angle is more than 90 degrees); and if it is scalene (all sides have a different length) or isosceles. In case of equilateral triangle, we are allowed to give back an imprecise answer, falling back to isosceles.

Before even start thinking about coding, I think it is better to refresh the underlying theory, clarifying what I want to get.

Collinear points

Let's call our points A, B, and C. They determine three segments, AB, BC, and AC. If two of them are collinear, we get for free that the third one is collinear too. It is easy to figure out that, at least in a Euclidean geometry, it has no other chance.

Our job is to compare the slope of whichever two segments. If it is the same, the three points are collinear.

Given our two points, A = (ax, ay) and B = (bx, by), the slope of the line determined by them is: (by - ay) / (bx - ax).

Similarly goes for the other segment, say BC: (by - cy) / (bx - cx), so we could say that the three points are collinear if and only if:

(by - ay) / (bx - ax) = (by - cy) / (bx - cx)

Cool. But you have to pay attention to a couple of details. Firstly, you don't want to divide by zero, and secondly you don't want to divide at all, if you just can avoid it. A division leads often to rounding problems, with consequent headaches.

So we'd better rewrite the equation above to multiply instead of divide. Also multiplications could give to the programmer their shares of trouble (overflow would probably be its name), but here the problem is designed to let them out of the window, since we deal with tiny numbers. This is the equation I am going to use in my code:

(by - ay)*(bx - cx) = (by - cy)*(bx - ax)

Type by angles

Thanks to the Pythagorean theorem, we can easily detect if a triangle is right. As anyone should know, in a rectangle triangle, the sum of the squares of the lengths of the two catheti is equal to the square of the length of the hypotenuse.

Given the lengths of the three sides, it is just a matter of comparing the square of the biggest (let's call it SQx) against the sum of the square of the other two (SQy and SQz):

SQx < SQy + SQz -> obtuse
SQx > SQy + SQz -> acute
SQx = SQy + SQz -> right

Type by sides

That's pretty easy. Assuming that we have the length of each side, if at least two of them are the same we say our triangle is isosceles. We could be more precise, and checking also if all the three of them have the same length (equilateral triangle), but this is not required, and so we should sadly avoid it.

Side length

Both the previous point require the sides length to work. Given two vertices coordinates, we calculate that side length applying (again) the Pythagorean theorem. Actually, to get the value, we should calculate the square of delta x and delta y, sum them, and then extract the square. But we'd better being lazy, and stop at the second step. Instead of calculating the length, get its squared value. In this way we'll avoid a costly operation, and also the usual rounding problems.

Besides, for determine the angles we are specifically requested for the squared values, and for the sides working with the actual value or its square is a non-issue.

This is what I have to do to calculate the squared length of a segment AB:

SQ(A,B) = square(B.y - A.y) + square(B.x - A.x)

Work on triangles with class

Large part of the job is done. I just have to implement the solution. I choose C++ with gtest for the TDD support. It should be a non issue to adapt my code to other languages.

Firstly, a couple of type defines. We are working in a two-dimensional plane, where point are defined are pairs (abscissa, ordinate). And we'll need to operate to collections of exactly three points:

typedef std::pair<int, int> Point;
typedef std::array<Point, 3> Points;

Pair are a well know citizen of the STL nation, array joined the company with C++11. Letting us specify the number of elements in its declaration, it is more expressive than a vector in this context.

I designed a Triangle class having such private data members:

class Triangle
{
private:
  enum Angle { OBTUSE, ACUTE, RIGHT };

  Points vertices_; // 1
  std::array<int, 3> squaredLengths_; // 2
  bool collinear_; // 3

// ...

1. My triangle is described by its vertices.
2. This data member is not strict necessity, it is just a way of saving some computation time using some more space.
3. Ditto.

The real job described above is done by three private function members:

class Triangle
{
private:
  // ..

  int squaredLength(const Point& a, const Point& b) // 1
  {
    return std::pow(b.second - a.second, 2) + std::pow(b.first - a.first, 2);
  }

  bool scalene() // 2
  {
    if(collinear_)
      return false;

    return !(squaredLengths_[0] == squaredLengths_[1] || squaredLengths_[0] == squaredLengths_[2] || squaredLengths_[1] == squaredLengths_[2]);
  }

  Angle angle() // 3
  {
    int ssq = squaredLengths_[0] + squaredLengths_[1];
    return ssq < squaredLengths_[2] ? OBTUSE : ssq > squaredLengths_[2] ? ACUTE : RIGHT;
  }

// ...

1. Utility function to calculate the squared length of the passed segment using the Pythagorean theorem. It is called by the constructor.
2. Is this triangle scalene? If this is not an actual triangle (the three points are collinear) the question makes no sense. I could have thrown an exception, but I decided for a more forgiving behavior. Otherwise let's check if there is at least a couple of sides with the same length. Actually, for the reason described above, I check the squared lengths instead.
3. To ensure that I correctly apply the Pythagorean theorem, I have sorted the squared lengths (see the constructor). It is very easy now to determine if the triangle is obtuse, acute, or right.

In the public interface I left just the constructor and a method to get the required answer:

class Triangle
{
// ...
public:
  Triangle(const Points& p) : vertices_(p), collinear_(false) // 1
  {
    if((p[1].second - p[0].second) * (p[2].first - p[0].first) == (p[1].first - p[0].first) * (p[2].second - p[0].second))
      collinear_ = true;

    squaredLengths_[0] = squaredLength(p[0], p[1]); // 2
    squaredLengths_[1] = squaredLength(p[0], p[2]);
    squaredLengths_[2] = squaredLength(p[1], p[2]);
    std::sort(squaredLengths_.begin(), squaredLengths_.end());
  }

  std::string description() // 3
  {
    std::string result("triangle");
    if(collinear_)
      return "not a " + result;

    Angle ang = angle();
    result.insert(0, ang == OBTUSE ? "obtuse " : ang == ACUTE ? "acute " : "right ");
    result.insert(0, scalene() ? "scalene " : "isosceles ");
    return result;
  }
};

1. The constructor create a triangle from a collection of three points. The points are stored in the private data member vertices_, the collinear_ flag is set accordingly to what we discussed in the section "Collinear points". A real life class should add more checking on the input parameters. Here I rely on the client fairness.
2. Each side squared length is calculated and stored in the private data member squaredLengths_, then the array is sorted, following the natural sorting function, so that the longest one is last (position 2).
3. Build a string containing a triangle description.

Test cases

As usual, I let the design of my code to be driven by test cases. I'm using here the Google C++ Testing Framework (friendly known as googletest), but you should easily adapt them to any xUnit framework you like.

Firstly I have written the test cases provided by the problem itself. Here are the first and last of them:

#include "gtest/gtest.h"

TEST(TestTrilemma, CaseSample1)
{
  Triangle triangle({{ Point(0, 0), Point(0, 4), Point(1, 2) }}); // 1
  ASSERT_EQ("isosceles obtuse triangle", triangle.description());
}

TEST(TestTrilemma, CaseSample8)
{
  Triangle triangle({{ Point(7, 7), Point(7, 7), Point(7, 7) }});
  ASSERT_EQ("not a triangle", triangle.description());
}

1. Maybe is worthy spend a few words on this line. I am creating an object Triangle, passing to it a brace-enclosed initializer list (C++11 goodies) to initialize on the fly a temporary array object, as required by the constructor. Being this an rvalue, the move flavor for the Triangle vertices_ data member constructor will be called, resulting in sleeker code.
Right. But why the double braces? Wasn't one brace enough? No, it wasn't enough. And this is a compiler, and not a language issue. Currently, the GCC compiler get sometimes confused by a single-braced initializer list. This is one of those cases. If you put just a single brace there, you should get a very confusing diagnostic output. But if you write the same code in a simpler way, like this:

Points ps = { Point(0, 0), Point(0, 4), Point(1, 2) };
Triangle triangle(ps);

You should get a cleaner message, a warning like "missing braces around initializer".

Then I have added a few more test cases, exploring different setting. Here are some of them:

TEST(TestTrilemma, CaseCentered) // 1
{
  Triangle triangle({{ Point(0, -2), Point(0, 2), Point(1, 0) }});
  ASSERT_EQ("isosceles obtuse triangle", triangle.description());
}

TEST(TestTrilemma, CaseNegative) // 2
{
  Triangle triangle({{ Point(-1000, -500), Point(-1000, -1000), Point(-100, -700) }});
  ASSERT_EQ("scalene acute triangle", triangle.description());
}

TEST(TestTrilemma, CaseHuge3) // 3
{
  Triangle triangle({{ Point(-1000, 0), Point(-1000, -1000), Point(1000, 1000) }});
  ASSERT_EQ("scalene obtuse triangle", triangle.description());
}

1. What if the triangle is (sort of) centered on the plane origin?
2. Could we have an issue on a Triangle lying in the plane negative quarter?
3. The problem requirements state that the Triangle points must be in the [-1000, 1000] range. I didn't enforced this constrain in the code, but I ensured with a number of tests that my class works fine with the biggest expected triangles.

Go to the full post