CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Apr 2011
Posts
5

Hi all,

I am writing a program in which there is a part that computes all the possible values for two vectors of string patterns, one like 1XX78X9X32X (11 digit) the other like 26XX (4 digit), using digits from 0 to 9, and that passes all these possible strings to another two vectors.
So I wrote 16 nested for loops, the outer one for vector, the 15 inner ones for every digit of the patterns (11+4).
But for some reason the loop is infinite and it never terminates. I could not discover why.
I would really appreciate it if you have any ideas and can help me, it is really urgent.

My code is:
Code:
```for(int x=0; x<namevect.size(); x++){

for(int a=0;a<=9;a++){

if(idpvect[x][0]=='X'){
idpvect[x][0]=intToChar(a);

}
for(int b=0;b<=9;b++){
if(idpvect[x][1]=='X'){
idpvect[x][1]=intToChar(b);

}
for(int c=0;c<=9;c++){
if(idpvect[x][2]=='X'){
idpvect[x][2]=intToChar(c);
}
for(int d=0;d<=9;d++){
if(idpvect[x][3]=='X'){
idpvect[x][3]=intToChar(d);
}
for(int e=0;e<=9;e++){
if(idpvect[x][4]=='X'){
idpvect[x][4]=intToChar(e);
}
for(int f=0;f<=9;f++){
if(idpvect[x][5]=='X'){
idpvect[x][5]=intToChar(f);
}
for(int g=0;g<=9;g++){
if(idpvect[x][6]=='X'){
idpvect[x][6]=intToChar(g);
}
for(int h=0;h<=9;h++){
if(idpvect[x][7]=='X'){
idpvect[x][7]=intToChar(h);
}
for(int i=0;i<=9;i++){
if(idpvect[x][8]=='X'){
idpvect[x][8]=intToChar(i);
}
for(int j=0;j<=9;j++){
if(idpvect[x][9]=='X'){
idpvect[x][9]=intToChar(j);
}
for(int k=0;k<=9;k++){
if(idpvect[x][10]=='X'){
idpvect[x][10]=intToChar(k);
}
for(int l=0;l<=9;l++){
if(bypvect[x][0]=='X'){
bypvect[x][0]=intToChar(l);
}
for(int m=0;m<=9;m++){
if(bypvect[x][1]=='X'){
bypvect[x][1]=intToChar(m);
}
for(int n=0;n<=9;n++){
if(bypvect[x][2]=='X'){
bypvect[x][2]=intToChar(n);
}
for(int o=0;o<=9;o++){
if(bypvect[x][3]=='X'){
bypvect[x][3]=intToChar(o);

if(validate(idpvect[x])){
tckimlik[x].push_back(idpvect[x]);
birthyear[x].push_back(bypvect[x]);
}
}
}}}}}}}}}}}}}}}}```

2. Elite Member Power Poster
Join Date
Aug 2000
Location
New York, NY, USA
Posts
5,656

Are you sure it is infinite?
May be it is just too loooong?

3. Member +
Join Date
Aug 2008
Posts
902

Infinite loop, or infinitively nested loops?

Maybe both?

4. Elite Member Power Poster
Join Date
Oct 2007
Location
Seattle, WA
Posts
10,895

If that indenting is correct, then you have loops to 10 nested 15 deep. That's 10^15 total iterations. Of course this is going to take awhile------hours, probably, days, maybe. It's not out of the realm of possibility for this sort of exhaustive enumeration to result in code which could take decades to complete.

You need to choose a faster algorithm to solve your problem.

5. Junior Member
Join Date
Apr 2011
Posts
5

Actually I realized that it is not infinite. But what kind of an algorithm should I use here to make it faster?

6. Elite Member Power Poster
Join Date
Nov 2003
Location
Florida
Posts
12,518

What's that thing supposed to be doing?

7. Elite Member Power Poster
Join Date
Aug 2000
Location
New York, NY, USA
Posts
5,656

Originally Posted by exca
But what kind of an algorithm should I use here to make it faster?
Algorithm for WHAT? You never said WHAT you are trying to do. Some sort of brute force hacking?

8. Junior Member
Join Date
Apr 2011
Posts
5

Well, no It is part of my school project. We have a 11-digit ID number and 4-digit birth year. We are using cURL to access the ID verification website. We have to have the name, surname, ID and birth year all matching for this. We are given a pattern like I said before, like 12672XX2367 and 198X. We must enumerate X's to see if such a combination exists or not. Our professor said, in our project there will be at most 4-5 X's.

9. Elite Member Power Poster
Join Date
Nov 2003
Location
Florida
Posts
12,518

10. Junior Member
Join Date
Apr 2011
Posts
5

If you do not answer because you think I am hacking something, well, with 15 nested for loops, it would take a quiitee long time. So, as I said before, we'll just have 3-4 X's. And why would I ask you for this if I have a pattern that I want to hack? Do I not know the number of unknown digits in that pattern? I could easily have written some nested for loops like above, it's not a big deal.
So, yes, I'm not a hacker, just a student who wishes to be able to finish her project

11. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

Originally Posted by exca
Well, no It is part of my school project. We have a 11-digit ID number and 4-digit birth year. We are using cURL to access the ID verification website. We have to have the name, surname, ID and birth year all matching for this. We are given a pattern like I said before, like 12672XX2367 and 198X. We must enumerate X's to see if such a combination exists or not. Our professor said, in our project there will be at most 4-5 X's.
The first thing you should have done is not write one line of code, and instead come up with an algorithm that is somewhat optimal. Then when you come up with an algorithm, you write the code.

You're making the mistake of trying to come up with an algorithm by writing code, and all that will do is to make the problem more difficult.

Regards,

Paul McKenzie

12. Elite Member Power Poster
Join Date
Nov 2003
Location
Florida
Posts
12,518

Originally Posted by exca
If you do not answer because you think I am hacking something, well, with 15 nested for loops, it would take a quiitee long time. So, as I said before, we'll just have 3-4 X's. And why would I ask you for this if I have a pattern that I want to hack? Do I not know the number of unknown digits in that pattern? I could easily have written some nested for loops like above, it's not a big deal.
So, yes, I'm not a hacker, just a student who wishes to be able to finish her project
Well as Paul said, figure out how to do it with a pencil and paper first. Basically you just need to know the number of Xs. Suppose it's 6, you'd need a single loop that counts to the biggest number 6 digits can hold. See what you can do with that.

13. Elite Member Power Poster
Join Date
Apr 1999
Posts
27,449

For example take the 11-digit ID number. Let's see if we can efficiently find the match if there are at most "n" X's in the number.

1) Since you know there will be n X's, and each X is a digit, we can generate all n-digit numbers starting from 0...0 to 9...9. For example, if there are 2 X's in the ID, the numbers you will generate are:
00
01
02
03
04
...
10
11
12
...
98
99
The ... are the numbers I didn't have time to list. Assume we can represent the above as a string, where the first digit on the left is at position 0, and the digit on the far right is at position n-1. So for example, 32 would be represented as a string (call the string "NumberString"):
Code:
```NumberString[0] = '3';
NumberString[1] = '2';```
Now you are also told the positions within the ID string where the X's are. Let's store this information into an array of integers called XPosition. So let's say the ID string is this:
Code:
`12672XX2367`
Since (counting from left to right), the position of the X's are 5 and 6, respectively, you have an XPosition array with the following values:
Code:
```XPosition[0] = 5;
XPosition[1] = 6;```
Now, for each of the numbers in the list I generated and was too lazy to fill in, you do this:
Code:
```for ( each 2-digit number i, starting from 00 up to 99 )
{
NumberString[0] = // convert first digit of i to char
NumberString[1] = // convert second digit of i to char
IDString[XPosition[0]] = NumberString[0];
IDString[XPosition[1]] = NumberString[1];

if ( IDString passes my test )
{
break out of loop with a "found!!" message;
}
}```
So the algorithm does this:
Code:
```Try 00:
12672002367
is this valid?  Yes->found it, so quit : No->keep going

Try 01:
12672012367
is this valid?  Yes->found it, so quit : No->keep going

Try 02:
12672022367
is this valid?  Yes->found it, so quit : No->keep going

... (etc.)

Try 98:
12672982367
is this valid?  Yes->found it, so quit : No->keep going

Try 99:
12672992367
is this valid?  Yes->found it, so quit : No->quit, because we tried all the combinations```
Do you understand now? Change the ID string so that the X's are not consecutive (position 5 and 6), and you see the algorithm still works because the "magic" of the XPosition array. Change the number of X's, and the algorithm still works, because we would be generate all n-digit numbers, where n is the number of X's and the loop will be performed 10^n times.

If there are 5 X's in the ID string, the loop will run at most 100,000 before finding a match. Not the greatest thing in the wold, but it isn't 10^15 or whatever ridiculous number of times your solution was looping. Also, note that the algorithm has no inherent nested loops. Only one loop is described in the algorithm above.

This is how you are to think out a problem. Note that none of it, except maybe a few lines of the psuedo-code loop, is C++. You can take the idea (algorithm), and adapt it to any language.

Now, your job is to take the algorithm, and fit it to the programming language you're using. In C++, you may want to use vector to easily resize arrays, for another language, you use some other paradigm that fits the language. You may want to write a separate function to turn an int into a character string so that you have a ready-made function to turn an int 0 to "000" (if there are three X's), etc.

Is this solution optimal? Probably not. I'm sure others have better ones than the one I gave. But at the very least, it isn't naive as the solution you initially gave where you're nesting loops to the umpteenth level. I bet the professor was looking for "solutions" just as yours, and expected it to fall flat on its face due to it taking days to run. Maybe that was the whole idea of the assignment -- not who can write a bunch of loops, but who can think of an optimal way of solving the problem.

I also wouldn't be the least bit surprised if you handed in your original solution, even though it will "solve the problem". and got a grade of "C" or below, but another student gets a "B" who had tried to implement the solution I gave, but didn't finish the program. The latter shows that they thought about the problem, refused to implement the naive approach, and attempted to solve the problem optimally.

Regards,

Paul McKenzie
Last edited by Paul McKenzie; April 9th, 2011 at 05:31 PM.

14. Junior Member
Join Date
Apr 2011
Posts
5

I made some changes to the initial code I have given (before you responded)
I count the numbers of X's in a string and determine their positions (I use an array arr1 and increment the positions where there is an X)
And then I use continue, to skip the for loop if there is no X at that position, to avoid unnecessary cycles. Like this:

Code:
```for(int l=0;l<=9;l++){
if(arr1[y][0]!=1)
continue;
idpvect[y][0]=intToChar(l);

for(int m=0;m<=9;m++){
if(arr1[y][1]!=1)
continue;
idpvect[y][1]=intToChar(m);
.......```
Will it do fine? Or should I try what you told me? Which one is better do you think?

15. Elite Member Power Poster
Join Date
Nov 2003
Location
Florida
Posts
12,518

Originally Posted by exca
I made some changes to the initial code I have given (before you responded)
I count the numbers of X's in a string and determine their positions (I use an array arr1 and increment the positions where there is an X)
And then I use continue, to skip the for loop if there is no X at that position, to avoid unnecessary cycles. Like this:

Code:
```for(int l=0;l<=9;l++){
if(arr1[y][0]!=1)
continue;
idpvect[y][0]=intToChar(l);

for(int m=0;m<=9;m++){
if(arr1[y][1]!=1)
continue;
idpvect[y][1]=intToChar(m);
.......```
Will it do fine? Or should I try what you told me? Which one is better do you think?

I alluded to and Paul expounded on the best way to approach this problem. I can't tell what you're trying to do but you've been given the best approach.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•