Here is another project then

[Creosote]

See how many tries and how long it takes you to create a random string of "techimo".

Rules:

• All random strings must contain 7 letters

• All random strings be able to contain any of the 26 letters of the alphabet (meaning, don't make a random num between 1 and 7 and with only t, e, c, h, i, m, o).

• Seed your random number appropriately. No "cheating" to get a head start

• Use whatever language you want

Once you get it debugged and working, then do 3 runs only. Average out the times and iterations it took you to get "techimo."
Post your results, and your code if you want.

[PyroSama]

Why?

[Creosote]

Just thinkin of something to do, going along with the previous thread below this one. If you don't like it, you don't have to do it.


Edit: I gave up after 2.1 billion iterations.

[qball]

gave up?

Let's see:

for 7 char random generated string there are:

26**7 possibilities, that's 8031810176, assuming not generating unique chars, as in "aaaaaaa" is possible.

which is 8.change billion???

just looping through 8031810176 iterations without even DOING anything will probably takes minutes on even the hardiest of hardware.

maybe we should try somehting a little more reasonable like trying "tech" first, then push the envelope to go further...

just doing 4 chars, three tries:

6.599 seconds
1010925 loops

3.215 seconds
445908 loops

2.994 seconds
418538 loops

please note:

for 4 char random generated string there are:

26**4 possibilities, that's 456976

as far as why?

I find this a little more constuctive than 'the most ridiculous way to compute 2+2. One can actually learn something...

[Creosote]

thanks cueball. Actually 4 and 5 characters was nothing as far as time. 7 was in fact, taking well over an hour when I quit. I was using C# however.

But, possibly my method could have been flawed as I was not reseeding my numbers, so it could be possible that I may never generate that string for quite a while depending on what I started with.

Edit:

Here is mine with just using "tech"

403710 iterations, 0.68 seconds
272761 iterations, 0.48 seconds
495914 iterations, 0.89 seconds

Qball, are you sure your seconds figures are right?

[strangerstill]

Hey, this is fun!

I've got it down to 6.83e-08 sec/It (14.64 MIt/s) on my Athlon XP 1700+, using gcc with -O3 -march=athlon-xp for optimizations.

The bottleneck seems to be the rand() calls, they take 4e-08 seconds but only give 31 bits; "techimo" is 7 alphas, just under 33 bits, so even if I wrote my own PRNG it would be constrained by the architecture to 32 bits (bring on the 64-bit processor!)

I tried the simple route of making 2 rand() calls per iteration:

do {
        r1 = rand() % _26_EXP_4;
        r2 = rand() % _26_EXP_3;
        ++iter;
} while ( r1 != tech || r2 != imo );

this works but takes 8.2e-08 seconds per iteration because of the two rand() calls.

so... I spread things out: each rand() call gives 31 bits = 6.60 alphas, I cut that down to 6 alphas (i.e. % _6_EXP_6) and spread 7 rand() calls over 6 iterations by combining them into a single loop:

do {
        r1 = rand() % _26_EXP_6;
        randval = rand() % _26_EXP_6;
        r2 = randval % _26;
        randval /= _26;
        ++iter;
        if ( r1 == techim && r2 == o ) break;

        r1 = randval * _26_EXP_1;
        randval = rand() % _26_EXP_6;
        r1 += randval % _26_EXP_1;
        randval /= _26_EXP_1;
        r2 = randval % _26;
        randval /= _26;
        ++iter;
        if ( r1 == techim && r2 == o ) break;
...
        r1 = randval * _26_EXP_4;
        randval = rand() % _26_EXP_6;
        r1 += randval % _26_EXP_4;
        randval /= _26_EXP_4;
        r2 = randval % _26;
        randval /= _26;
        ++iter;
        if ( r1 == techim && r2 == o ) break;

        r1 = randval * _26_EXP_5;
        randval = rand() % _26_EXP_6;
        r1 += randval % _26_EXP_5;
        randval /= _26_EXP_5;
        r2 = randval;
        ++iter;
        if ( r1 == techim && r2 == o ) break;
} while ( 1 );

this averages at 1 1/6 rand() calls and 6 1/6 arithmetic operations per iteration:
2736114671 iterations, 187.43 seconds, 14.60 MIt/s, 6.85022e-08 s/It.
3591265471 iterations, 245.30 seconds, 14.64 MIt/s, 6.83046e-08 s/It.
6688730912 iterations, 457.80 seconds, 14.61 MIt/s, 6.84435e-08 s/It.

I'm not too sure how to improve this: maybe it can be streamlined a bit or even ( ) rewritten in assembler!

Actually, this is a great problem; it's one bit too complex to manage in a single pass through a 32-bit processor, but test runs take 5-10 minutes - long enough that tweak-compile-run gets annoying but short enough that you get an answer in a reasonable timescale. Nice one creosote!

[Creosote]

Cool. I'm gonna have to try that now, using the 2 random numbers. Stay tuned!

[zskillz]

soo.... what language is that stranger??

-Z

[strangerstill]

It's pure C.

[zskillz]

thx... don't know that at all!... if it's simple (and I assume it is), can you just write a quick java translation of that so that I understand what you're doing?

if not!!! no biggie.

-Z