Hexagonal Tiles

In this post I will explain how to solve the exercise Hexagonal Tiles [link], using the concept of Dynamic Programming.

This exercise is quite simple, and it’s a good start for those who don’t have familiarity with Dynamic Programming yet.

Click in the link below to see the post.

The concept of Dynamic Programming can be explained in several ways, and I will use one of them in here.
I will divide the exercise in main problem, and sub-problem:

  • Main problem is the goal problem, the one we want to know the answer.
  • Sub-problem is a problem similar to the main problem. It’s not the goal problem, but its resolution will help to solve the main problem.

With this definition in mind, let’s see the exercise: we want to find out the number of different paths, from the tile number 0 (the one with the smiling face), and ending at the tile N.

Here the main problem is obvious: Number of paths, starting at the tile 0, and ending at the tile N.

But what about the sub-problem?
According to the definition, it will be similar to the main problem.
Let’s try this: Number of paths, starting at the tile K, and ending at the tile N.

It’s similar to the main problem, and since K is different from 0, it’s not the goal problem.

Ok, once the main problem and the sub-problems are defined, how is a sub-problem supposed to help in the resolution of the main problem, or even in the resolution of another sub-problem?

Let’s visualize the problem. If we are at the tile K, where can we walk?

imagem2

Ok, if we are at the tile K, we have two paths: We can go to the tile K+1, and follow some path until the tile N; or we can go to the tile K+2, and follow some path until the tile N.

If, for instance, we go to the tile K+1. Now, where can we walk?

imagem3

Notice the similarity?

All the sub-problems are equal, and the only thing that changes is the value of K. And the best: they are all related!
If we solve one, we are helping solving another, and that consequently leads us to the resolution of the main problem, once it’s similar to the sub-problems,¬†as well as it’s related to them.

Let’s think about a formula: be “np” equal to “number of paths”, we have:
np[K] = np[K+1] + np[K+2].

To find out np[K], we need to find out np[K+1] and np[K+2]. To find out np[K+1], we need to find out np[K+2] and np[K+3]. When does it end?
I present you something called base case.
Base case is a particular sub-problem so ridiculously easy that we don’t need other sub-problems to solve it. You can solve it by yourself.

For example, if we are at the tile N, how many paths are there until the tile N? Well, just 1, because we are already there.
And if we are at the tile N-1, how many paths are there until the tile N? Well, just 1, because you just have to walk ahead.

Now we just have to solve the sub-problems, from right to left, and we will get to the main problem. Here is the code in C++:

// number of tiles
int N;
scanf("%d", &N);

// array with the answer to the sub-problems
int np[N+1];

// base cases
np[N] = 1;
np[N-1] = 1;

// sub-problems
for(int K=N-2; K>=0; K--) {
     np[K] = np[K+1] + np[K+2];
}
// the main problem is solved when K is equal to 0, in the loop above

// answer
printf("%d\n", np[0]);

Any doubt, suggestion or review, let me know below.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.