C++

Forum

 
recursive loop not doing what I want

Dan Feerst (85)
You know the android phones with the 9 dots for a password, and you run your finger around to make a pattern. I was bored and sick in bed and started writing a little code this morning to try to figure out how many combinations there were. It is proving to be more difficult than I thought. It is not complete but here is what I think it should be doing up to this point.

There is a structure at the top called point which contains its point position(0-8), whether it has been touched, the number and a list of adjacent numbers(routes). There is a lot of code in the midsection which just populates structures for each of the 9 points.
At the bottom is a function called getRoutes( point *p )
There is some debug code in there so you can see what it is actually doing.
what I would like it to do, is this:
starting from whatever position it is initiated on( in this case 0 ) I want it to mark the current position as touched, scan through the routes, and look for ones that haven't been touched, spawn a new function for that position and repeat. More code will be required obviously to track the number of routes found at each depth, but right now I'm just trying to get it to fork properly. It seems to be going sequentially.

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
119
120
121
122
123
124
125
126
127
 
#include <iostream>
using namespace std;

unsigned int twoDeep = 0;
unsigned int threeDeep = 0;
unsigned int fourDeep = 0;
unsigned int fiveDeep = 0;
unsigned int sixDeep = 0;
unsigned int sevenDeep = 0;
unsigned int eightDeep = 0;
unsigned int nineDeep = 0;

struct point{
    bool touched;
    unsigned int number;
    unsigned short rt;
    unsigned short * rlist;
};
point makePoint( unsigned short num){
    point p;
    p.touched = false;
    p.number = num;
    switch ( num ){
    case 0:
        p.rt = 3;
        p.rlist = new unsigned short[p.rt];
        p.rlist[0] = 1;
        p.rlist[1] = 3;
        p.rlist[2] = 4;
        break;
    case 1:
        p.rt = 5;
        p.rlist = new unsigned short[p.rt];
        p.rlist[0] = 0;
        p.rlist[1] = 2;
        p.rlist[2] = 3;
        p.rlist[3] = 4;
        p.rlist[4] = 5;
        break;
    case 2:
        p.rt = 3;
        p.rlist = new unsigned short[p.rt];
        p.rlist[0] = 1;
        p.rlist[1] = 4;
        p.rlist[2] = 5;
        break;
    case 3:
        p.rt = 5;
        p.rlist = new unsigned short[p.rt];
        p.rlist[0] = 0;
        p.rlist[1] = 1;
        p.rlist[2] = 3;
        p.rlist[3] = 6;
        p.rlist[4] = 7;
        break;
    case 4:
        p.rt = 8;
        p.rlist = new unsigned short[p.rt];
        p.rlist[0] = 0;
        p.rlist[1] = 1;
        p.rlist[2] = 2;
        p.rlist[3] = 3;
        p.rlist[4] = 5;
        p.rlist[5] = 6;
        p.rlist[6] = 7;
        p.rlist[7] = 8;
        break;
    case 5:
        p.rt = 5;
        p.rlist = new unsigned short[p.rt];
        p.rlist[0] = 1;
        p.rlist[1] = 2;
        p.rlist[2] = 4;
        p.rlist[3] = 7;
        p.rlist[4] = 8;
        break;
    case 6:
        p.rt = 3;
        p.rlist = new unsigned short[p.rt];
        p.rlist[0] = 3;
        p.rlist[1] = 4;
        p.rlist[2] = 7;
        break;
    case 7:
        p.rt = 5;
        p.rlist = new unsigned short[p.rt];
        p.rlist[0] = 3;
        p.rlist[1] = 4;
        p.rlist[2] = 5;
        p.rlist[3] = 6;
        p.rlist[4] = 8;
        break;
    case 8:
        p.rt = 3;
        p.rlist = new unsigned short[p.rt];
        p.rlist[0] = 4;
        p.rlist[1] = 5;
        p.rlist[2] = 7;
        break;
    default:
        break;
    }
    return p;
void getRoutes( point * p ){
    static unsigned int depth = 0;                    // Start a static counter to keep track
    depth++;                                          // of the depth of the recursive loop.
    p->touched = true;                                // Mark the current point as visited
    cout << "Point: "<< p->number <<" - "<< p->rt << " routes via [ ";
        for(int i = 0; i < p -> rt; i++)
            cout << p -> rlist[i] << " ";
        cout << "]\n";
    for(int i = 0; i < p -> rt; i++){                 
        int jmpSize = p->rlist[i] - p->number;        //distance between the route and the current value
        cout << "Jump size = " << jmpSize <<endl;
        if( p->rlist[i] != '\0' && !(p + jmpSize)->touched && (p -> number + jmpSize) < 9)
            getRoutes((p + jmpSize));
    }
}
int main(){
    point position[9];
    for( unsigned short i=0; i < 9; i++ )
        position[i] = makePoint(i);
    getRoutes(&position[0]);
    return 0;
}
TheIdeasMan (6781)
Hi,

I might be wrong about most that follows, but here are things I noticed.

With recursion, I always look for a base case - that is, an ending situation. All I could see was, if all the conditions on line 115 are false, so the function returns. Is that right?

Have you tried using a debugger? It will save you days of wondering.

What is point.rt ? Presumably it is route? Either make the variable name meaningful or add a comment. Mind though, you did say you were sick in bed :+)
Gamer2015 (810)
uhm, you can move from one point to any other when i know what you mean, that means you can get from one point to any other so there is a infinite number of combinations.

Well, you still could try it like that, but i didn't test it ^^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <iostream>

int GetPossibilities(int Depth) /// Depth = how long your combination is
{
	if(Depth == 0)
		return 0;

	int OtherPoints = 8;
	int Possibilities = 0;

	for(int i = 0; i < OtherPoints; ++i)
	{
		 Possibilities += GetPossibilities(Depth - 1);
	}
	return Possibilities;
}

int main(void)
{
	int depth = 9; // you may click 9 buttons
	std::cout << "There are " << GetPossibilities(depth) << " possible Combinations with Depth " << depth << std::endl;

	return 0;
}
Dan Feerst (85)
Hey guys,

Yeah sorry for the messy code. The variables are not named well but I was trying to keep the commands small. The basic structure of the point struct was meant to be this.

1
2
3
4
5
6
7
 
struct point{
    bool touched;                         // Has the point been touched
    unsigned int number;             // Position of the point(1-8)
    unsigned short rt;                  // Number of adjacent positions
    unsigned short * rlist;            // Pointer array of adjacent positions in
                                                  // ascending order
};


The problem is that there are a lot of considerations to take into account which add to the complications of the code.
Input:
starting position and length of the password
constraints:
The pattern must be continuous, cannot pass over the same point twice and can move in all 8 directions.
I have never tried a debugger. I generally just code in tiled console windows, and I'm self taught, so I really don't know the first thing about them. I guess I should probably learn.
Gamer2015 (810)
Oh, so you want to start at a given Point at get all points around this one, right?
But you still want to figure out the number of combinations right?

Ah and also note that there is a closing bracked missing after your makePoint function...

Furthermore, calling your function from main() everything is fine, all points are marked as untouched.
Then within your function you set a point to visited, and never unset the "touched" variable to false, so as soon as a button is visited it never gets untouched (which makes recursive things useless because they won't be recalculated)
try adding p->touched = false; at the end of the function. i think that might actually do the trick, if it doesnt, continue reading ...
(I'm sorry, i don't find the right words to explain that)

I'll use make some changes to use std::vector instead of array and var with length of the array and i'll simulate your pointer behaviour by a function definition with call-by-reference

1
2
3
4
5
 
struct point {
    bool touched;
    unsigned int number; // Not used anywhere
    std::vector<unsigned short> rlist;
}


Now I'll give it an other try with that many constraints...
but I'll just try to get the Function getRoutes to work, everything else seems fine to me.

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
119
120
 
#include <iostream>
#include <vector>

struct point {
	bool touched;
		unsigned int number;  /// Not needed anywhere
	std::vector<unsigned short> rlist;
};

point makePoint(unsigned short num){
	point p;
	p.touched = false;
	switch ( num ){
	case 0:
		p.rlist.push_back(1);
		p.rlist.push_back(3);
		p.rlist.push_back(4);
		break;
	case 1:
		p.rlist.push_back(0);
		p.rlist.push_back(2);
		p.rlist.push_back(3);
		p.rlist.push_back(4);
		p.rlist.push_back(5);
		break;
	case 2:
		p.rlist.push_back(1);
		p.rlist.push_back(4);
		p.rlist.push_back(5);
		break;
	case 3:
		p.rlist.push_back(0);
		p.rlist.push_back(1);
		p.rlist.push_back(3);
		p.rlist.push_back(6);
		p.rlist.push_back(7);
		break;
	case 4:
		p.rlist.push_back(0);
		p.rlist.push_back(1);
		p.rlist.push_back(2);
		p.rlist.push_back(3);
		p.rlist.push_back(4);
		p.rlist.push_back(5);
		p.rlist.push_back(6);
		p.rlist.push_back(7);
		p.rlist.push_back(8);
		break;
	case 5:
		p.rlist.push_back(1);
		p.rlist.push_back(2);
		p.rlist.push_back(4);
		p.rlist.push_back(7);
		p.rlist.push_back(8);
		break;
	case 6:
		p.rlist.push_back(3);
		p.rlist.push_back(4);
		p.rlist.push_back(7);
		break;
	case 7:
		p.rlist.push_back(3);
		p.rlist.push_back(4);
		p.rlist.push_back(5);
		p.rlist.push_back(6);
		p.rlist.push_back(8);
		break;
	case 8:
		p.rlist.push_back(4);
		p.rlist.push_back(5);
		p.rlist.push_back(7);
		break;

	default:
		break;
	}
	return p;
}
int GetCombinations(int start, std::vector<point> points)
{
	points[start].touched = true;
	int combinations = 0;

/// Loop through Connected points
	for(int i = 0; i < points[start].rlist.size(); i++)
	{
/// Check if a connected point is touched (Note: looping through points[start].rlist 
/// makes it mandatory to call it so ugly because:
/// First i = points[start].rlist[0], the first connected point and so on 
		if(points[points[start].rlist[i]].touched == false)
		{
			combinations += 1; // When a Point is not touched yet, increase counter by 1
						// look for all combinations with that points that are not touched
			combinations += GetCombinations(points[start].rlist[i], points);
		}
	}
 
        points[start].touched = false; // DO NOT FORGET THAT, otherwise you will get "8" as result
	return combinations;
}
void GetCombinations(std::vector<point> points)
{
	int combinations = 0;

/// Look for the sum of the combinations from each starting position
	for(int i = 0; i < points.size(); i++)
		combinations += GetCombinations(i, points);

	std::cout << "Possible Combinations: " << combinations << std::endl;
}

int main(void)
{
	std::vector<point> Points;
	for( unsigned short i=0; i < 9; i++)
		Points.push_back(makePoint(i));

	GetCombinations(Points);
        return 0;
}


ps. sorry for the formatting, I made the code in QtCreator and copied it but the taps are for some reason converted to 8 spaces
Last edited on
Topic archived. No new replies allowed.