MBEEWALK — Bee Walk — SPOJ
This problem can be found on spoj here. Problem statement goes like this: A bee larva living in a hexagonal cell of a large honey comb decides to creep for a walk. In each “step” the larva may move into any of the six adjacent cells and after n steps, it is to end up in its original cell. Your program has to compute, for a given n, the number of different such larva walks.
BRUTE FORCE Algorithm:
At every block, we can move to six adjacent boxes. starting from center we enumerate(visit all) possibilities, so at each step we can pick any one of 6 adjacent boxes and will see if we will reach the starting point after n moves, if it does we add 1 to the answer. Each block can be (encoded)numbered using natural numbers or can use the method given in the picture below. This algorithm is not good because it takes O(6^n) time(basically somewhere around 6^n steps has to be evaluated to get the answers). for example, if n = 8, number of steps to evaluate will be 1679616. It is pretty slow.
DYNAMIC PROGRAMMING Method:
Bee can move from one place to any of the 6 adjacent hexagon blocks in one step, which can be rephrase the sentence in favor of our solution, we can reach a hexagonal block from 6 adjacent blocks in one step.
So, now the problem is uniquely naming the hexagonal blocks. Though we can’t straight away find orthogonal axis(like x,y in our math textbooks), the representation given above in the image will work for us.
Think of the horizontal axis as x-axis and axis through (0,0) at an angle of 120 degrees, the y-axis. Then we can easily name all the boxes uniquely.
Now, the problem becomes simple. think of the simplest situation, to reach (0,0) from some other block in a single step, the bee have to be at one of these blocks [(0,1) , (0,-1) , (1,0), (-1,0), (1,-1), (-1,1)] the previous step. So in a similar way to move to some (i,j) coordinate in k steps we have to be at one of the [(i,j-1), (i,j+1), (i-1,j), (i+1,j), (i-1,j+1), (i+1,j-1)] after k-1 steps. so the number of ways to reach (i,j) in k steps from starting position is some of number of ways you can reach to aforementioned six places in k-1 steps.
We can use array of arrays of arrays to store the previously computed values, so that we can use them later. and as arrays doesn’t have negative indices(we need to name all boxes according to coordinate system) we can make each array of size 2n at the minimum where n is number of steps bee is going to cover.
we start from the center with zero steps, i.e, way[0][n/2][n/2] and iterate to fill all the values, and return way[n][n/2][n/2] at the end, because bee reaches to the center(where it has started it’s journey) in n steps.
This is better than Brute Force method because there will be 3 for loops of size 2n, so worst time case is O(n³) which is better than O(6^n).
revert back if you have any doubts or found any mistakes. You can find cpp code of the same problem at this link, can find jupyter notebook and .py file for the same problem if you want it in python at this repository
If you have time, read this related post https://medium.com/@sudheernaidu53/the-josephus-problem-36cbf94f3a64
