
April 8th, 2011, 11:00 AM
#1
infinite loop please help
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.
Thanks in advance..
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]);
}
}
}}}}}}}}}}}}}}}}

April 8th, 2011, 11:17 AM
#2
Re: infinite loop please help
Are you sure it is infinite?
May be it is just too loooong?
Vlad  MS MVP [2007  2012]  www.FeinSoftware.com
Convenience and productivity tools for Microsoft Visual Studio:
FeinWindows  replacement windows manager for Visual Studio, and more...

April 8th, 2011, 11:29 AM
#3
Re: infinite loop please help
Infinite loop, or infinitively nested loops?
Maybe both?

April 8th, 2011, 11:31 AM
#4
Re: infinite loop please help
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 awhilehours, 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.

April 8th, 2011, 02:33 PM
#5
Re: infinite loop please help
Actually I realized that it is not infinite. But what kind of an algorithm should I use here to make it faster?

April 8th, 2011, 02:42 PM
#6
Re: infinite loop please help
What's that thing supposed to be doing?

April 8th, 2011, 02:43 PM
#7
Re: infinite loop please help
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?
Vlad  MS MVP [2007  2012]  www.FeinSoftware.com
Convenience and productivity tools for Microsoft Visual Studio:
FeinWindows  replacement windows manager for Visual Studio, and more...

April 8th, 2011, 03:04 PM
#8
Re: infinite loop please help
Well, no It is part of my school project. We have a 11digit ID number and 4digit 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 45 X's.

April 8th, 2011, 03:17 PM
#9
Re: infinite loop please help
Your school project involves ID and password hacking??? Really???

April 8th, 2011, 03:27 PM
#10
Re: infinite loop please help
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 34 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

April 8th, 2011, 03:31 PM
#11
Re: infinite loop please help
Originally Posted by exca
Well, no It is part of my school project. We have a 11digit ID number and 4digit 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 45 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

April 8th, 2011, 03:47 PM
#12
Re: infinite loop please help
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 34 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.

April 8th, 2011, 04:02 PM
#13
Re: infinite loop please help
For example take the 11digit 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 ndigit 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 n1. 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:
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 2digit 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 ndigit 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 psuedocode 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 readymade 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.

April 8th, 2011, 04:50 PM
#14
Re: infinite loop please help
Thank you very much for your response and also advices.
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?
Thanks in advance.

April 8th, 2011, 05:50 PM
#15
Re: infinite loop please help
Originally Posted by exca
Thank you very much for your response and also advices.
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?
Thanks in advance.
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

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
