C++

Forum

 
Jumping game in C++

Shervan360 (183)
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.)

I uploaded question:
https://ibb.co/SBY7FjP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
  #include<iostream>
#include <string>
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); 
}
dutch (2548)
You need to change it something like this:

1
2
3
4
5
6
7
8
9
10
11
12
 
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.
Shervan360 (183)
Thank you for your help,
I fixed my code and add seen array for it.
Is this a good solution? Thanks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#include<iostream>
#include <string>
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
zapshe (1834)
Here's a primitive recursive solution I made:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
#include <iostream>
#include <string>

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
zapshe (1834)
I might have too much free time on my hands:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
#include <iostream>
#include <string>

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
lastchance (6980)
Can you treat it as a graph and use Dijkstra's algorithm?
lastchance (6980)
Via Dijkstra's algorithm (shortest path):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
#include <iostream>
#include <vector>
#include <set>
using namespace std;

const int LARGE = 1000000000;

struct Node
{
   int value;
   int distance;
   int prev;
};

void output( const vector<Node> &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> node( N );
   set<int> 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
dutch (2548)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
#include <iostream>
#include <iomanip>

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
dutch (2548)
Here's a solution that shows the resulting paths.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <memory>
#include <algorithm>
using namespace std;

using Stack = std::vector<int>;
using BoolArray = std::unique_ptr<bool[]>;

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<bool[]>(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<int[]>(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
zapshe (1834)
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.