VB6: Best way to find all permutations of a given string in a file - Contest

Also when you submit please use your VBForums name in the submission. I have no idea of who you are without the cross reference.

<assuming you were commenting my post>

But positions are perfectly enough for validation! My results are correct and my method is 100% solid and working; I wasn't speaking about incorrect results at any point. I don't see how you get more correctness by stating, although not literally, that outputting the found permutation alongside position is an absolute requirement.

I get the correct amount of results.
I get the correct positions.

Why I'd need to output more than that?

</assuming you were commenting my post>

The question was asked what is the difference between FindStrIndex and FindStrSearch:

Well the difference are:

FindStrIndex is the output of the file used to create the permutations in the created file.

FindStrSearch is the output from the program used to find the permutation in the created file.

Merri,

The original statement in the original post reads:

I would like to have several category of winners because speed does not always determine the needed solution (some methods won't be able to generate the exact log file but will still be correct).

Meaning if you generate just the offsets that can be verified. That too can be deemed as correct.

Your results (that you provided in the file FindStrSearch.txt) are 100% wrong...rename the file to output.txt and test it with my permutation checker I wrote into my code...all it does is grab the index given in the file and checks for the 4 digits at the end at that exact position...if it doesn't find, it's a fail...mine are 100% :-P

BTW, make sure that the first permutation is the first line, so delete everything before it...otherwise it won't show you :-P

(Edit: Ignore the "100% wrong" bit if you haven't read further down...they're right, but Randem is using 0 as the first byte position, and I was using 1...now both match :-))

Okay, to help people with this a little, I've split my "checker" from the main program and can give that out for people to use themselves...it's a simple enough program, and it expects the filename for output to be output.txt and to have the format:

Code:

---

00000154,fsad
00000169,safd
00000263,fasd
00000839,asdf
00001416,dfsa
00004139,dsaf
00005068,sdfa
00005719,dfas
00006915,asdf
00008984,fads
00009248,fasd
00009852,fdsa
00010081,dsfa
00011051,fdsa
00011640,dasf
00012397,dsfa
00013533,afsd
00013623,sadf
00014368,fsad
00015131,safd
00015764,fasd
00017022,fsad
00017473,asfd
00018037,dafs
00018041,sdfa

---

Currently it crashes if there's no null line (1 vbcrlf) after the last one because that's where it looks to see where the end is...I wrote it for me, so sue me :-P

The file is available at http://download.yousendit.com/F543F2913B9BA07F and it is in a RAR and is available in both compiled and source so you can see for yourself how it works. I have also attached RAR/ZIP version to this post

Randem, I am sure you'll enjoy being able to check the file results with an actual checker that works :-P

(Edit: Deleted the checker...they've been reposted with a minor change to allow for an offset value...randem apparently wants the first byte to be considered 0, <sarcastic>thanks for telling me</sarcastic> :-P)

smUX: switch to output according first character is at zero position. VB's string functions are base one.

Eh? Nothing in the original post suggested to use any base value...first byte = 1 as far as I am concerned :-P

I see what you are saying though, Randem's results would be right if I took that into account (Edit: Confirmed...I allowed for the offset and Randem's results were 100% correct)

So I've uploaded a modified checker which deals with this offset

I've now submitted my code as I didn't see anything I could improve in that version without writing an entirely new code, so I guess this'll be it for me now.

Same here...I can't see any way at all of improving the speed of my code...I have got it down to 1.5 seconds compiled with other stuff running (+0.125 seconds to sort and save the output file) and there *REALLY* isn't any easy way of improving on the code IMO, very little that can actually be done to boost speed :-)

Oh, there is a lot you could do ^_^

I wonder if the code is submitted is the shortest code that has been submitted, what I did was fairly simple.

BTW: Offsets always start at zero, Positions start at one.

To help you guys out some I will make a few comments in the folowing post about code that could help you but I will not use names or references.

1 - It would probably help speed things up if things were defined and all variable were not variants.

It probably wasn't to clear when I mentioned the 64kb boundaries was that the file is to be read in 64kb chunks to process so that it can handle any size file (I will change that, my bad). The final file you may not be able to read the whole file into memory.

That effectively forces to include the file loading into timing :)

All things being equal yes. But everyone will have exactly the same issue.

Yeah, although it doesn't matter much: it only cost me 5 ms or so; I can throw a guess that depending on how others have made their programs, they'll get more timeloss.

Fixing my program wasn't really a problem at all thanks to the way I solved the original problem :)

Same here, I think I can recode my prog to work within a 64k boundary easy enough...however, a boundary like that *will* slow things down :-P

Edit: Interestingly enough, the boundary *GREATLY* sped things up although at the moment the code refuses to work properly. I am getting the right number of permutations but the actual offset values don't seem to be right for some reason and I've no idea why...but as soon as I get the code sorted, it looks good...takes under 0.7 seconds to do the calculations, which is less than half the time it took before :-)

Edit again: Well, it's working 100% now (had to mess about with offset data for each successive block I load in...eventually got it right :-)) and I have written it so the blocksize is variable (you can choose the blocksize to load in each time) and this actually *greatly* improves speed. Four 16k blocks are actually faster than one 64k block, and I've seen speeds of between 500-600ms overall (without closing programs and without using realtime priority)...using realtime priority I got it below 300ms :-)
(all times in this second edit are *without* saving...add 125ms for saving)

Code:

---

The following errors occurred when this message was submitted:

1. smUX has chosen not to receive private messages or may not be allowed to receive private messages. Therefore you may not send your message to him/her.

---

Because I can't contact in other ways, I put it here.


Edit
Then when coming back I notice he is banned.

Yeah, I got that too. Does the words "Banned" under his name have anything to do with this??? Geessh! What happened there???

BTW: Some code submitted is basically uncommented and hard to read. Those are area of the contest as well...

FYI

Yeah, I was banned for "insulting another member"...and to make matters worse they were posting game code in the classic VB forum and the mods *allowed* it saying it's VB code so it's allowed. Trust me, this is the last time I (1) report incorrectly posted posts, (2) actually reply to a post unless I have good reason to do so

I informed the person politely that talking about a tic-tac-toe game in "classic VB" should have been done in the games programming forum and he apologised the first time then did it again, so I wasn't as polite

So, after this contest, don't expect me around here much :-P

I have a question/comment. According to the totals you provided with the sample file there should be 8070 permutations found, but my app is finding more than that. So I compared the result files and mine is counting something like "Dsafd" as 2 where your results is only count it as 1. So I guess the question would be, should this search be case sensitive?

It is case sensitive. Thanks for the idea, I'll make my code have a feature for case insensitivity ^_^

It is case sensitive, but you do have an idea there...

LOL... Let us add more flexibility to our utterly useless function. :D

It's only useless because you haven't thought of a reason to use it.:p

As soon as I think of a reason I let you know ;)

Ok, Time for the second file. For this test I have included a program that will create the exact same file for each of you to test with. I have included the parameters that you will use in the downloaded zip file. There is a verification checksum to insure that you are testing with the same file everyone else is testing with.

Contents of the ReadMe.txt file:

Supplied is a program that will create a permutation file for you to test with
For this test we will use a file with the following parameters:

Permutation String: asdf
Filesize 10mb
Seed: 9756
Permutations Per Buffer: 1000
Verification Checksum: 46774
Blocks 160


Create Permutation File

Good luck. I have already tested this file on some of the current entries and although most of the submissions pass on the 5mb file they severely bomb :eek2: on the 10mb file.

Atleast that file is big enough to cause that most of the time goes to writing the output file :P


Err... did I just blow off my cover?

Actually, No. The way I have it organized it that all the output it to arrays then after that finishes the output goes to the file. That is not to be included in the timing.

Yeah, my prog failed dismally with the new file but that's because it was all variations of asdf and I hadn't set the upper bound for a variable array high enough (was trying to safeguard against memory errors from using too much :-))

However, I adjusted (and way way way overshot) the new setting and ran the test and on my PC with other programs running and not setting priority to realtime I got just under 2.1s...1.25s with priority set. Add another .6s for saving the file :-)

In the case of my program, it works with such small blocks (16k to 64k, settable) that the array in question (which is used for sorting the output later when saving) doesn't need to be excessively large, so I am confident that future "bugs" like this won't be an issue....and I've tested it with all blocksizes on the new file. Randem, expect the new file to be sent to you once I've done a test with a random 100MB file I make with your prog.

And BTW, nice prog...it's a lot simpler than the prog I sent you, and has more features (I didn't think of adding a validation system although I am pretty sure I was considering something similar at one point :-P)

randem: Humm, are you using the flexible function that can take any permutation string (which I have understood means that every character must be different) up to 30 characters or the fixed one in the button that can only do asdf and that's it?


Edit!
Found 1628577 permutations of "adsf" in 1400 (or 1320 in realtime).

Merri: 1.62m results returned? You sure? Randem's own generator program calculates 153k of them, although interestingly enough *my* program calculates 162.9k of them. If I were to explain why mine gives a higher number than Randems, I would say it's because mine allows for one thing most people probably haven't considered (although Merri definitely is smart enough to have :-P)...mine allows for a 4 byte "overhang" between each block in case the string in question happens between the end of one block and the start of another (although I realised a minor bug with this possibly, it *might* have double-counted a result if it occurred at the very end of a block...which I fixed by modifying the overhead length and it doesn't seem to have actually made an effect at all, so it wasn't an issue)

However, I don't think this was the issue because I did a test without using the "overhang" and it returned 162,889 rather than 162,906 (only a difference of 17) using a 16k block and the full 162,906 using a 64k block (which I am assuming Randem used) and I have also written in double and order checking to my own checker built into my prog and the order is fine and there are *no* doubles so Randem's count is wrong (or calculated differently to how we've been told to calculate it...please elucidate :-P) anyway :-)

Edit: BTW I actually added a "double checker" into the main search code, I was sure I had done but couldn't remember...this code checks to see if the next result matches the previously added result and only writes it if it is different to last one...that's why the bug didn't make any difference, because it was double-checking results before writing them :-)

You assume WRONG!!! You must read all that is written. What the program does is to insert KNOWN permutations into the file. Of course as we all know when you generate random data anything can be in there. I only give the count of what I place into the file as a reference. I do state that there could be more...

That is actually the purpose of YOUR program to find them all, No?

True I guess...I had a feeling that you faked the randomness in the file by forcing in instances, although personally I think it should have been 100% random like the random file maker I sent you :-P

Oh, and I might have thought of a use for this method. It could be useful for dictionary compression methods and working out which strings would return the best compression ratios...maybe only useful for word-or-text-based dictionary compression rather than for anything though. I'll probably adapt it to be usable for this sometime. If my code takes 2 seconds to do 24 checks in a 5MB file, imagine how quickly it could scan a 100k file for a max of 10k words and work out which ones are going to give the best compression ratio :-)

Well, I needed some verification that the sequences would actually appear in the file and know exactly where they were so that I could do a quick check to see if any submissions were worth a further look for if they could not find all the known ones they rest would be moot!

Quote:

---

Originally Posted by Merri

Atleast that file is big enough to cause that most of the time goes to writing the output file :P


Err... did I just blow off my cover?

---

You're not alone, Merri. With this newly generated file, my code runs four times as long while outputting data than it does while only counting the permutations. I am also wondering about your 1628577 permutations, because I concur with smUX that there are 162,906 of them. I'm rather curious about your speed, too... I think mine is faster :)

logophobic,

I don't have a submission from you, eh?

Personally I don't think writing to the HD should be included in the time...my prog gives stats both with and without the HD writing, just in case.

However, with the 10MB file, writing it only takes about 0.6s...doesn't add too much to the time :-P

smUX: 1 533 257 known permutations in the file. And I'm very sure the result is correct.

Writing isn't included in timing as randem stated a few posts above. (I have four different versions in my submitted program.)