C++

Forum

 
Jumping game in C++

Dec 28, 2019 at 8:08pm
Shervan360 (184)
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); 
}
Edit & run on cpp.sh
Dec 28, 2019 at 9:18pm
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.
Dec 28, 2019 at 11:37pm
Shervan360 (184)
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); 

}
Edit & run on cpp.sh
Last edited on Dec 29, 2019 at 12:42am
Dec 29, 2019 at 2:59am
zapshe (1983)
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");
}
Edit & run on cpp.sh


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 Dec 29, 2019 at 3:30am
Dec 29, 2019 at 6:41am
zapshe (1983)
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");
}
Edit & run on cpp.sh


I wanted a solution without the bool array, but it would have made the code larger. Oh well.
Last edited on Dec 29, 2019 at 6:42am
Dec 29, 2019 at 9:14am
lastchance (6980)
Can you treat it as a graph and use Dijkstra's algorithm?
Dec 29, 2019 at 1:48pm
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 );
}
Edit & run on cpp.sh


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 Dec 29, 2019 at 5:41pm
Dec 29, 2019 at 1:55pm
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';
}
Edit & run on cpp.sh

Last edited on Dec 29, 2019 at 1:56pm
Dec 29, 2019 at 2:37pm
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';
    }
}
Edit & run on cpp.sh


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 Dec 29, 2019 at 4:07pm
Dec 30, 2019 at 12:17am
zapshe (1983)
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.