3
\$\begingroup\$

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);

}
\$\endgroup\$
  • \$\begingroup\$ The posted code does not compile! Amongst other things, it is missing the statement: #include <stdio.h> And is missing the prototype for the function: is_hoppable() and has the unused parameters to main() argc and argv[] \$\endgroup\$ – user3629249 Jan 28 '18 at 9:34
  • \$\begingroup\$ @user3629249, what do you mean "the unused parameters to main()..."? Yes to your two other points but the code compiles just fine with #include <stdio.h> and the function prototype. Apologies if I'm supposed to post code ready for compilation by copy/paste, but I just clicked on every related question on the side and maybe one of them had all the necessary #include statements and the likes. I've never been reprimanded for this before on Codereview, but I'll look for the policy if it exists. \$\endgroup\$ – jeremy radcliff Jan 28 '18 at 21:03
  • 1
    \$\begingroup\$ if the code does not (preferably cleanly) compile, then there is (effectively) nothing to review. \$\endgroup\$ – user3629249 Jan 28 '18 at 21:52
  • 1
    \$\begingroup\$ When compiling, always enable the warnings, then fix those warnings. ( for gcc, at a minimum use: -Wall -Wextra -Wconversion -pedantic -std=gnu11 ) Regarding the unused parameters to 'main()': There are two parameters: argc and argv[] Neither parameter is being used. Suggest using the signature: int main( void ) -or- the first two statements in the body of the function should be: (void)argc; and (void)argv \$\endgroup\$ – user3629249 Jan 28 '18 at 21:55
  • \$\begingroup\$ How can you jump from tower[1] to tower[4]? That example seems to be wrong. \$\endgroup\$ – Roland Illig Mar 25 '18 at 17:10
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the feedback. The single loop does look right to me, it makes sense. One thing that's interesting about this algorithm is that it guarantees to be run in exactly n steps regardless of the input, and the iterative approach you coded up makes that clear with the mandatory jumpTower -= 1 at each step. \$\endgroup\$ – jeremy radcliff Jan 27 '18 at 21:17
2
\$\begingroup\$

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;
    }
    
\$\endgroup\$
  • \$\begingroup\$ Thank you. Good point about adding const, I didn't know certain optimizations were possible based on that. \$\endgroup\$ – jeremy radcliff Feb 2 '18 at 21:02
2
\$\begingroup\$

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.

enter image description here

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].

\$\endgroup\$
  • \$\begingroup\$ Your solution could've been a new question. But it doesn't take a look at the code provided by the original post, so it's not a review. At Code Review, all answers should at least contain a review. \$\endgroup\$ – Mast Mar 24 '18 at 14:34
  • \$\begingroup\$ Please take a look at the help. Your question could become a review, but you'd have to make at least an insightful remark about the existing code. Why is the current code worse than your proposal, for example? What are the main flaws with it? Add that and you're well on your way. If you have any questions, you can find some of the regular users in chat. \$\endgroup\$ – Mast Mar 24 '18 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.