CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 16
  1. #1
    Join Date
    Apr 2011
    Posts
    5

    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]);
    											}
    										}
    }}}}}}}}}}}}}}}}

  2. #2
    Join Date
    Aug 2000
    Location
    New York, NY, USA
    Posts
    5,656

    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...

  3. #3
    Join Date
    Aug 2008
    Posts
    902

    Re: infinite loop- please help

    Infinite loop, or infinitively nested loops?

    Maybe both?

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

    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 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. #5
    Join Date
    Apr 2011
    Posts
    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?

  6. #6
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: infinite loop- please help

    What's that thing supposed to be doing?

  7. #7
    Join Date
    Aug 2000
    Location
    New York, NY, USA
    Posts
    5,656

    Re: infinite loop- please help

    Quote Originally Posted by exca View Post
    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...

  8. #8
    Join Date
    Apr 2011
    Posts
    5

    Re: infinite loop- please help

    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. #9
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: infinite loop- please help

    Your school project involves ID and password hacking??? Really???

  10. #10
    Join Date
    Apr 2011
    Posts
    5

    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 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. #11
    Join Date
    Apr 1999
    Posts
    27,449

    Re: infinite loop- please help

    Quote Originally Posted by exca View Post
    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. #12
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: infinite loop- please help

    Quote Originally Posted by exca View Post
    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. #13
    Join Date
    Apr 1999
    Posts
    27,449

    Re: infinite loop- please help

    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. #14
    Join Date
    Apr 2011
    Posts
    5

    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.

  15. #15
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,635

    Re: infinite loop- please help

    Quote Originally Posted by exca View Post
    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.

Page 1 of 2 12 LastLast

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured