### Jumping game in C++

Hello,

I want to create a jumping game with recursion in C++.
I try to write code to solve the jumping game in C++ but I have a problem.

Stack overflow (I debug the program and I saw when goal condition is true the program is still running.)

https://ibb.co/SBY7FjP

 ``1234567891011121314151617181920`` `````` #include #include using namespace std; bool jump(int arr[], int len, int current) { if (current < 0 || current > len) return false; if (current == len-1) return true; jump(arr, len, current + arr[current]); jump(arr, len, current - arr[current]); } int main() { int arr[] = { 3,6,4,1,3,4,2,5,3,0 }; //int arr[] = { 6, 8, 2, 3, 4, 6, 3, 5, 2, 0 }; cout << jump(arr, 9, 0); }``````
You need to change it something like this:

 ``123456789101112`` ``````bool jump(int arr[], int len, int current = 0) // use a default parameter for the initial call { if (current < 0 || current > len) return false; if (current == len-1) return true; if (jump(arr, len, current + arr[current])) return true; // if jump returns true, keep returning true so it "bubbles up" the call stack. if (jump(arr, len, current - arr[current])) return true; return false; }``````

However, you can still get into an infinite loop and blow the stack if it encounters a cycle. You can avoid that by marking the used numbers in some way so that you don't use them again. Maybe you could negate the values to mark them since the input seems to be all positive except for the last number, which is a 0 (actually it's value doesn't really matter). You need to unmark (negate back to positive) them as you come back out of unsuccessful calls so they can be reused.
I fixed my code and add seen array for it.
Is this a good solution? Thanks

 ``1234567891011121314151617181920212223242526272829303132333435363738`` ``````#include #include using namespace std; bool jump(int arr[], bool seen[],int len, int current = 0) { if (current < 0 || current > len) return false; if (current == len-1) return true; current = current + arr[current]; if (seen[current] || current > len) return false; seen[current] = true; if (jump(arr, seen, len, current)) return true; current = current - arr[current]; if (seen[current] || current > len) return false; seen[current] = true; if (jump(arr, seen, len, current)) return true; return false; } int main() { bool seen[5] = { false }; //int arr[] = { 3,6,4,1,3,4,2,5,3,0 }; //int arr[] = { 6, 8, 2, 3, 4, 6, 3, 5, 2, 0 }; int arr[] = { 3,1,2,3,0 }; cout << jump(arr,seen, 5, 0); }``````
Last edited on
Here's a primitive recursive solution I made:
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657`` ``````#include #include using namespace std; int count = 0; bool jump(int arr[], int len, int current = 0) { if (current == len || len <= 0) return false; if (::count > 100) { //No Solution return false; } if ((arr[current] + current) > len) { ::count++; current = current - arr[current]; if (current < 0) return false; if (!jump(arr, len, current)) { return false; } } else if ((arr[current] + current) < len) { current = current + arr[current]; if (!jump(arr, len, current)) { return false; } } else if ((arr[current] + current) == len) { current = current + arr[current]; return true; } return true; } int main() { int arr[] = { 6, 8, 2, 3, 4, 6, 3, 5, 2, 0 }; int arr1[] = { 3, 6, 4, 1, 3, 4, 2, 5, 3, 0 }; int arr2[] = { 3, 1, 2, 3, 0 }; cout << (jump(arr, 9, 0) ? "True\n" : "False\n"); ::count = 0; cout << (jump(arr1, 9, 0) ? "True\n" : "False\n"); ::count = 0; cout << (jump(arr2, 4, 0) ? "True\n" : "False\n"); }``````

It doesn't solve the problem the same way the linked solution wants to, but it should be able to solve most puzzles that are solvable (NOT all). I also made a very primitive way to detect whether or not there's no solution - if we reach a point where the number we're on is too large to grant victory 100 times. If you try to reach the end 100 times and fail, it'll consider the puzzle unsolvable.

The issue with your solution is that it's only capable of going backwards ONCE. And if the puzzle requires going backwards more than once, it'll fail and conclude with "false" even though the puzzle has a solution.
Last edited on
I might have too much free time on my hands:

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118`` ``````#include #include int c = 0; using namespace std; bool jump(int arr[], bool a[], int len, int current = 0) { if (c > (len * 100)) return false; c++; if(current < 0) std::cout << "\n\nCurrent: " << current << "\n\n"; a[current] = true; if (((arr[current] + current) == len || current == len)) { current = arr[current] + current; return true; } if ((arr[current] + current) < len && a[current - arr[current]]) { current = arr[current] + current; if (jump(arr, a, len, current)) return true; else if ((current - arr[current]) > 0) { if (arr[current] == arr[current - arr[current]] || a[current - arr[current]]) return false; current = current - arr[current]; if (jump(arr, a, len, current)) return true; } } if ((current - arr[current]) > 0) { if (arr[current] == arr[current - arr[current]] && a[current - arr[current]]) return false; if (a[current - arr[current]]) { int temp = current - arr[current]; if (!((temp - arr[temp]) > 0)) { return false; } current = current - arr[current]; } current = current - arr[current]; if (jump(arr, a, len, current)) return true; else if ((arr[current] + current) < len) { current = arr[current] + current; if (jump(arr, a, len, current)) return true; } } return false; } int main() { int arr[] = { 6, 8, 2, 3, 4, 6, 3, 5, 2, 0 }; int arr1[] = { 3, 6, 4, 1, 3, 4, 2, 3, 1, 0 }; int arr2[] = { 3, 1, 2, 3, 0 }; //False int arr3[] = { 3, 6, 4, 1, 3, 4, 2, 7, 1, 0 }; int arr4[] = { 3, 6, 4, 1, 3, 4, 2, 4, 1, 0 }; int arr5[] = { 3, 6, 4, 1, 1, 2, 2, 4, 1, 0 }; int arr6[] = { 7, 6, 4, 1, 1, 2, 2, 4, 1, 0 }; int arr7[] = { 3, 6, 5, 1, 3, 4, 3, 4, 1, 0 }; //False int arr8[] = { 3, 7, 1, 1, 3, 4, 2, 4, 1, 0 }; int arr9[] = { 3, 9, 1, 1, 3, 4, 2, 4, 1, 0 }; //False int arr10[] = { 3, 9, 1, 1, 3, 4, 2, 4, 1, 2, 6, 2, 6, 0 }; int arr11[] = { 3, 9, 1, 1, 3, 4, 2, 4, 1, 2, 6, 3, 6, 0 }; //False bool a[9] = { false }; bool a1[9] = { false }; bool a2[5] = { false }; bool a3[9] = { false }; bool a4[9] = { false }; bool a5[9] = { false }; bool a6[9] = { false }; bool a7[9] = { false }; bool a8[9] = { false }; bool a9[9] = { false }; bool a10[13] = { false }; bool a11[13] = { false }; std::cout << "0: " << (jump(arr, a, 9, 0) ? "True\n" : "False\n"); c = 0; std::cout << "1: " << (jump(arr1, a1, 9, 0) ? "True\n" : "False\n"); c = 0; std::cout << "2: " << (jump(arr2, a2, 4, 0) ? "True\n" : "False\n"); c = 0; std::cout << "3: " << (jump(arr3, a3, 9, 0) ? "True\n" : "False\n"); c = 0; std::cout << "4: " << (jump(arr4, a4, 9, 0) ? "True\n" : "False\n"); c = 0; std::cout << "5: " << (jump(arr5, a5, 9, 0) ? "True\n" : "False\n"); c = 0; std::cout << "6: " << (jump(arr6, a6, 9, 0) ? "True\n" : "False\n"); c = 0; std::cout << "7: " << (jump(arr7, a7, 9, 0) ? "True\n" : "False\n"); c = 0; std::cout << "8: " << (jump(arr8, a8, 9, 0) ? "True\n" : "False\n"); c = 0; std::cout << "9: " << (jump(arr9, a9, 9, 0) ? "True\n" : "False\n"); c = 0; std::cout << "10: " << (jump(arr10, a10, 13, 0) ? "True\n" : "False\n"); c = 0; std::cout << "11: " << (jump(arr11, a11, 13, 0) ? "True\n" : "False\n"); }``````

I wanted a solution without the bool array, but it would have made the code larger. Oh well.
Last edited on
Can you treat it as a graph and use Dijkstra's algorithm?
Via Dijkstra's algorithm (shortest path):

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172`` ``````#include #include #include using namespace std; const int LARGE = 1000000000; struct Node { int value; int distance; int prev; }; void output( const vector &node, int start, int p ) { if ( p != start ) output( node, start, node[p].prev ); cout << "position: " << p << " ( value = " << node[p].value << " )\n"; } int main() { int sequence[] = { 3, 6, 4, 1, 3, 4, 2, 5, 3, 0 }; int N = sizeof sequence / sizeof sequence[0]; // Define nodes of graph vector node( N ); set available; int p = 0; node[p] = { sequence[p], 0, -1 }; for ( int i = 1; i < N; i++ ) { node[i] = { sequence[i], LARGE, -1 }; available.insert( i ); } while ( true ) { // Update distances fom last finalised point int d = node[p].distance + 1; for ( int q : { p - node[p].value, p + node[p].value } ) { if ( q >= 0 && q < N && available.find( q ) != available.end() && node[q].distance > d ) { node[q].distance = d; node[q].prev = p; } } // Find shortest available distance and finalise d = LARGE; for ( int q : available ) { if ( node[q].distance < d ) { d = node[q].distance; p = q; } } if ( d == LARGE ) { cout << "insoluble\n"; return 1; } available.erase( p ); // Output if finished if ( p == N - 1 ) break; } output( node, 0, N - 1 ); }``````

 ```position: 0 ( value = 3 ) position: 3 ( value = 1 ) position: 2 ( value = 4 ) position: 6 ( value = 2 ) position: 8 ( value = 3 ) position: 5 ( value = 4 ) position: 9 ( value = 0 )```

If you change the sequence to
{ 6, 8, 2, 3, 4, 6, 3, 5, 2, 0 }
you get
 ```position: 0 ( value = 6 ) position: 6 ( value = 3 ) position: 9 ( value = 0 )```

Try changing the sequence to
{ 6, 8, 2, 3, 4, 6, 8, 5, 2, 0 }
Last edited on
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344`` ``````#include #include bool jump(int *a, int len, int curr = 0) { if (!(curr >= 0 && curr < len && a[curr] >= 0)) return false; if (curr == len - 1) return true; a[curr] *= -1; if (jump(a, len, curr + a[curr]) || jump(a, len, curr - a[curr])) return true; a[curr] *= -1; return false; } // search for 0 at end of array to determine the length. int length(int *a) { int *end = a; while (*end) ++end; return end - a + 1; // return length including the 0 } int main() { int a[][20] = { { 6, 8, 2, 3, 4, 6, 3, 5, 2, 0 }, // 0 { 3, 6, 4, 1, 3, 4, 2, 3, 1, 0 }, // 1 { 3, 1, 2, 3, 0 }, // 2 false { 3, 6, 4, 1, 3, 4, 2, 7, 1, 0 }, // 3 { 3, 6, 4, 1, 3, 4, 2, 4, 1, 0 }, // 4 { 3, 6, 4, 1, 1, 2, 2, 4, 1, 0 }, // 5 { 7, 6, 4, 1, 1, 2, 2, 4, 1, 0 }, // 6 { 3, 6, 5, 1, 3, 4, 3, 4, 1, 0 }, // 7 false { 3, 7, 1, 1, 3, 4, 2, 4, 1, 0 }, // 8 { 3, 9, 1, 1, 3, 4, 2, 4, 1, 0 }, // 9 false { 3, 9, 1, 1, 3, 4, 2, 4, 1, 2, 6, 2, 6, 0 }, // 10 { 3, 9, 1, 1, 3, 4, 2, 4, 1, 2, 6, 3, 6, 0 } // 11 false }; int size = sizeof a / sizeof *a; std::cout << std::boolalpha; for (int i = 0; i < size; ++i) std::cout << std::setw(2) << i << ": " << jump(a[i], length(a[i])) << '\n'; }``````

Last edited on
Here's a solution that shows the resulting paths.

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485`` ``````#include #include #include #include #include using namespace std; using Stack = std::vector; using BoolArray = std::unique_ptr; bool jump_r(int *a, int size, int curr, BoolArray& seen, Stack& indices) { if (!(curr >= 0 && curr < size && !seen[curr])) return false; seen[curr] = true; indices.push_back(curr); if (curr == size - 1) return true; if (jump_r(a, size, curr + a[curr], seen, indices) || jump_r(a, size, curr - a[curr], seen, indices)) return true; indices.pop_back(); seen[curr] = false; return false; } Stack jump(int *a, int size) { Stack indices; auto seen = std::make_unique(size); jump_r(a, size, 0, seen, indices); return indices; } void print_result(int *a, int size, const Stack& indices) { for (int i = 0; i < size; ++i) cout << std::setw(2) << a[i] << ' '; cout << '\n'; auto pos = std::make_unique(size); std::fill(&pos[0], &pos[size], -1); for (size_t i = 0; i < indices.size(); ++i) pos[indices[i]] = i; for (int i = 0; i < size; ++i) if (pos[i] >= 0) cout << std::setw(2) << pos[i] << ' '; else cout << " "; cout << '\n'; } // search for 0 at end of array to determine the length. int length(int *a) { int *end = a; while (*end) ++end; return end - a + 1; // return length including the 0 } int main() { int a[][20] = { { 6, 8, 2, 3, 4, 6, 3, 5, 2, 0 }, // 0 { 3, 6, 4, 1, 3, 4, 2, 3, 1, 0 }, // 1 { 3, 1, 2, 3, 0 }, // 2 false { 3, 6, 3, 1, 3, 4, 2, 7, 1, 0 }, // 3 { 4, 6, 4, 1, 3, 4, 2, 4, 1, 0 }, // 4 { 7, 6, 4, 1, 1, 2, 2, 4, 1, 0 }, // 5 { 3, 6, 5, 1, 3, 4, 3, 4, 1, 0 }, // 6 false { 3, 7, 1, 1, 3, 4, 2, 4, 1, 0 }, // 7 { 3, 9, 1, 1, 3, 4, 2, 4, 1, 0 }, // 8 false { 3, 9, 1, 1, 3, 4, 2, 4, 1, 2, 6, 2, 6, 0 }, // 9 { 3, 9, 1, 1, 3, 4, 2, 4, 1, 2, 6, 3, 6, 0 }, // 10 false { 7, 1, 6, 1, 2, 1, 5, 3, 1, 6, 2, 6, 6, 1, 1, 3, 1, 2, 3, 0 } }; int size = sizeof a / sizeof *a; for (int i = 0; i < size; ++i) { auto indices = jump(a[i], length(a[i])); std::cout << i << ":\n"; if (indices.size() > 0) { std::cout << "Solution:\n"; print_result(a[i], length(a[i]), indices); } else std::cout << "No solution.\n"; std::cout << '\n'; } }``````

 ```0: Solution: 6 8 2 3 4 6 3 5 2 0 0 1 2 1: Solution: 3 6 4 1 3 4 2 3 1 0 0 2 1 3 4 5 2: No solution. 3: Solution: 3 6 3 1 3 4 2 7 1 0 0 2 1 3 4 4: Solution: 4 6 4 1 3 4 2 4 1 0 0 4 3 1 5 2 6 7 5: Solution: 7 6 4 1 1 2 2 4 1 0 0 3 2 4 1 5 6 6: No solution. 7: Solution: 3 7 1 1 3 4 2 4 1 0 0 3 1 2 4 5 8: No solution. 9: Solution: 3 9 1 1 3 4 2 4 1 2 6 2 6 0 0 1 2 3 4 5 10: No solution. 11: Solution: 7 1 6 1 2 1 5 3 1 6 2 6 6 1 1 3 1 2 3 0 0 4 1 2 5 3 6 7 ```
Last edited on
Didn't know there was an algorithm already made that I could have coded from. With my brute-force code, knowing the exact path it took to get to the answer would be difficult if even possible. Nice solutions !
Topic archived. No new replies allowed.