FASTEST way to try all strings (a until ZZZZZZZZZZZZZZZZZZZZZZZZ)

  • Thread starter Thread starter DraguVaso
  • Start date Start date
D

DraguVaso

Hi,

I need to find the FASTEST way to get a string in a Loop, that goes from "a"
to "ZZZZZZZZZZZZZZZZZ".
So it has to go like this:

a
b
....
z
A
....
Z
aa
ab
....
az
aA
....
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ

So it has to try every combination with all the 26 letters, making a
difference between upper case and lower case, and the space (" ") has to be
included too.

Does anybody knows a way to do this?


I do not need this to hack any password or stuff liek this: I'm working with
the SDK of the Belgian governemnet for the electronic identity card. For
some @%£&§*$!! reason these guys made some big mistakes in there
documentation, and used the parameters with the info on a stupid way. Half
of them aren't working.... So the only ways to find out the missing
paramters is:
1. ask them for info, but they seem to be to stupid to knwo anything about
the stuff they made themselves...
2. Try avery combination of letters... So that's what I want to do :-)


I came up with this: but it doesn't work as fast as I want to...

dblBegin = 0
dblEnd = 52 ^ 30
For dblTeller = dblBegin To dblEnd
strT = GiveWord()
TestValue(strT)
txtWord.Text = strT
Application.DoEvents()
Next


Private Function GiveWord() As String
Dim strA As String = ""
Dim dblRest As Double
Dim dblQuotient As Double
dblQuotient = dblTeller
Do
dblRest = dblQuotient Mod 53
'1-26 = a-z
'27-52 = A-Z
If dblRest = 0 Then
dblRest = 32 'space
ElseIf dblRest < 27 Then
dblRest = dblRest + 96
Else
dblRest = dblRest + 38
End If
strA = Chr(dblRest) & strA
dblQuotient = dblQuotient \ 53
Loop Until dblQuotient = 0
GiveWord = strA
End Function
 
DraguVaso said:
I need to find the FASTEST way to get a string in a Loop, that goes from "a"
to "ZZZZZZZZZZZZZZZZZ".
Click to expand...

Even using just 17 characters (unlike the last one you've given below)
there are a ridiculous number of combinations. You just *won't* be able
to test every one of them. With 53 symbols (a-z, A-Z, space) you get
205442259656281392806087233013 combinations.

Assuming you could process 100 *billion* of them every second, it would
still take you 65145313183 years to go through them all. Do you really
have that much time?

Now, as for speeding up what you've got: using a StringBuilder instead
of repeated string concatenation would be a good start. Alternatively
you could use a char array. (I haven't checked your actual algorithm
for correctness, btw.)

I note that you're using 52^30 as the number of possible combinations,
which I don't quite understand if you're including space, but even so,
that makes the length of time taken even greater.

Suppose you have a million computers *each* processing 100 billion
combinations a second, to get through 52^30 combinations I suspect
you'd have to wait until way after the sun had gone cold to see the
end.

In other words: you'll need to find a different way of approaching your
problem...
 
Hehe, well, I found alreaddy some of them that had 4 our 5 characters, but
offcourse, for every character more it would take me exponential more time
to find it out. And I assumed aleaddy I would get very soon to my limit
(getting to 5 characters took already 10 minutes...).

But nevertheless, I've been lucky: The governement doesn't care a lot about
us, but the company that wants to sell to us the card-readers doesn't want
to miss a contract with some of the biggest chains of stores in belgium, and
they gave me the parameters, hehe :-)

In cae somebody else needs them:

ID Keys:
-----------
CardNumber, ChipNumber, BeginValidityDate, EndValidityDate,
IssuingMunicipality, NationalNumber, Name, FirstName1, FirstName2,
FirstName3,
Nationality, BirthPlace, BirthDate, Gender, NobilityTitle, DocumentType,
WhiteCane, YellowCane, ExtendedMinority

Adres keys:
---------------
Street, HouseNumber, BoxNumber, ZIPCode, Municipality, Country

Picture keys:
---------------
Picture


Thanks anyways guys!

Pieter
 
Pieter,

I was busy with it because it is a nice chalenge, I was thinking as well to
the tale of the "grain of rice" when I was busy with it.

I brought it back to 3 in the chalenge however I do not understand you, do
you not need it anymore?

Cor
 
I indeed doesn't need it anymore :-) But thanks anyways for searching!

And me too found it a nice challenge, hehe :-) This is 'real' programming to
me: looking for the most effecient way to find a solution for a logical
problem... I have to adit that I like it a lot more than programming is
now...

In the past it was about intelligence, logical capabilities of the
programmer. now it's jsut about stupid knowloedge, knowing how to do
soemthing and were to find it. Now even idiots can program... :-/
 
Jon,
Just out of curiosity, would you consider a StringBuilder "better" then
simply defining an array of 17 Char that you passed to New String?

As you are continually replacing a single char in the "buffer".

Something like:

Private Shared Sub FindMatch(ByVal chars() As Char, ByVal index As
Integer)
If index = chars.Length Then
Debug.WriteLine(New String(chars))
Else
FindMatch(chars, index, AscW(" "c))
For charCode As Integer = AscW("a") To AscW("z")
FindMatch(chars, index, charcode)
Next
For charCode As Integer = AscW("A") To AscW("Z")
FindMatch(chars, index, charcode)
Next
End If
End Sub

Private Shared Sub FindMatch(ByVal chars() As Char, ByVal index As
Integer, ByVal charCode As Integer)
chars(index) = ChrW(charCode)
FindMatch(chars, index + 1)
End Sub

Public Shared Sub Main()

Dim chars(16) As Char

FindMatch(chars, 0)

End Sub

I would consider inlining FindMatch(char(), integer, integer) for
performance reasons...

Just curious
Jay
 
Jay B. Harlow said:
Just out of curiosity, would you consider a StringBuilder "better" then
simply defining an array of 17 Char that you passed to New String?
Click to expand...

Yes - because it doesn't require creating an extra string each time.
The StringBuilder contains a string which is mutable until you call
ToString on it.
As you are continually replacing a single char in the "buffer".
Click to expand...

That actually suggests an even better strategy: create *and keep* a
StringBuilder, calling ToString on it each time you've finished that
iteration, but then still using it on the next iteration as a
StringBuilder which will automatically create a copy with "mostly" the
right data in.

Of course, if you could get your "test" procedure to work on array of
chars instead of a string, you could have the best of all worlds - a
basically static memory footprint, with no extra objects to create.
 
Jay B.

I think that an array of bytes would in this case be the fastest and also
would help to minimize the used space.

Cor
 
Jon,
Yes - because it doesn't require creating an extra string each time.
The StringBuilder contains a string which is mutable until you call
ToString on it.
Click to expand...
Its the "mutable until you call ToString" part that "confuses" me, hence my
question.

Presumably you would need to call StringBuilder.ToString on each iteration,
as you want to pass the string to another function. Does the StringBuilder
then need to create a new buffer (aka a new "string") so that you can modify
the char, or does it simply call New String(char[]) & copy the existing
buffer.

I was under the impression that it will create a new buffer when you modify
the StringBuilder after calling ToString (copy on write, not copy on read).
Of course, if you could get your "test" procedure to work on array of
chars instead of a string, you could have the best of all worlds
Click to expand...
Yes, that would be the best of both worlds...

Thanks for the thoughts
Jay
 
Cor,
How would saving 17 bytes really be saving anything?

How would an array of Byte be any faster then an array of Char? Especially
when I would expect the function that the OP is calling needs a String? I
agree if the OP's function needed an array of Byte, then an array of Byte is
needed, however the OP suggested Chars (A to Z, a to z and space).

My routine works directly with Unicode Chars there is no encoding involved
(an array of Byte would need an "expensive" Encoding object to convert from
Bytes to Chars or String.

Just curious where you are coming from.

Jay
 
Jay B. Harlow said:
Its the "mutable until you call ToString" part that "confuses" me, hence my
question.
Click to expand...
Presumably you would need to call StringBuilder.ToString on each iteration,
as you want to pass the string to another function.
Yup.

Does the StringBuilder then need to create a new buffer (aka a new "string")
so that you can modify the char, or does it simply call New String(char[]) &
copy the existing buffer.
Click to expand...

ToString itself doesn't create a new buffer; when you next modify the
data it creates a new copy.
I was under the impression that it will create a new buffer when you modify
the StringBuilder after calling ToString (copy on write, not copy on read).
Click to expand...

Yup. I wasn't quite clear - sorry about that.

I guess it ends up being the same as creating a new string from a char
array, keeping the char array between iterations. Sorry - can't have
been thinking properly :(
 
Jon,
ToString itself doesn't create a new buffer; when you next modify the
data it creates a new copy.
Click to expand...
OK, that's what I was thinking.

I guess it ends up being the same as creating a new string from a char
array, keeping the char array between iterations. Sorry - can't have
been thinking properly :(
Click to expand...
I was asking more "stylistically" rather then performance. :-)

The OP would really need to profile it to see which performed better. I
would also watch what impact both had on the GC (I would expect about the
same, as the "buffer" itself should be static.)

Granted this is a somewhat limited scenario, I was just curious what you or
others thought...

Thanks for the info, I knew StringBuilder.ToString was "special", I just
didn't remember...

Thanks
Jay



Jon Skeet said:
Jay B. Harlow said:
Its the "mutable until you call ToString" part that "confuses" me, hence
my
question.
Click to expand...
Presumably you would need to call StringBuilder.ToString on each
iteration,
as you want to pass the string to another function.
Yup.

Does the StringBuilder then need to create a new buffer (aka a new
"string")
so that you can modify the char, or does it simply call New
String(char[]) &
copy the existing buffer.
Click to expand...

ToString itself doesn't create a new buffer; when you next modify the
data it creates a new copy.
I was under the impression that it will create a new buffer when you
modify
the StringBuilder after calling ToString (copy on write, not copy on
read).
Click to expand...

Yup. I wasn't quite clear - sorry about that.

I guess it ends up being the same as creating a new string from a char
array, keeping the char array between iterations. Sorry - can't have
been thinking properly :(
Click to expand...
 
Jay B. Harlow said:
Jon,
OK, that's what I was thinking.

I was asking more "stylistically" rather then performance. :-)
Click to expand...

In that case I'd probably go for the char array.
The OP would really need to profile it to see which performed better. I
would also watch what impact both had on the GC (I would expect about the
same, as the "buffer" itself should be static.)
Click to expand...

Yep, likewise. Indexing an array is probably quicker than indexing a
StringBuilder though.
Granted this is a somewhat limited scenario, I was just curious what you or
others thought...

Thanks for the info, I knew StringBuilder.ToString was "special", I just
didn't remember...
Click to expand...

It's a bit of a shock when you first find out that strings are really
mutable, isn't it?
 
Jay,

I was first going for the arraylist and the the stringbuilder as forever as
you know, however

Pieter told a to z and A to Z and space, that can be done as bytes
97 to 122 and 65 to 90 and 32.

Pieter lives in Belgium which has the same code set as you and me and he
told this explicitly because in Belgium is spoken Dutch and French (a very
small minority German) and the French uses a lot of characters which are not
ASCII however as far as I know in the standard 255 set (maybe can Pieter
tell that).

He told only the characters in the ASCII range so you can be sure that he as
a Belg did that explicitly.

It will be a very huge table so I in my opinion. I once did a test between a
stringbuilder against a bytearray (however silly one because it needed
chars, but somebody told his routine was faster so I made that to tell that
everything can go faster) where the bytearray was twice as fast.

There is in this case for sure only one byte needed instead of two. The only
place you loose some bytes against the characterstring is as far as I can
see when there are spaces at the end, however that will be a minority and
everytime less.

When it would be used, than it should be converted to a string, however
that can even with ASCII in this case. (And this is probably an exception
where this just fit)

I think it will not be that big difference with you method at the moment, it
uses at least than less memory I think and probably go faster.

However just what I thought, never tested, so when I have made mistakes in
this, tell it.

:-)

Cor
 
Cor,
It will be a very huge table so I in my opinion.
Click to expand...
If the OP is going to keep all or most of the entries in a table at one
time, then yes Bytes may be better.

However! I was going on creating one "value" & using it at a time. In which
case 17 Bytes is no "better" then 17 Chars...

Thanks for the additional
Jay
 
Jon,
It's a bit of a shock when you first find out that strings are really
mutable, isn't it?
Click to expand...

Check out:

MarshalAs(UnmanagedType.VBByRefStr)

It allows VB.NET to declare P/Invoke functions such that the String (yes
System.String) itself is modified during the P/Invoke call.

Its mentioned briefly in Adam Nathan's book ".NET and COM - The Complete
Interoperability Guide" from SAMS press, with caveats.

Jay
 
Jay B. Harlow said:
Granted this is a somewhat limited scenario, I was just curious what you or
others thought...
Click to expand...

I had a go at it, using this code:

LFS

Dim chars(19) As Char
Dim tbl(255) As Integer
Dim itm, ch As Integer

chars.Initialize()
For ch = 0 To 19
chars.SetValue(" "c, ch)
Next
chars.SetValue("a"c, 19)

For ch = 1 To 255
tbl(ch - 1) = ch
Next
tbl(33) = 97
tbl(123) = 65
tbl(92) = 32

Do
Label1.Text = CType(chars, String)
Label1.Refresh()

ch = tbl(Asc(CType(chars.GetValue(19), Char)))
If ch = 91 Then
itm = 19
Do While ch = 91
chars.SetValue("a"c, itm)
itm -= 1
If itm = 0 Then Exit Sub
ch = tbl(Asc(CType(chars.GetValue(itm), Char)))
chars.SetValue(Chr(ch), itm)
Loop
Else
chars.SetValue(Chr(ch), 19)
End If
Loop
 
Back
Top