infinite loop of string going through all possible character combinations in the alphabet, then breaks on match ... ??

[joshg]

I've been scratching my head about this for two days now......

Basically, I'm trying to write something that will test every single possible itteration of every single character in an array.

My idea is to have an array of my possible "choice" of characters, so it would have a value something like:

("a","b","c","d","e",..."z","A","B",...."Z")

And I have a string that I need to match it up to.

So basically I want to loop until myTestString = stringToMatch

And, theoretically, if you did a printout of "myTestString" for every test, it should look something like this:

a
b
c
d
e
f
g
...
z
A
B
...
Z
aa
ab
ac
ad
...
aZ
ba
bb
bc
...
...
ZZ
aaa
aab
aac
............
ZZZ
aaaa
aaab
aaac
............
ZZZZ
.........................
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaab
aaaaaaaaaaaaaaac
aaaaaaaaaaaaaaad
..........................
ZZZZZZZZZZZZZZZY
ZZZZZZZZZZZZZZZZ
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaab
aaaaaaaaaaaaaaaac
.....

and just keep going and going and going and going and going ... until it finds a case-sensitive match!

I've tried a few different ways of nesting loops together but I can't quite get the logic down.


Anyone have any ideas or an easy method to do this?

Thanks for any advice...

 

[notfred]

Why not just use regular expressions?

 

[joshg]

Hmmm...

Well, I haven't thought of that.

I don't have a whole lot of experience with Regular Expressions - the whole pattern deal always throws me off when I start looking at it.

However, from my limited knowledge of it, I'm not sure if it will work in this instance. I don't have the pattern for the "match string" that I'm looking for (as it could be anything), that's why I thought the easiest way to do it was to be just try everything until you get a match.

If you think regexp might work for this, would you care to post a little code or psuedo code that could do something about what I'm looking for, so that I can get an idea of what you're talking about? Thanks!

 

[Barnaby W. Füi]

I don't even get what you're trying to do. Why would you need to loop through letters to find a match to a string that you already have?

 

[notfred]

Originally posted by: BingBongWongFooey
I don't even get what you're trying to do. Why would you need to loop through letters to find a match to a string that you already have?

Yeah, that's what it sounds like you want to me, too.

Is there some goal of something you're trying to find or are you jsut trying to waste processor time and display a lot of random looknig characters on the screen?

 

[DaveSimmons]

Originally posted by: BingBongWongFooey
I don't even get what you're trying to do. Why would you need to loop through letters to find a match to a string that you already have?

a very inefficient password-cracking tool?

a very inefficient and easy-to-crack encryption tool? (whatever is matching the string also creates a code)

 

[Barnaby W. Füi]

Originally posted by: DaveSimmons

Originally posted by: BingBongWongFooey
I don't even get what you're trying to do. Why would you need to loop through letters to find a match to a string that you already have?

a very inefficient password-cracking tool?

a very inefficient and easy-to-crack encryption tool? (whatever is matching the string also creates a code)

This wouldn't crack anything though, it would basically just be a guage of how long it takes to "count" characters up to create a given string (which I suppose could be useful for something ). You already have the string you're trying to match, so you're not finding out anything about it.

 

[joshg]

This wouldn't crack anything though, it would basically just be a guage of how long it takes to "count" characters up to create a given string (which I suppose could be useful for something ). You already have the string you're trying to match, so you're not finding out anything about it.

Exactly!! I just kind of got stumped by it and was wondering if anyone might be able to help me with the logic...

The loop needs to be dynamic in that it keeps adding on an additional character to the string...

I've gotten as far as:

a
b
c
...
Z
aa
ab
...
ZX
ZY
ZZ

... but then it just goes right back to "aa" and starts the 2-char loop again:

...
ZY
ZZ
aa
ab
....
ZZ
aa
... (etc.)

I've also sort of accomplished the same thing but instead of getting stuck at 2 characters it gets stuck at 3, and is much dirtier.



What's my reasoning? Well, it's a challenge and I want to figure it out! (Or at least learn how to do it... you never know when something might come in handy! I've used code ideas from WAY back before that I thought I was just piddling around, but it turned into good use )

 

[notfred]

I thought about trying to do this, but then I kept trying to think of the most efficient way to do it, and that is this: "newstring = oldstring;" So screw it, you get the same output, and it works.

 

[joshg]

heheh, care to expand on that?

Sure it sounds simple by design, and I honestly thought it was going to take me all of 10 minutes... but actually trying to put it down and run it and get the right result - well that's a totally different story it seems.

 

[DaveSimmons]

Originally posted by: BingBongWongFooey

Originally posted by: DaveSimmons

Originally posted by: BingBongWongFooey
I don't even get what you're trying to do. Why would you need to loop through letters to find a match to a string that you already have?

a very inefficient password-cracking tool?

a very inefficient and easy-to-crack encryption tool? (whatever is matching the string also creates a code)

This wouldn't crack anything though, it would basically just be a guage of how long it takes to "count" characters up to create a given string (which I suppose could be useful for something ). You already have the string you're trying to match, so you're not finding out anything about it.

It's probably a class assignment so I'm not going to give a solution, but if the "stringToMatch" was NOT really known this describes a brute-force password cracking attempt.

do
generate next permutation
try permutation as password
while not accepted

 

[joshg]

Well, no not a class assignment - just a challenge to myself.

do
generate next permutation
try permutation as password
while not accepted

-- I know, sounds simple, right? Ok then, what would you suggest the "generate next permutation" logic to read? ... that's the hard part!

 

[Barnaby W. Füi]

Originally posted by: DaveSimmons
but if the "stringToMatch" was NOT really known this describes a brute-force password cracking attempt.

Ah, gotcha.

 

[joshg]

The string will be known - I will be inputting it myself via a prompt at the beginning of the run.


Since this would be pretty innefficient, I'm not quite sure exactly what I'd do with it... thought of using it to test speed of different types of loops and in different languages/compilers, in different OS's and different computers (I.E. Intel vs. AMD, mobo vs. mobo, etc...) and compare run times.


Here's all I'm trying to get at: If you were asked to print something like I sampled in the first post (the a, b, c... aa, ab, etc...) via a few nested loops (or whatever you may choose), how would you do it?

As I've said, it sure seems easy at first, but after actually trying to do it I can't seem to get it planted correctly!

 

[labgeek]

Assuming ASCII not unicode - design your program to count in base256 from 0 to 256^(# chars in the string) where the output is then decoded to that ASCII equivalent (like FF is 255 in hex). If you want to assume you know the # of characters, you would use integer division of the # div 256^n then taking the ASCII equivalent, where n is the number of characters looping -1 each time starting at n-1 until n=0, adding the character to the string. But if you don't want to assume you know the # of characters use the modulus instead and work up instead of down subtracting the modulus of #(256^n) times 256^n-1 with n starting at 1 (not 0) and working up until the left the remaining is 0 again each time you use the modulus take the ASCII equivalent and add it this time to the beginning of the string.

Let me work this in an example...
Word = "lab"
l = 108 decimal * 256^2 or 7077888
a = 97 * 256^1 or 24832
b = 98 * 256^0 or 98
7077888 + 24832 + 98 = 7102818

Not lets assume we've counted up to this point.

Assuming first method we know 3 characters.
7102818 div (256^2) = 108 (ASCII equivlent = l) String = "l"
7102818 - ((256^2)*108) (or 7077888) = 24930
24930 div (256^1) = 97 (ASCII a) String is now "la"
24930 - (97*(256^1) (or 24832) = 98
98 div (256^0) = 98 (ASCII b) String = "lab"
"lab" = source "lab" time to stop...

2nd method -string length unknown and work until 0 add chars to front
7102818 mod (256^1) = 98 (ASCII b) String = "b"
7102818 - (98*(256^1)) = 7102720 (still > 0 keep going)
7102818 mod (256^2) = 24832
24832 / (256^1) = 97 (ASCII a) String = "ab"
7102818 - (97*256^1) = 7077888 (still >0)
7077888 mod (256^3) = 7077888
7077888 / (256^2) = 108 (ASCII l) String ="lab"
7077888 / (108*256^2) = 0 (STOP!)

Haven't checked it math wise, but that should be pretty close...

 

[Kntx]

i'd make a recurisive function till it gets the right deal.

 

[GigaCluster]

Working C++ code here.

The only difference from your spec is that it begins with uppercase letters and ends with lowercase, since that's how it's positioned in the ASCII table. It's trivial to fix, if it matters to you.

To compile, you will either need to download AP College Board's apstring library or adapt the code to some other string class.

Enjoy.

 

[Special K]

Hey Gigacluster, I wrote a solution that works, but it is longer than yours, and in C rather than C++. I was wondering if you could answer a question for me. In your code, you do:

apstring str = "A";

Now I don't know about apstring, but I did mine like this:

char* manipulating_string = (char*)malloc(2);
puts("enter the value for the manipulating string:");
gets(manipulating_string);

Where the user is expected to enter 'a' to initialize the manipulating_string to run through all possible values (a, b.....Z, aa, ab, .... aZ, etc..)
Now why can I not just do

char* manipulating_string = "a"; , similar to what you did?

If I try that, it seems to make the string "read only" and the program crashes when I try to realloc() it and extend its length. Do you know why this happens? Is it possible to initialize a string to a specific value, but still be able to extend it with realloc()?

 

[BFG10K]

This is a pretty easy problem. Basically what you have to make is a base-52 number scheme where each "digit" is a member of the uppercase and lowercase alphabets.

All you have to do is create a variable length string and each time any letter reaches 'Z' set it to 'a' and add one to the previous letter. When all letters reach 'Z' set them all back to 'a' and add another 'a' to the end. Your addition should start from the back and work forward just like it does on regular numbers e.g aaa, aab, aac...aaZ, aba, abb, abc..ZZY...ZZZ...aaaa, aaab etc.

It should be easy to get it to work with iteration (all you need is one simple loop) and that'll be much faster than recursion.

If have time I'll post up the code later.

 

[GigaCluster]

SpecialK: apstring is a class with overloaded operators, so when I do apstring str = "a";, it actually instantiates an object for that string, allocates memory dynamically, and stores the letter(s). You cannot do char* manipulating_string = "a"; because your code does not allocate memory -- it tries to write to some other process's memory, as far as I understand it. Probably realloc() doesn't work for that because it expects already allocated memory. I have never used malloc(), realloc(), and free() in my life, although I know in theory how they work, so these are just educated guesses.

BFG10K: Did you read the entire thread? An iterative solution has been created already.

 

[joshg]

Well I'd like to see an implementation that doesn't use any header files or anything like this, in a simple looped procedure.

I got to thinking about it and I came to a realization: What do you use loops for? Essentially, they do something over and over for you (possibly with different values or fields, etc., whatever you are trying to do) that way you don't have to manually code every single possible instance of events.



With that in mind, I created sort of a "manual process" that I'm going to try and replicate automatically and have it extend itself automatically (written in VBScript syntax since that's the IDE that I happened to have open at the time also, please try not to cringe, remember this is the manual effort that we are trying to automate, so it's supposed to be big and ugly, and easily replaceable by something small ):


Dim CHAR_LIST()

CHAR_LIST = Array("a", "b", "c")

Dim sChar1, sChar2, sChar3, sChar4, sChar5

For Each sChar1 In CHAR_LIST
Debug.Print (sChar1) & vbCrLf
Next

For Each sChar1 In CHAR_LIST
For Each sChar2 In CHAR_LIST
Debug.Print (sChar1 & sChar2) & vbCrLf
Next
Next

For Each sChar1 In CHAR_LIST
For Each sChar2 In CHAR_LIST
For Each sChar3 In CHAR_LIST
Debug.Print (sChar1 & sChar2 & sChar3) & vbCrLf
Next
Next
Next

For Each sChar1 In CHAR_LIST
For Each sChar2 In CHAR_LIST
For Each sChar3 In CHAR_LIST
For Each sChar4 In CHAR_LIST
Debug.Print (sChar1 & sChar2 & sChar3 & sChar4) & vbCrLf
Next
Next
Next
Next

For Each sChar1 In CHAR_LIST
For Each sChar2 In CHAR_LIST
For Each sChar3 In CHAR_LIST
For Each sChar4 In CHAR_LIST
For Each sChar5 In CHAR_LIST
Debug.Print (sChar1 & sChar2 & sChar3 & sChar4 & sChar5) & vbCrLf
Next
Next
Next
Next
Next


... now, in this "manual test example" it's limited to only going up through a 5 charachter permutation. By examining it, it seems as if it's almost a poster child for a recursive function within a loop... I just haven't had time to work out the syntax yet, but hopefully I'll get a bit and tinker with it.

 

[DaveSimmons]

recursion would work, but you can also do this with one outer "while ( ! matched )" loop and one inner loop for the base-52 digits. Think odometer but adding an extra digit wheel when you roll over.