HackerRank Divisible Sum Pairs

Given a list of integers, we want to know how many couples of them, when summed, are divisible by a given integer k.

So, for instance, given [1, 2, 3, 4, 5, 6], we have five couples of items with sum divisible by 3:

(1, 2), (1, 5), (2, 4), (3, 6), (4, 5)

This is a HackerRank algorithm problem, implementation section.

Naive solution

Test all the couples, avoiding duplicates. If we check (a1, a2), we don't have to check (a2, a1).

The code I have written for this solution should be of immediate comprehension, even if you are not that much into Python:

result = 0
for i in range(len(values) - 1):  # 1
    for j in range(i+1, len(values)):  # 2
        if (values[i] + values[j]) % k == 0:  # 3
            result += 1

1. Loops on all the indices in the list but the last one.
2. Loops from the next index to the current "i" to the last one.
3. Check the current couple, and increase the result if compliant.

Even if this is what HackerRank was expecting from us (the problem is marked as easy), we can do better than this, considering its disappointing O(N^2) time complexity.

Linear solution

The problem could be restated as counting the couples that, added up, equal to zero modulo k. Following this insight, let's partition the items accordingly to their own modulo.

remainders = [0] * k
for i in range(len(values)):
    remainders[values[i] % k] += 1

Each element in the "remainders" list represents the number of items in the original list having as modulo the index of the element.

For the example shown above we'll get this remainders:

[2, 2, 2]

Now, if we add an element having remainder x to element with remainder k - x, we'll get a number equal zero modulo k. We want all the possible combinations of the x elements with the k - x ones, so we apply the Cartesian product to the two sets, that has a size that is their product.

There are a couple of exceptions to this rule. The elements having modulo zero have to be added among themselves, and the same happens to the element having as modulo half k, if k is even. The number of combinations of a set of N elements could be expressed as N * (N-1) / 2.

Putting all together we have this code:

result = remainders[0] * (remainders[0] - 1) // 2  # 1

pivot = k // 2  # 2
if k%2:
    pivot += 1  # 3
else:
    result += remainders[k//2] * (remainders[k//2] - 1) // 2  # 4

for i in range(1, pivot):  # 5
    result += remainders[i] * remainders[k-i]

1. Initialize "result" using the above described formula for the modulo zero items.
2. Let's calculate the central element in the list, where we have stop looping to sum up.
3. If k is odd, we won't have a lonely central element, and the pivot should be moved a step to the right.
4. When k is even, the elements having half-k modulo are managed as the zero modulo ones.
5. Normal cases.

After the for-loop, result contains the answer to the original question.

I pushed a python script with both solutions, naive and remainder based, to GitHub, along with a few tests.

Go to the full post

Boost ASIO echo UDP asynchronous server

A change request for the echo UDP client-server app discussed before. We want keep the client as is, but we need the server be asynchronous.

Instead of using the synchronous calls receive_from() and send_to() on a UDP socket, we are going to use their asynchronous versions async_receive_from() and async_send_to().

The asynchronicity leads naturally to implement a class, having a socket has its private data member, so that we can make our asynchronous call on it.

const int MAX_LEN = 1'024;
const uint16_t ECHO_PORT = 50'015;

class Server
{
private:
    udp::socket socket_;  // 1
    udp::endpoint endpoint_;  // 2
    char data_[MAX_LEN];  // 3

// ...

1. Our ASIO UDP socket.
2. The endpoint we use to keep track of the client currently connected to the server.
3. Data buffer, used to keep track of the message received from the client.

The constructor gets the app ASIO I/O context by reference from the caller and uses it to instantiate its member socket. Then it calls its private method receive() to start its endless job.

Server(ba::io_context& io) : socket_(io, udp::endpoint(udp::v4(), ECHO_PORT))  // 1
{
    receive();
}

void receive()
{
    socket_.async_receive_from(ba::buffer(data_), endpoint_, [this](bs::error_code ec, std::size_t len) {  // 2
        if (!ec && len > 0)  // 3
        {
            send(len);
        }
        else
        {
            receive();  // 4
        }
    });
}

1. The socket requires also an endpoint describing the associated protocol and port. We create it on the fly.
2. Call asynchronously receive_from on the socket. ASIO would put in the data buffer what the client sends and store its network information in the passed endpoint. When the socket receive is completed, ASIO would call the handler passed as third parameter, here a lambda that captures "this" and honors the expected parameters.
3. If the receiving worked fine - no error_code reported - and the message is not empty, we'll call our Server send() method, to echo the message.
4. Otherwise - error or empty message - we don't have to send anything back, so we call the enclosing receive() method, to serve a new client.

When a "good" message is received from a client, our server sends it back to it as is:

void send(std::size_t len)
{
    socket_.async_send_to(ba::buffer(data_, len), endpoint_, std::bind(&Server::receive, this));
}

The socket gets the job of asynchronously send the data, as stored in the Server member variable, with the length, as passed in as parameter, to the endpoint saved as Server member variable. When the data transfer is completed, ASIO would call the handler passed as third argument. Here we don't want to do anything in case or error, not even logging something, so we can simply bind to the handler a call to "this" receive(), ignoring error code and length of the transferred data.

I pushed the complete C++ source file to GitHub. The code is based on the UDP asynchronous echo example in the official Boost ASIO documentation.

Go to the full post

Boost ASIO echo TCP asynchronous server

Let's refactor the echo TCP server to achieve asynchrony. It's going to be a lot of fun. If you feel that it is too much fun, you could maybe have first a look at the similar but a bit simpler asynchronous server discussed in a previous post.

Main

This server works with the same clients as seen for the synchronous server, here we deal just with the server. All the job is delegated to the Server class, whose constructor gets a reference to the application ASIO I/O context.

namespace ba = boost::asio;
// ...

Server server(io);
io.run();

Server

The server ctor initialize its own acceptor on the ASIO I/O context on the endpoint specifying the TCP IP protocol and port chosen, then it calls its private member method accept():

using ba::ip::tcp;
// ...

const uint16_t ECHO_PORT = 50'014;
// ...

class Server
{
private:
 tcp::acceptor acceptor_;

 void accept()
 {
  acceptor_.async_accept([this](bs::error_code ec, tcp::socket socket)  // 1
  {
   if (!ec)
   {
    std::make_shared<Session>(std::move(socket))->read();  // 2
   }
   accept();  // 3
  });
 }
public:
 Server(ba::io_context& io) : acceptor_(io, tcp::endpoint(tcp::v4(), ECHO_PORT))
 {
  accept();
 }
};

1. As handler to async_accept() is a lambda that gets as parameters an error code that let us know if the connection from the client has been accepted correctly, and the socket eventually created to support the connection itself.
2. A beautiful and perplexing line. We create a shared_prt smart pointer to a Session created from a rvalue reference to the socket received as parameter, and call on it its read() method. However this anonymous variable exits its definition block on the next line, so its life is in danger - better see what is going on in read(). Actually, we are in danger, too. If something weird happens in this session object, we don't have any way to do anything about.
3. As soon as a Session object is created, a new call to accept() is issued, an so the server puts itself in wait for a new client connection.

Session

As we have seen just above, we should expect some clever trick from Session, especially in its read() method. Thinking better about it, it is not a big surprise seeing that its superclass is enable_shared_from_this:

class Session : public std::enable_shared_from_this<Session>
{
private:
 tcp::socket socket_;
 char data_[MAX_LEN];

// ...
public:
 Session(tcp::socket socket) : socket_(std::move(socket)) {}  // 1

 void read()  // 2
 {
  std::shared_ptr<Session> self{ shared_from_this() };  // 3
  socket_.async_read_some(ba::buffer(data_), [self](bs::error_code ec, std::size_t len) {  // 4
   if (!ec)
   {
    self->write(len);
   }
  });
 }
};

1. The ctor gets in the socket that we seen was created by the acceptor and moved in, in its turn, the constructor moves it to its data member.
2. The apparently short lived Session object created by the handler of async_accept() calls this method.
3. A new shared_ptr is created from this! Actually, being such, it is the same shared_prt that we have seen in the calling handler, just its use counter increased. However, our object is still not safe, we need to keep it alive until the complete read-write cycle between client and server is completed.
4. We read asynchronously some bytes from the client. To better see the effect, I have set the size of the data buffer to a silly low value. But the more interesting part here is the handler passed to async_read_some(). Notice that in the capture clause of the lambda we pass self, the shared pointer from this. So our object is safe till the end of the read.

So far so good. Just remember to ensure the object doesn't get invalidated during the writing process:

void write(std::size_t len)
{
 std::shared_ptr<Session> self{ shared_from_this() };
 ba::async_write(socket_, ba::buffer(data_, len), [self](bs::error_code ec, std::size_t) {
  if (!ec)
  {
   self->read();
  }
 });
}

Same as in read(), we ensure "this" stays alive creating a shared pointer from it, and passing it to the async_write() handler.

As required, as the read-write terminates, "this" has no more live references. Bye, bye, session.

I have pushed my C++ source file to GitHub. And here is the link to the original example from Boost ASIO.

Go to the full post

Boost ASIO echo UDP synchronous client-server

Close to the previous post. The main difference that there we have seen a TCP-based data exchange while here we see a UDP echo.

Server

This server is simpler than the previous one. Just one connection is served at a time.

udp::socket socket(io, udp::endpoint(udp::v4(), ECHO_PORT));  // 1

for (;;)  // 2
{
 char data[MAX_LEN];
 udp::endpoint client;
 size_t len = socket.receive_from(ba::buffer(data), client);  // 3

 // ...
 socket.send_to(ba::buffer(data, len), client);  // 4
}

1. Create an ASIO UDP socket on the app io_context, on a UDP created on the fly where the UDP IP protocol and the port to be used are specified.
2. Forever loop to serve, in strict sequential order, all the requests coming from clients.
3. ASIO blocks here, expecting the socket to receive a connection from a client. Make sure that the buffer data is big enough.
4. Since this is an echo server, nothing exciting happens between receiving and sending. Here we send the data, as received, to the endpoint as set by receive_from().

Client

char request[MAX_LEN];
// ...

udp::socket socket{ io, udp::endpoint(udp::v4(), 0) };  // 1
udp::resolver resolver{ io };
udp::endpoint destination = *resolver.resolve(udp::v4(), host, ECHO_PORT_STR).begin();  // 2
socket.send_to(ba::buffer(request, std::strlen(request)), destination);  // 3

char reply[MAX_LEN];
udp::endpoint sender;
size_t len = socket.receive_from(ba::buffer(reply), sender);  // 4
// ...

1. Create a UDP socket on the ASIO I/O context. Notice that the UDP endpoint passed specify the IP protocol but not a valid port.
2. The destination endpoint, that refers to the server, is generated by the resolver created on the line above, that resolves the specified host and port for the given UDP IP protocol. Then the first result is taken (by the begin iterator and then dereferencing). In case of any trouble we have guarantee an exception is thrown by resolve().
3. Send the data through buffer to the socket, that mediates the connection to the server.
4. Once send_to() has ended its job (notice that it is a blocking function), we get the reply from the server calling receive_from(). The socket knows where to go and get the data, and will fill the passed endpoint (sender) with these information.

I pushed the full C++ code - both client and server in the same source file - to GitHub. I based them on blocking_udp_echo_server.cpp and blocking_udp_echo_client.cpp from the official Boost ASIO Tutorial.

Go to the full post

Boost ASIO echo TCP synchronous client-server

I think this echo client-server application is a good introduction to ASIO. The server creates a new TCP socket each time it receives a request from a client, and run it in a new thread, where the read-write activity is accomplished in a synchronous way. The client sends some data to the server, gets it back, and then terminates.
The structure is simple, still a few interesting points are touched.

Client

Given io, the app ASIO io_context, and the server hostname as a string, the client tries this block, and eventually just output to console an exception.

namespace ba = boost::asio;
using ba::ip::tcp;
// ...

tcp::socket socket{ io };  // 1
tcp::resolver resolver{ io };
ba::connect(socket, resolver.resolve(host, ECHO_PORT_STR));  // 2

// ...
ba::write(socket, ba::buffer(request, reqLen));  // 3

char reply[CLIENT_MAX_LEN];  // 4
size_t repLen = ba::read(socket, ba::buffer(reply, reqLen));  // 4
// ...

1. Create an ASIO TCP socket and a resolver on the current io_context.
2. Then resolve() the resolver on the host and port of the echo server (in my case, localhost:50014), and use the resulting endpoints to estabilish a connection on the socket.
3. If the connection holds, write to the socket the data we previously put in the char buffer named request, for a size of reqLen.
4. We reserve a confidently large buffer where to store the server reply. Since we are writing a echo application, we know that the size of the data we are about to get from the client should be the same of the size we have just sent. This simplify our code to the point that we can do a single read for the complete data block.
5. Use the socket for reading from the server. We use the buffer, and the size of the data we sent, for what said on (4).

At this point we could do whatever we want with the data we read in reply with size repLen.

Server loop

Once we create an acceptor on the ASIO io_context, specifying as endpoint the IP protocol we want (here I used version 4) and the port number, we loop forever, creating a new socket through a call to accept() on the acceptor each time a request comes from a client, passing it to the session() function that is going to run in a new thread.

tcp::acceptor acceptor{ io, tcp::endpoint(tcp::v4(), ECHO_PORT) };

for (;;)
{
 std::thread(session, acceptor.accept()).detach();
}

Notice that each thread created in the loop survives the exiting of the block only because it is detached. This is both handy and frightening. In production code, I would probably push them in a collection instead, so that I could explicitly kill anyone that would stop behave properly.

Server session

Since we don't know the size of the data sent by the client, we should be ready to split it and read it in chunks.

for (;;)
{
 char data[SERVER_MAX_LEN];  // 1

 bs::error_code error;
 size_t len = socket.read_some(ba::buffer(data), error);  // 2
 if (error == ba::error::eof)
 {
  return;
 }
 else if (error)
 {
  throw bs::system_error(error);
 }

 ba::write(socket, ba::buffer(data, len)); // 3
}

1. To better see the effect, I have chosen a ridiculously small size for the server data buffer.
2. The data coming from the client is split in chunks from read_some() on the socket created by the acceptor. When the read is completed, read_some() sets the passed boost system error to eof error. When we detect it, we know that we could terminate the session. Any other error says that the something went wrong.
3. If read_some() set no error, we use the current chunk of data to do what the server should do. In this case, we just echo it back to the client.

Full C++ code on GitHub. The original source is the official Boost ASIO tutorial, divided in two parts, client and server.

Go to the full post

Boost ASIO UDP asynchronous server

Having already seen how to establish an ASIO UDP synchronous connection and how create ASIO TCP asynchronous server, we sort of put them together to write an ASIO UDP asynchronous server.

Main

As client we could happily recycle the one written for the UPD synchronous connection - only, be sure to use the same IP protocol for both. So in the main function we just instantiate an ASIO io_context (also known as io_service), pass it by reference to the ctor of a Server object, and then call run() on it.

In a second time, while running a number of clients to play with the app, you would want to run io also in other threads - be sure to do that between the server creation and the io run on the current thread.

Server class

The server would sit on port 50013 and send to the clients always the same message, concatenated with to a counter. To work it needs an ASIO UPD socket and a UDP endpoint that would identify the current client.

// ...
const int HELLO_PORT = 50'013;
const std::string MSG("Async UDP hello from ASIO ");

class Server
{
private:
 udp::socket socket_;
 udp::endpoint endpoint_;
 uint16_t counter_ = 0;
// ...
public:
 Server(ba::io_context& io) : socket_(io, udp::endpoint(udp::v6(), HELLO_PORT))
 {
  start();
 }
};

The server ctor sets the socket data member up using the reference to the ASIO io context received from the instantiator and a UDP endpoint created on the fly, specifying the required IP protocol (here version 6) and the server port.

Then the server start() private method is called:

void start()
{
 std::array<char, 0> buffer;  // 1
 socket_.async_receive_from(ba::buffer(buffer), endpoint_,
  std::bind(&Server::recvHandler, this, std::placeholders::_1));  // 2
 std::cout << "Server ready" << std::endl;
}

1. The client is expected to send an empty message, so the receive buffer could be zero sized.
2. We call async_receive_from() to receive asynchronously from the client a message in buffer. We'll get the client endpoint information in the data member and, on receive completion, it will call another Server's private method, recvHandler(), passing to it the first parameter that ASIO was expected to send, namely a reference to the boost system error_code describing how the async_receive_from() was completed.

If no error was detected in async_receive_from(), the recvHandler() creates a message and sends it to the client:

void recvHandler(const bs::error_code& error)
{
 if (!error)
 {
  std::shared_ptr<std::string> data(new std::string(MSG + std::to_string(++counter_)));  // 1

  socket_.async_send_to(ba::buffer(*data), endpoint_,
   std::bind(&Server::sendHandler, this, data, std::placeholders::_1, std::placeholders::_2));  // 2
  start();
 }
}

1. This piece of code is a bit involuted. We create on the heap a string containing the data to be send to the client, and we wrap it in a shared pointer. In this way we can keep it alive in a multithreading environment until we need it, that is, the end of the sendHandler() method invoked by async_send_to() at the end of its operation.
2. async_send_to() uses the endpoint set by async_receive_from() to know where sending the data. At the end, sendHandler() is called.

From the ASIO point of view, sendHandler() could be an empty method. The only important thing is that the data created in recvHandler() gets here in the shared smart pointer, so that it can ensure it not to be destroyed when still required.

void sendHandler(std::shared_ptr<std::string> data, const bs::error_code& error, std::size_t size)
{
 if (!error)
 {
  std::cout << size << " byte sent from [" << *data << "]" << std::endl;
 }
}

I pushed the full C++ source code on GitHub. It is based on the Daytime.6 example from the official Boost ASIO tutorial.

Go to the full post

Boost ASIO synchronous UDP client/server

If you know how to write an app that uses an ASIO TCP connection, you are close to know also how to do it on UDP.

Large part of the differences are taken care for us in ASIO, and we just have to use the socket as defined in boost::asio::ip::udp instead of its tcp counterpart.

Server

First thing, we create a udp socket, that requires the ASIO I/O context and a udp endpoint, that needs as parameters the IP protocol to be used - version 4 or 6 - and the port - here I picked up 50013.

namespace ba = boost::asio;
namespace bs = boost::system;
using ba::ip::udp;
// ...

const unsigned short HELLO_PORT = 50'013;
// ...

void server(ba::io_context& io)
{
    udp::socket socket{ io, udp::endpoint{udp::v6(), HELLO_PORT} };
 // ...

Then we repeat how many times we like this block - in my tester I did it just once:

std::array<char, 0> recvData;  // 1
udp::endpoint endpoint;  // 2
bs::error_code error;  // 3
socket.receive_from(ba::buffer(recvData), endpoint, 0, error);  // 4
if (error)
 throw bs::system_error(error);  // 5

std::string message{ "UDP hello from ASIO" };

bs::error_code ec;
socket.send_to(boost::asio::buffer(message), endpoint, 0, ec);  // 6

1. In this buffer we store the message sent from the client. It has no use here, so it could be it even zero sized.
2. The endpoint, that will be used to sent the message to the client, is set by the socket receive_from() method, two lines below.
3. This error code is set by receive_from(), in case of problems.
4. The server wait synchronously here for the client. The three parameters are output ones. When the connection starts, the data coming from the client is put in the first parameter (here, an empty message is expected), the second parameter is filled with the client endpoint, the last one stores the possible error in the operation.
5. If receive_from() fails, throw the boost system error code relative exception, that is a standard runtime_error subclass.
6. Send the message to the client, using the endpoint as set by receive_from() and not specifying any flag. Any possible error code returned is disregarded.

Client

The client function tries this code:

udp::resolver resolver{ io };
udp::endpoint destination = *resolver.resolve(udp::v6(), host, HELLO_PORT_STR).begin();  // 1

udp::socket socket{ io };
socket.open(udp::v6());  // 2

std::array<char, 0> sendData;
socket.send_to(ba::buffer(sendData), destination);  // 3

std::array<char, 128> recvData;  // 4
udp::endpoint sender;
size_t len = socket.receive_from(ba::buffer(recvData), sender);

std::cout.write(recvData.data(), len);  // 5

1. Having instantiated a udp resolver on the previous line, we resolve() on it for the same IP protocol of the server - here I used version six - specifying its host and port. Since resolve() returns at least one endpoint or fails, we could safely access the first one dereferencing its begin() iterator.
2. We need an ASIO upd socket. Having created it on the previous line, passing the current ASIO I/O control, we open it for the required UDP version.
3. We start the communication with the server, sending an empty message - as nothing more is expected from it.
4. We'd better have enough room for the message coming from the server, the actual size of it is returned by the call to receive_from().
5. Let's see what we get, outputting it to the console.

Client and server are two free functions in the same C++ file that I pushed to GitHub. Passing no parameter to its main you run it as server, otherwise is a client.

This example is based on Daytime.4 and Daytime.5 from the official Boost ASIO tutorial.

Go to the full post

Boost ASIO TCP/IP asynchronous server

Having seen how simple is creating a synchronous ASIO TCP/IP server, let's see now how to create an asynchronous one.

Main

The code for this example is divided in two classes, Server and Connection, described below. The example main function instantiates an ASIO io_context, uses it to instantiate a Server object, and then run() the I/O context.

namespace ba = boost::asio;
// ...

ba::io_context io;
Server server(io);
io.run();

Connection

The lower details of our code are here. Connection has as private data member an ASIO TCP/IP socket object on which we are going to write data to the client. Since we want to perform the write asynchronously, we use the ASIO async_write() function. This leads us to ensure that the current connection object is still alive when the write would actually be performed. To do that we'll pass to async_write() an instance of the connection object itself. To avoid a nightmarish memory management, we'll wrap it in a shared_ptr. However, to to that, we need to create a shared smart pointer from this, and to do that we have to enable the feature explicitly, deriving our class from the standard enable_shared_from_this:

class Connection : public std::enable_shared_from_this<Connection>
{
private:
 tcp::socket socket_;
 std::string message_{ "Async hello from ASIO " };
 static int counter_;

// ...

The Connection ctor creates its member socket using the passed ASIO I/O context, and sets the message that we'll send to the client. Notice that the message has to be a Connection data member because we have to guarantee its liveliness until the asynchronous write is performed.

Connection(ba::io_context& io) : socket_(io)
{
 message_ += std::to_string(counter_++);
}

However, the ctor is private. The only way we want to let a Connection user to create an instance of this class is by wrapping it in a smart pointer, for the reason we described above, so, we have this static public method:

static std::shared_ptr<Connection> create(ba::io_context& io)
{
 return std::shared_ptr<Connection>(new Connection(io));
}

The writing is performed by this public method:

void start()
{
 ba::async_write(socket_, ba::buffer(message_),
  std::bind(&Connection::write, shared_from_this(), std::placeholders::_1, std::placeholders::_2));
}

ASIO async_write() requires an AsyncWriteStream, our socket, a ConstBufferSequence, that we create on the fly from our message, and a WriteHandler. This last parameter represent a function in which we can perform any further action after the normal write to socket as been done and before the connection to the client is closed. A free function with two parameters, a constant reference to a Boost error_code and a size_t, is expected, but bind() is here a helpful friend. I use both parameters, but we could easily get rid of them. More importantly, notice the use of shared_from_this(). Even if we don't want do anything in the WriteHandler, it is vital that the connection is kept alive till the end of writing. Keeping the "this" reference active here does the trick.

Server

In the core of our server there is an ASIO TCP/IP acceptor, that is initialized by the ctor, and used by the Server start() function to accept - asynchronously - a connection from a client on a Connection object.

using ba::ip::tcp;
const int HELLO_PORT = 50013;
// ...

class Server
{
private:
 tcp::acceptor acceptor_;
// ...
public:
 Server(ba::io_context& io) : acceptor_(io, tcp::endpoint(tcp::v4(), HELLO_PORT))
 {
  start();
 }
// ...

The ctor calls the Server private method start(), that creates a new connection on the ASIO I/O context received from the main and stored in the acceptor. The socket owned by the connection is used in the async_accept() call on the acceptor, so that the server would wait for a client connection on it.

void start()
{
 ba::io_context& io = acceptor_.get_executor().context();
 std::shared_ptr<Connection> connection = Connection::create(io);
 tcp::socket& socket = connection->socket();
 acceptor_.async_accept(socket, std::bind(&Server::handle, this, connection, std::placeholders::_1));
}

As second parameter, async_accept() expects an ASIO AcceptHandler, a void free function that gets in input a constant reference to a boost system error code, we bind it to call the following Server private method:

void handle(std::shared_ptr<Connection> connection, const bs::error_code& ec)
{
 if (!ec)
 {
  connection->start();
 }
 start();
}

If the handshake with the client worked fine, we use the connection to write - asynchronously - through the socket. Then we call again Server start(), to prepare the server to accept another connection.

This is more or less all. You could see the full C++ code on GitHub.

I have tested this server using the client described in the previous post. I found interesting adding here and there sleeps and printing to console to better observe how the process work. For more fun I'd suggest you to run more clients and let ASIO I/O control to run on a few threads, as shown in the strand example. The code is based on the official ASIO tutorial, Daytime.3 example.

Go to the full post

Boost ASIO synchronous exchange on TCP/IP

Let's build a simple synchronous client-server application based on the TCP/IP protocol using the Boost ASIO ip tcp socket. The server waits a connection on a port, as it comes, it writes a message and then terminate. The client connects to the server, reads its message from the socket, outputs it, and then it terminates too.

Main

I have put both client and server in a single app, if no parameter is passed to the main, the process acts as server, otherwise as a client.

namespace ba = boost::asio;
// ...
const std::string HOSTNAME{ "localhost" };  // 1
// ...

int main(int argc, char* argv[])
{
 ba::io_context io;  // 1

 if (argc > 1)
  client(io, HOSTNAME);
 else
  server(io);
}

1. Used by the client, when connecting to the server. In this simple example both server and client live on the same machine.
2. An io_context (also known as io_service, but that name is now deprecated) is the first requirement for almost anything in ASIO, so I create it as first thing, then is passed by reference to the client or server function, accordingly to the number of parameters passed to the program.

Server

The following code in the server function throws exceptions deriving from std::exception to signal problems. Being this just an example, we just wrap it in a try-catch and output the relative message.

using ba::ip::tcp;
// ...
const int HELLO_PORT = 50013;
// ...

tcp::acceptor acceptor{ io, tcp::endpoint(tcp::v6(), HELLO_PORT) };  // 1

{   // 2
 tcp::socket socket{ io };  // 3
 std::cout << "Server ready" << std::endl;
 acceptor.accept(socket);  // 4

 std::string message{ "Hello from ASIO" };  // 5
 bs::error_code ec; // 6
 ba::write(socket, ba::buffer(message), ec);  // 7
}

1. Instantiate an object of the ASIO TCP/IP acceptor, so that we can listen for connections. We pass to it the ASIO io_context and a TCP endpoint, created specifying the version of the TCP/IP protocol to use (4 or 6) and the port to be used.
2. Here this block is executed just once. Convert it to a for loop for a more common behavior.
3. Each client connection requires a dedicated ASIO TCP/IP socket to be managed. Here it is created and, at the end of the block, exiting the scope, the socket dtor would clean it up.
4. The server sits down, waiting for a client to be served.
5. When the acceptor has accepted a client on the socket, the server wakes up and builds a message.
6. The ASIO write call in the next line requires an error code, to be set in case something goes wrong. We won't even check it here, usually this is not a good idea.
7. The message is converted to an ASIO buffer, so that it could be consumed by the ASIO write() to be written to the socket.

Client

It mirrors the server, with the part of the acceptor taken by a resolver.

tcp::resolver resolver{ io };
tcp::resolver::results_type endpoints = resolver.resolve(host, HELLO_PORT_STR);  // 1

tcp::socket socket{ io };
ba::connect(socket, endpoints);  // 2

for (;;)  // 3
{
 std::array<char, 4> buf;  // 4
 bs::error_code error;
 size_t len = socket.read_some(ba::buffer(buf), error);  // 5

 if (error == ba::error::eof)  // 6
  break; // Connection closed cleanly by peer
 else if (error)
  throw bs::system_error(error);  // 7

 std::cout.write(buf.data(), len);  // 8
 std::cout << '|';  // 9
}
std::cout << std::endl;

1. The resolver is resolved on the required host and port, returning a list of valid endpoints on them.
2. We call the ASIO connect() on the socket created in the line above, specifying the endpoints resolved in (1).
3. Let's loop until the full message is received from the server.
4. I have set the buffer size to a ridiculously low size, just for see it better at work.
5. read_some() data from the socket in the buffer.
6. If we reach end of file, the connection has been correctly completed.
7. Otherwise we interrupt the operation throwing the Boost system error we got.
8. Use the partial data received from the server.
9. This pipe character is put at the end of each chunk of data read only for seeing the effect on the read message.

Full C++ code is on GitHub. It is based on the Daytime.1 and Daytime.2 example from the official Boost ASIO tutorial.

Go to the full post

HackerRank DP: Coin Change

We are given in input a list of integers, and another integer that represents a total we should reach adding up how many elements from the passed list, each of them used 0+ times, with no upper limit. The name of the problem is slightly misleading, since the list could contain any positive integer, and we could not have almost any expectation them, besides being positive.
I'd say that is a version of the Partitions of Integers problem where a special condition is imposed on the integers that we can use.

You can find and solve this problem on HackerRank, section Cracking the Coding Interview.

First thing, I have taken a non completely trivial example and I studied it on paper.

Given in input [2, 5, 3, 6] and 10, it easy to see how the solution is 5:

2 + 2 + 2 + 2 + 2
5 + 5
2 + 3 + 5
3 + 3 + 2 + 2
2 + 2 + 6

The fact that it is marked as DP, should put me on the way of looking for a Dynamic Programming solution. So I create a table, reasoning how to fill it up coherently. Each column represents the totals I could get, ranging from 0 to the passed value. I have a column for each number passed in the input list, plus the topmost one, that represents the "no value" case.

Cell in position (0, 0) is set to 1, since I could get 0 from no value in just one way. The other values in the first row are set to zero, since I can't get that total having nothing to add up. We don't care much what it is in the other cells, since we are about to get the right value by construction.

We'll move in the usual way for a dynamic programming problem requiring a bidimensional table, row by row, skipping the zeroth one, from top to bottom, moving from left to right. We could have filled the first column before starting the procedure, since it is immediate to see that there is only one way to get a total of zero, whichever number I have at hand. Still, in this case it doesn't help to make the code simpler, so I just keep it in the normal table filling part.

For each cell what I have to do is:

• copy the value from the cell above
• if "cur", the current value associated to the row, is not greater than the current column index, add the value in the cell on the same row but "cur" times to the left

The first point should be clear. Maybe having a new number at hand would give us a new way to get the total, surely it won't reduce the alternatives we have already calculated.
The second point refers to the contribution of the new element. I guess the picture will help understand it.

The arrow pointing down from (0, 0) to (1, 0) means that since having no values leads to have one way to get a sum of zero, this implies that having no value and 2 still gives at least one way to get a sum of zero.
The other arrow pointing down, from (2, 8) to (3, 8) means that having one way to get 8 from no value and [2, 5] implies we still have at least one way to get it from no value and [2, 5, 3].
The arrow pointing left from (1, 0) to (1, 2) means that since we have a way to get zero having a 2, if we add a 2, we have a way to get 2 as a total.
The arrow pointing left from (3, 5) to (3, 8) means that having two ways of getting 5 using [2, 5, 3] implies that we still have two way of getting 5 + 3 = 8. Added with the one coming from the cell above, it explains why we put 3 in this cell.

Following the algorithm, I have written this python code here below:

def solution_full(denominations, total):  # 1
    table = [[0] * (total + 1) for _ in range(len(denominations) + 1)]  # 2
    table[0][0] = 1

    for i in range(1, len(denominations) + 1):  # 3
        for j in range(total+1):
            table[i][j] += table[i - 1][j]  # 4
            cur = denominations[i-1]
            if cur <= j:
                table[i][j] += table[i][j-cur]  # 5

    return table[-1][-1]  # 6

1. In the example, denominations is [2, 5, 3, 6] and total is 10.
2. Table has total + 1 columns and a row for each denomination, plus one. Its values are all set to zero, but the left-topmost one, set to 1.
3. Loop on all the "real" cells, meaning that I skip just the first row. I move in the usual way. Left to right, from the upper row downward.
4. The current cell value is initialized copying the value from the immediate upper one.
5. If there are enough cell to the left, go get the value of the one found shifting for the value of the current denomination, and add it to the one calculated in the previous step.
6. Return the value in the bottom right cell, that represents our solution.

How to save some memory

Writing the code, I have seen how there is no use in keeping all the rows. The only point where I use the values in the rows above the current one is in (4), and there I use just the value in the cell immediately above the current one. So I refactored the solution in this way:

def solution(denominations, total):
    cache = [0] * (total + 1)  # 1
    cache[0] = 1

    for denomination in denominations:  # 2
        for j in range(denomination, total+1):  # 3
            cache[j] += cache[j-denomination]
    return cache[-1]

1. The memoization here is done just in one row. Initialized as in the previous version.
2. Since I don't care anymore of the row index, I can just work directly on the denominations.
3. Instead of checking explicitly for the column index, I can start the internal loop from the first good position.

I pushed my python script with both solutions and a slim test case to GitHub.

Go to the full post

Boost ASIO Strand example

In the previous posts, we used ASIO keeping away from any possible multithreading issue, with the noticeable exception of
Asynchronous wait on timer, part two, where a job was executed concurrently to the ASIO handler in another thread, using of a mutex, a lock, and an atomic int to let it work as expected.

With ASIO we can follow a different approach, based on its strand concept, avoiding explicit synchronization.

The point is that we won't run the competing functions directly, but we will post the calls to a strand object, that would ensure they will be executed in a sequential way. Just be sure you use the same strand object.

We have a class, Printer, with two private methods, print1() and print2(), that uses the same member variable, count_, and printing something both to cout.

We post the two functions a first time in the class constructor, asking our strand object to run them.

namespace ba = boost::asio;
// ...

class Printer
{
// ...

ba::io_context::strand strand_;
int count_;


Printer(ba::io_context& io, int count) : strand_(io), count_(count)
{
 strand_.post(std::bind(&Printer::print1, this));
 strand_.post(std::bind(&Printer::print2, this));
}

The functions would post themselves again on the same strand, until some condition is satisfied.

void print1()
{
 if (count_ > 0)
 {
  print("one");
  --count_;

  strand_.post(std::bind(&Printer::print1, this));
 }
}

And this is more or less the full story for the Printer class. No need of synchronization, we rely on the strand to have them executed sequentially.

We still have to let ASIO run on two threads, and this is done by calling the run() method from io_context from two different threads. This is kind of interesting on its own, because we bump in an subtle problem due on how std::bind() is implemented.

The official Boost ASIO tutorial suggests to use the Boost implementation:

std::thread thread(boost::bind(&ba::io_context::run, &io));

It works fine, end of the story, one would say. But let see what it happens when using the standard bind implementation:

std::thread thread(std::bind(&ba::io_context::run, &io));
// error C2672: 'std::bind': no matching overloaded function found
// error C2783: 'std::_Binder<std::_Unforced,_Fx,_Types...> std::bind(_Fx &&,_Types &&...)': could not deduce template argument for '_Fx'

Damn it. It tries to be smarter than Boost, and in this peculiar case it doesn't work. The problem is that there are two run() functions in io_context, and bind() doesn't know which one to pick up.

A simple solution would be compile our code for a "clean" ASIO version, getting rid of the deprecated parts, as is the case of the run() overload.

If we can't do that, we should provide an extra help to bind, so that it could understand correctly the function type. An explicit cast would do:

auto run = static_cast<ba::io_context::count_type(ba::io_service::*)()>(&ba::io_context::run);
std::thread thread(std::bind(run, &io));

I have taken the address of the member function run from boost::asio::io_context (also known as io_service, but now it is deprecated too) and I explicitly casted it to its actual type.

Can we get the same result in a more readable way? Well, using a lambda could be an idea.

std::thread thread([&io] { io.run(); });

You could get my full C++ code from GitHub. I based it on the Timer.5 example from the official Boost ASIO tutorial.

Go to the full post

Boost ASIO using a member function as handler

In the fourth step of the official Boost ASIO tutorial, a class method in used as handler instead of the free function. See the previous post for my version that uses free function - or a lambda function. Here I present my refactored code that uses less Boost and more C++ standard stuff.

All the relevant code is now in the class Printer, so the function in the main thread gets much simpler:

Printer printer(io);
io.run();

Where io is a boost::asio::io_context object - previously known as io_service.

Here is the Printer class:

class Printer
{
private:
 ba::system_timer timer_;
 int count_;
public:
 Printer(ba::io_context& io) : timer_(io, sc::milliseconds(500)), count_(0)  // 1
 {
  timer_.async_wait(std::bind(&Printer::print, this));
 }

 ~Printer()  // 2
 {
  std::cout << "final count is " << count_ << std::endl;
 }

 void print()  // 3
 {
  if (count_ < 5)
  {
   std::cout << count_++ << ' ';
   timer_.expires_at(timer_.expiry() + sc::milliseconds(500));
   timer_.async_wait(std::bind(&Printer::print, this));
  }
 }
};

1. The constructor initializes the member variables and then asks ASIO to set an asychronous wait on the timer, passing as handler the member function print() of this object.
2. The dtor will print the final counter value.
3. Same old print() function, but now is a method of Printer, so it could freely access its data members.

This approach looks cleaner of the free function one. Still, we need to keep in our mind the fact that timer_, count_ (and cout) are seen by two different threads, and this could lead to concurrency problems, that could be solved using mutexes and locks, as I have shown in a previous spoilery post, or using the ASIO concept of strand, as we'll see in the next post.

Go to the full post

Boost ASIO passing parameters to handler

I have sort of spoiled the argument of this post in the previous one, where the focus was on telling ASIO to asynchronously run a function when a timer expires, but I couldn't keep from presenting also a scenario where multiple threads synchronize on a flag and access concurrently a shared resource. Let's do a step beyond, and analyze a simpler case, where the function we want ASIO to run at the timer expiration just has to access a variable defined in the main thread.


Plain function

The point raised in the official Boost ASIO tutorial is having a simple function passed to ASIO so that after it is called the first time, on timer expirations, it resets the timer on itself, keeping track on the times it has been invoked in a counter defined in the main thread. Here is my version of it, with some minor variation.

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

// ...

void print(ba::system_timer* pTimer, int* pCount) {  // 1
 if (*pCount < 5)  // 2
 {
  std::cout << (*pCount)++ << ' ';
  pTimer->expires_at(pTimer->expiry() + sc::milliseconds(500));  // 3
  pTimer->async_wait(std::bind(print, pTimer, pCount));  // 4
 }
}

1. I use system_timer, based on the standard chrono::system_clock, instead of the boost::posix_time based deadline_timer.
2. The check on the counter is used to avoid an infinite series of calls.
3. Reset the timer expiration to half a second in the future. To get the current expiration time I use expiry() instead of the deprecated overaload with no parameters of expires_at().
4. Reset an asychronous wait on the timer, passing as parameter the function itself.

Notice how the standard bind() function is used to bind the print() function to the handler expected by async_wait() on the timer. This makes possible to elide the reference to boost::system::error_code, that we decided not to use here, and add instead the two parameters we actually need.

In the main thread we start the asychronous wait on the ASIO managed timer in this way:

// ...

int count = 0;
ba::system_timer timer(io, sc::milliseconds(500));  // 1

timer.async_wait(std::bind(print, &timer, &count));  // 2
io.run();  // 3

1. io is a boost::asio::io_context object - previously known as io_service.
2. Notice that both count and timer are shared between the main thread and the one owned by ASIO in which is going to be executed print().
3. However, nothing happens in the main thread until ASIO ends its run().

The code is so simple that we can guarantee it works fine. However, when between (2) and (3), another thread is spawned, with something involving io and timer (and cout, by the way) we should be ready to redesign the code for ensure thread safety.

Same, with lambda

Usually, I would feel more at ease putting the code above in a class, as I did in the previous post. Still, one could argue that in a simple case like this one, that could be kind of an overkill. Well, in this case I would probably go for a lambda implementation, that at least would keep the code close, making less probable forgetting something in case of future refactoring.

Since I could capture count and timer instead of passing them to the lambda, there is no need of custom binding here. However, the original function needs to use its name in its body, and this is something that C++ lambdas are not allowed to do. There are a couple of workaround available, I have chosen to save it as a local std::function variable, and then pass it to async_wait() like this:

// ...
std::function<void(const bs::error_code&)> print = [&](const bs::error_code&) {
 if (count < 5)
 {
  std::cout << count++ << ' ';
  timer.expires_at(timer.expiry() + sc::milliseconds(500));
  timer.async_wait(print);
 }
};

timer.async_wait(print);

I have pushed the two new files, free function and lambda example, on GitHub.

Go to the full post

Boost ASIO asynchronous wait on timer

Having seen how ASIO takes care of resources, now we are ready for something a bit more spicy, setting up an asynchronous wait.

Plain example

Firstly, I have faithfully followed the Timer.2 Boost ASIO tutorial, only using standard C++ construct instead of the Boost counterpart.

We want ASIO to run in another thread the following simple function, that just does some output, and we want it to be done after a certain delay.

namespace bs = boost::system;

// ...

void hello(const bs::error_code& ec)  // 1
{
 std::cout << "delayed hello [" << ec.value() << "] " << std::flush;
}

1. If ASIO completes the wait on the timer correctly, it passes an error code with value zero.

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

// ...

void timer2(ba::io_context& io)  // 1
{
 std::cout << "2) Starting ... " << std::flush;

 ba::system_timer timer{ io, sc::seconds(1) };  // 2
 timer.async_wait(hello);
 std::cout << "hello " << std::flush;

 io.run();  // 3
 std::cout << "done" << std::endl;
}

1. The old io_service is now deprecated, get used to see io_context in its place.
2. Create a system timer on ASIO, setting its expire time to one second. Then start a non-blocking wait on it, passing the address of above defined hello() function as parameter.
3. After doing some job on the current thread, here just a print on the output console, we want to wait for the termiantion of the other thread, controlled by ASIO. So we call its run() method, blocking until we get back the control.

More action

Let's add some meat to the above example. Say that we want to run a loop in the main thread until a timeout expires.

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

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

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

 void timeout()  // 5
 {
  expired_ = true;
  log("Timeout!\n");
 }

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

   log(os.str().c_str());
   std::this_thread::sleep_for(sc::milliseconds(300));
  }
 }
};

1. The objects of this class are inherently non-copyable. So I remove copy ctor and assignment operator from its interface.
2. The output console is shared between two threads. This mutex is going to rule its access.
3. The threads are going to synchronize on a boolean. At startup it is set to false. When the timer expires set it to true. The main loop runs until it sees an expiration. Being just one thread setting it, while the other only reading it, an atomic boolean would be enough to ensure communication between threads.
4. Lock the mutex to acquire exclusive access to the shared resource.
5. This method is going to be called by the timer on expiration.
6. The loop I want to run until timer expiration.

Let's see how I used this class.

void timer2a(ba::io_context& io)
{
 std::cout << "2a) Starting ... " << std::flush;

 ba::system_timer timer(io, sc::seconds(1));

 MyJob job;
 timer.async_wait([&job](const bs::error_code&) { job.timeout(); });  // 1
 std::thread thread(std::ref(job));  // 2

 io.run();
 thread.join();
}

1. The async_wait() method of the timer is fed with a lambda that capture by reference the instance of the class MyJob that I created in the previous line. In the lambda body we call the job timeout() method. The result is that the expiration flag is set when the timeout expires. Here I ignore the ASIO error code, but it would be easy to take notice of it, when required.
2. Create a new thread to run the job loop.

One thing more. I want to run the two examples, one after the other, using the same ASIO io_context object. But the first one run() it, putting it in the stopped status. No problem, I just have to remember to reset it. That is what I do in the main:

timer2(io);
assert(io.stopped());

io.reset();
timer2a(io);

I have pushed both C++ source files on GitHub, the simpler, and the more interesting one.

Go to the full post

Boost ASIO Basic Skills

In the latest years there have been a few changes in the ASIO library, and I finally decided to review the post I have produced on it. I have downloaded the (currently) latest Boost libraries, version 1.66 (please have a look the Boost Revision History for details) and I am about to use it on a WIndows box with Visual Studio 2017 as IDE with the current (March 2018) Visual C++ programming language implementation.

In this and the next few posts, I plan to follow the Boost ASIO tutorial, basic skills section.

Notice that a few well established ASIO elements are now marked as deprecated. Define BOOST_ASIO_NO_DEPRECATED among the compiling option to get rid of them. I kept a more conservative approach, however, simply avoiding deprecations whenever I saw them.

First victim is a big one, io_service. Luckily it looks like the solution is just using io_context instead.

This led to the main change in the code for my version of the Timer.1 tutorial.

Its point is using ASIO to set a synchronous timer to block the current thread execution for a while. This is not very interesting, but shows the common pattern we are about to use to let ASIO know about a service we want it to manage on our behalf.

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

// ...

void timer1(ba::io_context& io)
{
 std::cout << "1) Starting ... " << std::flush;

 ba::system_timer timer{ io, sc::seconds(1) };  // 1
 timer.wait();  // 2

 std::cout << "done!" << std::endl;
}

1. I am creating an ASIO service, system timer, setting its delay to one second.
2. I consume the service synchronously, blocking the current thread execution.

I have used here system_timer, equivalent to the deadline_timer used in the official example, differing from it that is based on the standard C++ chrono library, instead of the boost equivalent one. If you need a steady clock, use steady_timer.

I have pushed the reviewed code for this example on GitHub. I have added a main in an another file, that would run all the examples in this section.

Go to the full post