Tower Hopper problem recursive approach

Question

The Tower Hopper problem gives us an array of values representing heights that express how far we can jump from a certain tower, and asks whether there's a way to get from tower[0] (0 indexed) to outside of the array.

For ex, if we have towers = [4, 2, 0, 0, 2, 0], we can jump from towers[0] to towers[4] and then outside of the bounds of the array. Or we could jump from towers[0] to towers[1] to towers[4] and then out of the array. But if we had towers = [4, 2, 0, 0, 1, 0], there would be no way to hop out of the array and we should return False.

I wrote a recursive function that starts from the last array index.

I'm concerned that the way I wrote the function is not the most efficient. It seems to work but I'm thinking I might not have to pass in that many arguments. I very much welcome any other kind of criticism (style, syntax, design...).

I was also wondering (but maybe I should post this as another question) how to turn this into a dynamic programming format. Hints on how to do that (rather than a straight up solution) would be greatly appreciated.

int main(int argc, char const *argv[])
{

    int num_towers = 6;

    int towers[6] = {5, 4, 3, 3, 1, 0};

    printf("These towers are %s\n", is_hoppable(towers, num_towers - 1, num_towers) ? "hoppable" : "NOT hoppable");

    return 0;
}




int is_hoppable(int* towers, int jumpTower, int targetTower){   

    if (jumpTower == 0){
        if (jumpTower + towers[jumpTower] >= targetTower)
            return 1;
        else 
            return 0;
    }

    if (jumpTower + towers[jumpTower] >= targetTower)
        return is_hoppable(towers, jumpTower - 1, jumpTower);
    else 
        return is_hoppable(towers, jumpTower - 1, targetTower);

}

Answer 1

The recursion stop condition looks clumsy. First, inside the if clause you already know that jumpTower == 0. Second,

    if (condition)
        return 1;
    else
        return 0;

is a long way to say return condition. Suggested rewrite:

    if (jumpTower == 0) {
        return towers[0] >= targetTower;
    }

---

The two recursive calls differ only by the last parameter. This strongly hints to make the function tail-recursive:

    if (jumpTower + towers[jumpTower >= targetTower) {
       targetTower = jumpTower;
    }
    jumpTower -= 1;
    return is_hoppable(towers, jumpTower, targetTower);

and mechanically eliminate tail recursion (sorry for another shameless self promotion):

    while (jumpTower > 0) {
        if (jumpTower + towers[jumpTower >= targetTower) {
           targetTower = jumpTower;
        }
        jumpTower -= 1;
    }
    return towers[0] >= targetTower;

Now the problem is reduced to a single loop. It doesn't look right. But don't blame me. It is a mechanical rewrite (much like a C compiler would do), so if there's a problem here, there must be a problem in the original code.

---

The printf line is too long to my taste. I was almost sure that you print int as %s. Then I scrolled.

---

Returning bool rather than int would clarify intentions.

Answer 2

Not much significant issues left to add after @vnp good review.

1. Respect the presentation width. This should be easy to accommodate if code is auto formatted. Time spent manually formatting is inefficient.

       printf("These towers are %s\n", is_hoppable(towers, num_towers - 1, num_towers) ? "hoppable" : "NOT hoppable");
   

   • could be

     printf("These towers are %s\n",
         is_hoppable(towers, num_towers - 1, num_towers) ?
         "hoppable" : "NOT hoppable");
     

2. I found the vertical spacing excessive, yet with such style issues, follow your group's coding standard.

3. Use void instead of int argc, char const *argv[] or use (void)argc; and (void)argv; @user3629249 to clearly indicate their intended non-used.

4. As towers in is_hoppable(int* towers, ...) does not alter the referenced data, use const. This adds clarity and breadth to code's functionality and can allow certain optimizations a compiler may not see.

   int is_hoppable(const int* towers, int jumpTower, int targetTower) {
   

5. Add declaration of is_hoppable() before first use.

   int is_hoppable(const int* towers, int jumpTower, int targetTower);
   

6. Rather than an explicit 6, consider letting code handle that math.

   int main(void) {
     const int towers[] = { 5, 4, 3, 3, 1, 0 };
     int num_towers = sizeof towers/sizeof towers[0];
   
     printf("These towers are %s\n",
         is_hoppable(towers, num_towers - 1, num_towers) ?
             "hoppable" : "NOT hoppable");
     return 0;
   }
   

Answer 3

EDIT: My review: Regarding your question - firstly, you cannot jump from towers(1) to towers(4). towers(1) = 2, so you can only reach 1+2 = towers(3).

So that's a basic misunderstanding of the problem.

But - your code actually works, and its very efficient. Basically O(n). Also, with vnp's changes, it's even more efficient (albeit not recursive) (but still O(n)).

I think Dynamic Programming won't help you so much as you already came to a very efficient solution. Here's how it did help me to improve my first recursive solution which was really not efficient O(2^n) to a O(n^2):

---

ORIGINAL:

Here's my solutions (in C#, can be "easily" adapted to C):

I started with a recursive solution, that breaks the big problem to smaller ones (basically defers the decision on complicated matters until the simpler matters are solved) - there is basically 2 base cases - either the tower is bigger than remaining size (return true) or it's 0 (return false). For the rest you have to recurse. The loop starts from the farthest you can go from the first tower (recurse for that tower etc.), and then goes down... up to making just 1 step:

    public static bool IsHoppableNaive(int[] array, int len)
    {
        if (array[0] >= len)
            return true;

        if (array[0] <= 0)
            return false;

        bool ret = false;
        for (int i = array[0]; i >= 1; i--)
        {
            var newArray = new int[len - i];
            Array.Copy(array, i, newArray, 0, len - i);
            ret = ret || IsHoppableNaive(newArray, len - i);

            if (ret) // optimization - no point in continuing if already true...
                break;
        }

        return ret;
    }

Time complexity of this is 2^(n-1)... So this could be very inefficient. That is why it can be improved with Dynamic Programming.

For DP solution, I first solved this theoretically by constructing a table of n x n. The way you fill this table is for each row you take the tower number and set the subsequent columns to true, (representing can I reach the next tower? and not can I reach the current tower, as you are already in it). Otherwise you give it false (for the first row), and for any subsequent row you take whatever is in the upper row.

the * are ones that are true thanks to their above row, and not for the actual number.

(EDIT: How did I came up with this? If we go over a bad case solution - say 5, 4, 3, 2, 1, 0 - we can see that we end up computing a lot of stuff we already computed before - this is where DP can help us, if we store these calculations somewhere; So - the entire point of "the above row" is to tell us which calculations we don't need to redo).

Here's the code:

    public static bool IsHoppableDP(int[] array, int len)
    {
        bool[,] dp = new bool[len, len];

        for (int i = 0; i < len; i++)
        {
            for (int j = i; j < len; j++)
            {
                if (j < i + array[i])
                    dp[i, j] = true;
                else if (i > 0)
                    dp[i, j] = dp[i - 1, j];
                else
                    dp[i, j] = false;
            }
        }

        return dp[len - 1, len - 1];
    }

So, here we can save from bad cases, but even good cases will take n + (n-1) + (n-2) + ... + 1 - which is n*(n+1)/2 ... basically also O(n^2). Which is a major improvement over the O(2^n)

Finally there is the "Simple" solution shown here, without the helper method/function.

The "simple" solution (it was actually far less simple to write that tricky getNext function) seems to offer the best time and space complexity. It basically uses some "heuristics", i.e. we know that the best tower to jump to is the one that offers the farthest range. The farthest range can be computed by adding the current index with the current value. We just have to be careful not to get out-of-bounds Argument-Exception...

Here's the code:

    public static bool IsHoppableSimple(int[] array, int len)
    {
        int current = 0;
        while (true)
        {
            if (current >= len)
                return true;

            if (array[current] == 0)
                return false;

            current = bestNextStep(current, array, len);
        }
    }

    private static int bestNextStep(int current, int[] array, int len)
    {            
        int best = current + array[current]; // Assuming the current farthest is the best            

        for (int i = current; i < current + array[current]; i++) // find the actual best
        {
            if (i + array[i] > len)
                return i + array[i]; // caution against getting outside of the bounds of the array

            if (i + array[i] > best)
                best = i + array[i];
        }

        return best;
    }

Time complexity here is O(n) [we only traverse the array once], and space complexity is O(1) [we do everything in place].