Javascript 16 Help (I have the code, but it's slow, any ideas how to speed it up)
Well, I basically converted the javascript algorithm in this mission to C++, and it surprisingly works. But it's kind of slow, does anyone have any ideas how to speed it up? My code:
#include <cstdlib>
#include <iostream>
#include <string>
void Sleep(clock_t wait)
{
clock_t goal;
goal=(wait*CLOCKS_PER_SEC)+clock();
while (goal>clock())
{}
}
using namespace std;
string tab = "azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789_$&#@";
string entry;
string word;
string tocheck;
string wordreturn;
int sum;
int n;
int index;
int main()
{
for (int a=0;a<tab.size();a++)
{
entry=tab[a];
for (int b=0;b<tab.size();b++)
{
entry+=tab[b];
for (int c=0;c<tab.size();c++)
{
entry+=tab[c];
for (int d=0;d<tab.size();d++)
{
entry+=tab[d];
for (int e=0;e<tab.size();e++)
{
entry+=tab[e];
for (int f=0;f<tab.size();f++)
{
entry+=tab[f];
for (int g=0;g<tab.size();g++)
{
entry+=tab[g];
n = entry.length();
sum = 1;
for(int i=0;i<n;i++)
{
index = tab.find(entry[i]);
sum += (index*n*i)*(index*i*i);
}
if(sum==88692589)
{
ofstream found("found.txt");
found << entry;
found.close();
while (true)
{
cout << "Match Found: \a" << entry << endl;
sleep((clock_t) 600)
}
}
else
{
cout << "No Match for Entry: " << entry << " : " << sum << endl;
}
}
}
}
}
}
}
}
system("PAUSE");
return EXIT_SUCCESS;
}
looks like the length of that character array (tab) is constant, so the easiest way to gain yourself a speedup on this would be to make a size variable to replace tab.size(); in each of your for loops.
the way it is now, the for loop has to call up the size() function for the comparison each time it cycles through the loop, and you have a lot of nested loops, so that eats up some time.
also, be aware that printing (e.g. cout) takes up a lot of time.
EDIT: you should edit your post to disable smileys
ynori7 wrote: looks like the length of that character array (tab) is constant, so the easiest way to gain yourself a speedup on this would be to make a size variable to replace tab.size(); in each of your for loops.
the way it is now, the for loop has to call up the size() function for the comparison each time it cycles through the loop, and you have a lot of nested loops, so that eats up some time.
also, be aware that printing (e.g. cout) takes up a lot of time.
That was a good idea, changing the tab.size() I changed it around a tiny bit to this, but do you think the tab.erase() is too slow or what, because I couldn't think of any other way to not have to reset the string every time the for(int g) loop runs.
#include <cstdlib>
#include <iostream>
#include <string>
#include <fstream>
void Sleep(clock_t wait)
{
clock_t goal;
goal=(wait*CLOCKS_PER_SEC)+clock();
while (goal>clock())
{}
}
using namespace std;
string tab = "azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789_$&#@";
string entry;
string word;
string tocheck;
string wordreturn;
int sum;
int n;
int index;
int main()
{
for (int a=0;a<67;a++)
{
entry=tab[a];
for (int b=0;b<67;b++)
{
entry.erase(1,7);
entry+=tab[b];
for (int c=0;c<67;c++)
{
entry.erase(2,6);
entry+=tab[c];
for (int d=0;d<67;d++)
{
entry.erase(3,5);
entry+=tab[d];
for (int e=0;e<67;e++)
{
entry.erase(4,4);
entry+=tab[e];
for (int f=0;f<67;f++)
{
entry.erase(5,3);
entry+=tab[f];
for (int g=0;g<67;g++)
{
entry.erase(6,2);
entry+=tab[g];
for (int h=0;h<67;h++)
{
entry.erase(7,1);
entry+=tab[h];
n= 8;//entry.length();
sum=1;
for(int i=0;i<n;i++)
{
index = tab.find(entry[i]);
sum += (index*n*i)*(index*i*i);
}
if(sum==88692589)
{
ofstream found( "found.txt" );
found << entry;
found.close();
while (true)
{
cout << "Match Found: \a" << entry << endl;
Sleep((clock_t) 600);
}
}
else
{
cout << entry << endl;
}
}
}
}
}
}
}
}
}
system( "PAUSE" );
return EXIT_SUCCESS;
}
devilsson2010 wrote: while (true) { cout << "Match Found: \a" << entry << endl; Sleep((clock_t) 600); } } else { cout << entry << endl; }
i dont see any easy way around the .erase() method, but you should get rid of all that stuff i put in the quote above. if you find a match, it gets put into a text file, and you can just open the file when the program is done if you want to see the results. and you have no reason to see the wrong answers, so printing that just wastes time.
devilsson2010 wrote: I get what you're saying, but I want to see where it's at in its loop, because otherwise you don't know how far along it is and it is just a black screen, which isn't too useful. just have it tell you when it's done. removing the prints will give you at least a 5 times speedup, probably more.
devilsson2010 wrote: Even without that, my code seems slow compared to the 200,000+ words a second other people on the forums said they were getting. What would the reason for that be? probably has to do with the fact that you have 10 nested loop. i'm too lazy to really read through the code to see what it's doing, so i couldnt really say how to write it better.
heres some pseudo code on how to do it with out the nested loops
TabMax= tab..length-1
EntryMax= entry.length-1
firstchar= tab(0)
lastchar = tab(TabMax)
do
For I = 0 to TabMax
Entry[i]= tab[i]
if Check(entry)=true
save(entry)
end if
next
for I = 0 to EntryMax
if entry[i]=lastchar then
if not i = entry max then
entry[i]=firstchar
else
exit do
end if
else
index = tab.indexOf(entry[i])
entry[i]=tab[index+1]
end if
next
loop
bool Check(entry)
return GetCheckSum(entry)=CheckSum
In any case, just bruteforcing this is not going to work. Base on my research on this so far, the password is 12 characters long. anything under 10 characters long does not porduce a high enough check sum. 10 characters will but every single checksum ends with a zero. and none of the comininations 11 characters long will end up with 89 at the end. So are 12 or 18 characters long. 18 is just way to insane (or so I think) so I am going off a 12 character long password.
Based on a 12 character password.
-
You need to code your bruteforcer so it skips out on the quadrillions upon quadrillions of entries that can in no way possibly add up to the checksum. for example in order for a string of 12 a's to be altered to reach the checksum the 9th charcter needs to be incremented to Q. You app logic needs to skip all those bad combinations
-
Once you have done that, you will still have over 2 quadrillion possible combinations that equal this checksum. Where to go from there I am lost.
devilsson2010 wrote: Very mathematical, you deserve a cookie
I Like Cookies :)
Ok, I have no clue what language you program in, but it's confusing the shit out of me. Can you put it in C++ friendly terms :happy:.
I program in VB.NET, but that was just pseudo code…, I am not a C++ guy, so some brainiac out there can probably make this better, please feel free to add your suggestions /comments
Standard C++
#include "stdafx.h" #include <string.h>
int _tmain(int argc, TCHAR* argv[]) { char tab[] = " azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789$&#@"; char chars[] = "azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789"; char nextChar[] = "zertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789"; char entry[] = "aaaaaaaaaaaa"; __int32 tabLen = strlen(tab); __int32 tabMax= strlen(tab)-1; __int32 entryLen= strlen(entry); __int32 entryMax= strlen(entry)-1; char firstChar= tab[0]; char lastChar = tab[tabMax];
while (true) {
for (__int32 i = 0; i < tabLen; i++) {
entry[i]=chars[i];
/*
//TODO: Implement your own methods for checking the sum
if (check(entry) == true)
{
//TODO: Implement your own methods for saveing the entry
save(entry);
}*/
}
for(__int32 i = 0; i < entryLen; i++) {
if (entry[i]==lastChar) {
if (!i == entryMax) {
entry[i]=firstChar;
continue;
}
else {
//exit while;
break;
}
}
else {
entry[i]= nextChar[i];
}
}
}
return 0;
}
bool check(const char *s) { return false; } void save(const char *s) {
}
Thanks much :D, I'm about to go to bed but I'm going to see if I can get it working first, I'll tell you how it goes.
Edit Again:
I changed that code a lot. It seemed like there was some unnecessary stuff in there that made the program not work i.e:
entry[i]=chars[i];
{check(entry);}```
Alls this does is add every char from chars[] to entry, extremely pointless.
This is what I've come down to:
```markupwhile (entry!="999999999999")
{
for (__int32 i=0;i<tabLen;i++)
{
for (__int32 a=0;a<entryLen;a++)
{
Check(entry);
if (entry[a]==lastChar)
{entry[a]=firstChar;
break;
} else {
entry[a]=nextChar[i];}
}
}```
It doesn't work correctly though, it changes each character in entry sequentially with the next char in tab. It sounds fine but it outputs something like this:
```markupaaaaaaaaaaaa
zaaaaaaaaaaa
zzaaaaaaaaaa
zzzaaaaaaaaa
zzzzaaaaaaaa
zzzzzaaaaaaa
zzzzzzaaaaaa
zzzzzzzaaaaa
zzzzzzzzaaaa
zzzzzzzzzaaa
zzzzzzzzzzaa
zzzzzzzzzzza
zzzzzzzzzzzz
ezzzzzzzzzzz
eezzzzzzzzzz
eeezzzzzzzzz
eeeezzzzzzzz
eeeeezzzzzzz
eeeeeezzzzzz
eeeeeeezzzzz
eeeeeeeezzzz
eeeeeeeeezzz
eeeeeeeeeezz
eeeeeeeeeeez
eeeeeeeeeeee
reeeeeeeeeee
rreeeeeeeeee
rrreeeeeeeee
rrrreeeeeeee
rrrrreeeeeee
rrrrrreeeeee
rrrrrrreeeee```
And that obviously isn't checking for every possible combination. I still don't completely get what you were going for with the code, it doesn't seem doable. But it was a great starting point :happy:.
ok you are missing alot of things here, I didn't in all of the blanks to begin with, but maybe you'll do better with this.
#include "stdafx.h"
#include <iostream>
#include <string.h>
char chars[] = "azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789";
__int32 charLen = strlen(chars);
__int32 charMax= strlen(chars)-1;
char getNextChar(const char c) {
int i;
for (i=0; i < charMax; i++) {
if(chars[i]== c) {
return chars[i+1];
}
}
return '\0';
}
int _tmain(int argc, _TCHAR* argv[]) {
char tab[] = " azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789_$&#@";
char nextChar[] = "zertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789";
char entry[] = "aaaaaaaaaaaa";
for (__int32 i = 0; i < 12; i++) {
entry[i] = 'a';
}
__int32 tabLen = strlen(tab);
__int32 tabMax= strlen(tab)-1;
__int32 entryLen= strlen(entry);
__int32 entryMax= strlen(entry)-1;
char firstChar= chars[0];
char lastChar = chars[charMax];
bool done=false;
while(!done) {
for (__int32 i = 0; i < charLen; i++) {
entry[0]=chars[i];
/*
//TODO: Implement your own methods for checking the sum
if (check(entry) == true)
{
//TODO: Implement your own methods for saveing the entry
save(entry);
}*/
}
for(__int32 i = 0; i < entryLen; i++) {
if (entry[i]==lastChar) {
if (!(i == entryMax)) {
entry[i]=firstChar;
entry[i+1]= getNextChar(entry[i+1]);
}
else {
//exit while;
//break;
done=true;
}
}
}
}
return 0;
}
bool check(const char *s) {
return false;
}
void save(const char *s) {
}