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

Partitioning Souvenirs

Given a list of integers, we want to know if there is a way to split it evenly in three parts, so that the sum of each part is the same than the other ones.

Problem given in week six of the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego.

This 3-partition problem is not too different from the classic 2-partition one, for which I have described the well known dynamic programming solution in the previous post. As before, we build a table where the rows represents the sums we want to get and the columns the elements in the collection we are about to consider.
However, we have to change a bit the meaning of the value that we push in each cell. This time we check two of the three tentative subcollections, and we want to keep track of how many of them could have as sum the row index, given the elements of the input list available in that column.

Consider as example this input:

[3, 1, 1, 2, 2]

We are looking for three subcollections having all a sum of three. The table is having six columns and four rows, including a first dummy one. We initialize all its cells to zero, and we loop on all the "real" cells applying rules close to the ones we have seen for the 2-partition problem, with slight variations.
(a) If the column element matches the row index, I increase the value of the left-hand cell, up to reach 2.
(b) If there is not a match, but the column element added to the previous one matches it, I still increase the value of the left-hand cell, up to reach 2.
(c) Otherwise, I copy the value in the left-hand cell to the current one.
The result should be reflected by this table:

And the answer to the original question is yes only if the bottom-left value in the table is two.

Here is my python code to implement this algorithm.

def solution(values):
    total = sum(values)
    if len(values) < 3 or total % 3:  # 1
        return False
    third = total // 3
    table = [[0] * (len(values) + 1) for _ in range(third + 1)]  # 2

    for i in range(1, third + 1):
        for j in range(1, len(values) + 1):  # 3
            ii = i - values[j - 1]  # 4
            if values[j - 1] == i or (ii > 0 and table[ii][j - 1]):  # 5
                table[i][j] = 1 if table[i][j - 1] == 0 else 2
            else:
                table[i][j] = table[i][j - 1]  # 6

    return True if table[-1][-1] == 2 else False

1. If dividing the sum of values by three I get a remainder, or if there are less than three elements in the list, for sure there is no way of 3-partition my list.
2. Build the table as discussed above. Note the zero as default value, even in the dummy top row - it is not formally correct, but those values are not used anywhere.
3. Loop on all the "real" cells.
4. Precalculate the row for the (b) check described above.
5. The first part of the condition is the (a) check above. If it fails, we pass to the second part, using the row calculate in (4). If one of the two conditions is true, the value of the current cell is increased up to 2.
6. Vanilla case, moving to the right we keep the value already calculate for the previous cell.

It looks easy, once one see it, doesn't it?

Actually, a tad too easy, as Shuai Zhao pointed out - see below in the comments. The problem is that the (b) check, as described above, is too simple. Before using a value I have to ensure it has not already used on the same line. Things are getting complicated, better to explain them in another post.

I pushed my python code and a few test cases to GitHub. The latest version is the patched code, working also for the Shuai test. Get back in the history if you want to see the solution described here.

Go to the full post

2-partition problem

Having a list of integers, we want to know if we can split it evenly in two parts.

There is a well known, elegant and relatively fast dynamic programming solution to this problem.

Say that this is the list

[3, 1, 1, 2, 2, 1]

Being the sum of its elements ten, we'll have a positive answer to the problem if we could find a subcollection with a sum of five.

To check it, we build a table having rows from zero to the sum of the subcollection we are looking for - five in this case. Actually, the zeroth row is pretty useless here, I keep it just because it makes indices less confusing in the code. The columns represents the partial sum of elements in the list we have in input, column zero is for the empty collection, one contains just the first element (3 in the example), column two the first two items (3 and 1 here), up to the last one that keep all.

The content in each cell is the answer to the question: is there a combination of elements in the subcollection specified by the column that have a sum specified by the row?

So, for instance, table[2][3] means: could I get 2 as a sum from [3, 1, 1]? The answer is yes, because of latter two elements.

The bottom-right cell in the table is the answer for the original problem.

Let's construct the table. Whatever I put in the topmost row is alright, since I won't use it in any way. They would represent the answer to the question if I could get a sum zero from a collection that could be empty (leftmost cell) up to including all the element in the original input (rightmost cell). Logically, we should put a True inside each of them but, since we don't care, I leave instead a bit misleading False. Forgive me, but this let me initialize with more ease the table, considering that each first cell in any row (but the zeroth one) should be initialized with False, since it is impossible having a sum different from zero from an empty collection.

Now let's scan all the cell in the table, from (1, 1) to the bottom-right one, moving from left to right, row by row.
If the currently added element in the list has the same value of the row index (that is, the total we are looking for), we can put a True in it.
If the cell on the immediate left contains a True, we can, again, safely put a True in it. Adding an element to the collection won't change the positive answer we already get.
If the first two checks don't hold, I try to get the total adding up the current value to the previous one. If so, bang, True again.

At the end of looping, we should get a table like the one shown here below.

(a) The cell (1, 2) is set to True because the column represent the subcollection {3,1}, having as latest element the row index.
(b) The cell (1, 4) is True because (1, 3) is True
(c) The cell (4, 2) is True because of cell (3, 1), checked because being the left adjacent column, moving up 1 (from the latest element in current subcollection {3,1}).

Checking the bottom-right cell we have a True, so the answer to our original question is yes.

Here is my python implementation of this algorithm:

def solution(values):
    total = sum(values)  # 1
    if total % 2:
        return False

    half = total // 2
    table = [[False] * (len(values) + 1) for _ in range(half + 1)]  # 2

    for i in range(1, half + 1):
        for j in range(1, len(values) + 1):  # 3
            if values[j-1] == i or table[i][j-1]:  # 4
                table[i][j] = True
            else:  # 5
                ii = i-values[j-1]
                if ii > 0 and table[ii][j-1]:
                    table[i][j] = True

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

1. If the sum of values is not an even number, we already know that the list can't be split evenly.
2. Build the table as described above. Don't pay attention to the topmost row, it's just a dummy.
3. Loop on all the "real" cell, skipping the leftmost ones, that are left initialized to False.
4. See above, case (a) and (b) as described and visualized in the picture
5. This code implements the case (c). I get the the tentative row index in ii. If the relative cell on the left adjacent column is available and it is set to True, the current cell is set to True too.
6. Get the solution to the problem.

I pushed my python code and a few test cases on GitHub.

Go to the full post

Other Dynamic Programming problems

Sixth and last week of the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, again on Dynamic Programming. Just three problems, fully described in this pdf.

The first one, named "Maximum Amount of Gold", states that you have a bag of given capacity, and you see n gold bars of (possibly) different weights. Push as much gold as you can in the bag.

It is easy to say that it is a variation on the classic 0/1 knapsack problem. Here the bars have all the same unitary value, so we just need to know their weight to build our solution. Not much sweat to solve it, anyway I pushed to GitHub first a python script to solve the generic problem, then one tailored on the specific requirements of the problem.

Much more challenging the other two problems. "Partitioning Souvenirs" is a 3-Partition problem. Before solving it, I practiced with the more common 2-partition version. "Maximizing the Value of an Arithmetic Expression" is well described, step by step, in the course, and I guess that I solved it easily only because of this intensive training. You could see my python implementation on GitHub.

Go to the full post

Longest Common Subsequence of Three Sequences

And finally, the last one of this group of Dynamic Programming problems. Actually, from the algorithmic point of view this is the less interesting one, being just a variation on the previous one. Now we have in input three sequences instead of two, still we have to get the longest subsequence among them.

The interest here is all in extending the algorithm to work with a three-dimensional cache. Basically just an implementation issue, that each programming language could solve in its own way.

Here is how I did it in python:

def solution_dp(a, b, c):
    cube = []
    for m in range(len(c) + 1):  # 1
        sheet = [[0] * (len(b) + 1)]
        for n in range(1, len(a) + 1):
            sheet.append([0] * (len(b) + 1))
        cube.append(sheet)

    for i in range(1, len(cube)):
        for j in range(1, len(cube[0])):
            for k in range(1, len(cube[0][0])):
                if a[j - 1] == b[k - 1] == c[i - 1]:  # 2
                    cube[i][j][k] = cube[i - 1][j - 1][k - 1] + 1
                else:
                    cube[i][j][k] = max(cube[i - 1][j][k], cube[i][j - 1][k], cube[i][j][k - 1])

    return cube[-1][-1][-1]

1. If you compare this code with the one for the 2-sequences problem, you would see how the difference is all in this extra for-loop. Now the cache is a three dimensional matrix (actually, it is not a cube but a parallelepiped, you could guess why I used a wrong name here).
2. The comparisons get now three way. Luckily, python helps us keeping them readable.

Once you manage correctly the three-level loop, the job is done.

I have pushed the complete python script and its test case to GitHub.

Go to the full post

Longest Common Subsequence of Two Sequences

Close to the previous problem, where we had to compute the minimum edit distance between two strings, here we have to get the maximum number of common elements in the same order between two sequences.

The similarity drives us to look again for a Dynamic Programming solution (adding up to the hint that these problems are in the same lot).

Here is my python solution:

def solution_dp(lhs, rhs):
    table = [[0] * (len(rhs) + 1)]  # 1
    for _ in range(1, len(lhs) + 1):
        table.append([0] * (len(rhs) + 1))

    for i in range(1, len(table)):
        for j in range(1, len(table[0])):  # 2
            if lhs[i - 1] == rhs[j - 1]:
                table[i][j] = table[i-1][j-1] + 1  # 3
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])  # 4
    return table[-1][-1]

1. The cache is created as in the previous problem, bidimensional, with extra dummy row and column to keep the code simple.
2. Again, we loop on all the "real" cells in the cache, from left to right, up to down.
3. The code change in the algorithm. If the corresponding elements in the input sequences match, we put as current value the counter stored in the top-left cell, increased it by one.
4. If it is a mismatch, we don't increase anything, just get the bigger value coming from the two possible alternatives.

And that's all. Richard Bellman, who found out this algorithm, was a genius.

Python script and testcase pushed to GitHub.

Go to the full post

Computing the Edit Distance Between Two Strings

Given two strings, we should compute their edit distance. It is a well know problem, commonly solved by Dynamic Programming.

As we should expect, the idea is very close to the one seen in the previous problem, with the noticeable difference that here we are working on two lists, so our cache is going to be a bidimensional matrix and the complexity of the algorithm is moving to the O(n * m) realm, being n and m the sizes of the two strings in input.

def solution_dp(lhs, rhs):
    table = [[x for x in range(len(rhs) + 1)]]  # 1
    for k in range(1, len(lhs) + 1):
        table.append([k] + [0] * len(rhs))

    for i in range(1, len(table)):
        for j in range(1, len(table[0])):  # 2
            if lhs[i - 1] == rhs[j - 1]:
                table[i][j] = table[i-1][j-1]  # 3
            else:
                table[i][j] = min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1]) + 1  # 4

    return table[-1][-1]  # 5

1. This is our cache. Instead of having a single dummy cell, here we have both zeroth row and column just filled with zeroes and not touched anymore. Again, not strictly a necessity, still the code is much more readable in this way.
2. Let's loop on all "real" elements in the matrix.
3. If the corresponding characters in the strings are the same, we have a match. Meaning the edit distance won't change, so we just copy in the current cell the value of the one on the left top corner.
4. Otherwise we have seen a change. Since we are looking to the minimal distance, we get the lowest value in the top / left cells, and increase it by one.
5. At the end of the loop, the bottom-right cell contains the result.

Incredible simple, isn't it?

Python code and testcase on GitHub.

Go to the full post

Primitive Calculator

We always start from 1, and we get the positive integer we should get to. We could apply just three operations, multiply by 2, by 3, or adding one. Which is the minimum number of operations that gives us the expected result? Which sequence will be generated?

This problem is close to the previous one, about changing money. After all, are all part of the same lot about Dynamic Programming.

The first part of the code follows almost naturally from looking at the money changer:

cache = [0] * (target + 1)  # 1
for i in range(1, len(cache)):  # 2
    cache[i] = cache[i-1] + 1
    if i % 2 == 0:
        cache[i] = min(cache[i], cache[i // 2] + 1)
    if i % 3 == 0:
        cache[i] = min(cache[i], cache[i // 3] + 1)

1. Reserve a cache for all the intermediate results, again, a dummy zeroth element would make our code simpler.
2. Loop an all the elements, checking for all the possible alternatives. The minimum local solution would be kept an used to the next steps.

Now in the last element of the cache we have the answer to the first question. To get the second answer we need to backtrack the cache, identify each choice we did at each step.

result = [1] * cache[-1]  # 1
for i in range(1, cache[-1]):  # 2
    result[-i] = target  # 3
    if cache[target-1] == cache[target] - 1:  # 4
        target -= 1
    elif target % 2 == 0 and (cache[target // 2] == cache[target] - 1):  # 5
        target //= 2
    else:  # 6 # target % 3 == 0 and (cache[target // 3] == cache[target] - 1):
        target //= 3
return result

1. This is the list we are going to return. We know its size, stored in the last element of the cache, since I have to provide an initialization value, I use 1, the right value for its leftmost element.
2. I am going to set the result list, each value but the leftmost one, already correctly set.
3. I know the rightmost value would be the target passed by the user.
4. If the previous element in the cache is the current value of the cache minus one, I got there adding one, so I here apply the inverse operator, decreasing target by one
5. If the current target is divisible by 2, and the cache at position current divided by two is actually the value of the current element of the cache minus one, we got there multiplying by two. So I apply the inverse to backtrace.
6. Otherwise we got there multiplying by three. I could have written the full elif statement as shown in the comment. The point is that by construction we have only three choices to get to an element in the cache and this must be the third one.

Python code and testcase on GitHub.

Go to the full post