Computer Science Canada

Word Scrambler
Author:  jamonathin [ Thu May 12, 2005 8:59 am ]
Post subject:  Word Scrambler
This is a program that scrambles up a word (obviously). It slow though. The max amount of letters it does in a resonable amount of time is 4 Confused . Here it is, and if anyone knows a faster way, I'm curious to know Smile
Author:  wtd [ Thu May 12, 2005 12:16 pm ]
Post subject: 
For one thing, when you're doing a lot of string concatenation (+=), don't. Instead use a stringstream.

You're using string constants where you just have characters. Don't.

You're using C-style casts. Don't.

You're using ints where you want boolean values. Just use bools.

So, wihout changing too much else logic-wise, let's look at this function.

c++:
#include <sstream>

int mix (string thing)

{

    int l(thing.length());

    int hold;
    bool taken[l];

    stringstream scramble;

   

    cout << "Please Wait ";

   

    for (int i (1); i <= l; ++i)

    {

        taken[i] = false;

    }


    for (int q (1); q <= l; ++q)

    {

        while (true)

        {

             srand(static_cast<unsigned>(time(NULL)));

             hold = rand() % l + 0;

             

             if (taken[hold])

             {

                   scramble << thing[hold];

                   taken[hold] = true;

                   cout << '.';

                   break;

             }

         }

     }       

     cout << endl << scramble.str();

}


That said... learn to use the power of the Standard Template Library.

c++:
#include <string>
#include <algorithm>
#include <iostream>

int main()
{
   std::string input;
   std::cin >> input;
   std::random_shuffle(input.begin(), input.end());
   std::cout << input << std::endl;

   return 0;
}
Author:  md [ Thu May 12, 2005 1:22 pm ]
Post subject: 
Here's the code for reference:
c++:


int mix (string thing)
{
    int l = thing.length();
    int hold, taken [l];
    string scramble = "";
   
    cout << "Please Wait ";
   
    for (int i (1); i <= l; i++)
    {
        taken[i] = 0;
    }
    for (int q (1); q <= l; q++)
    {
        while (true)
        {
             srand((unsigned)time(NULL));
             hold = (rand() % (l))+ 0;
             
             if (taken [hold] == 0)
             {
                   scramble += thing [hold];
                   taken [hold] = 1;
                   cout << ".";
                   break;
             }
         }
     }       
     cout << "\n" << scramble;
}


Now you mentioned it being slow, thats because of how your rearanging the string. By getting a random character, and then seeing if it's been used before your basically increasing the chance that you'll have to chose again the fewer choices there are left.

Here's a much better randomizing algorythm (which can be modified for almost any data set), that runs in linear time:

c++:

void Randomize(string &s)
{
        int min = 1, max = s.length();      // max and min for rand
        bool *flagged = new bool[max+1];           // flags to know if the character has been swapped already
        int current = 1, swap;            // swap indicies
        char tmp;                                          // temprary character buffer
       
        for(int i = 0; i <= max; i++)          // clear the flagged array
                flagged[i] = false;

        while(current <= max)             // while we're not at the end of the string
        {
                if( !flagged[current])            // if the current character has not already been swapped
                {
                        swap = (rand() % (max-min))+min;        // get a random swap index
                        tmp = s[current];                            // save teh current character
                        s[current] = s[swap];            // copy the swap character
                        s[swap] = tmp;          // copy the original character
                        flagged[swap] = true;
                }

                current++;                                    // increment the current index
        }

        delete [] flagged;                                    // get rid of the array, leaks are bad
}



**I HATE how tabs are always messed up...
Author:  jamonathin [ Thu May 12, 2005 1:49 pm ]
Post subject: 
wtd:
Im not too sure what stringstream does, im guessing it makes it easier to play with string variables, but how?

Im guessing that scramble << thing [hold] is the same as the += when using stringstream

And now do we have to use scramble.str(); when we cout becasue we're using stringstream?

One last thing, What C-Style casts did I use, so I don't do them in the future (i know nothing about C)

Cornflake:
Can you explain this to me a little more bool *flagged = new bool[max+1]; Just what the *flagged means and how it can be equal to new bool [max+1], which is 1 + the length of the string, like why we use new bool.

Not too sure what (string &s) means Confused

And pretty much everything in the if statement. I know we first get a random number, then im lost on how that stuff makes a new scrambled word.


If you guys could help me out [again Razz ] It'd be greatly appreciated. Smile
Author:  md [ Thu May 12, 2005 2:16 pm ]
Post subject: 
Sure
c++:

bool *flagged = new bool[max+1];

Means we want a pointer to a boolean, and we're assigning the pointer the address of a dynamically created array of booleans of size max+1. Basically this is how you get dynamically sized arrays, the code you gave actually doesn't compile Wink Since we're allocating memory for this array we need to be sure to deallocate it when we're done with it also which is what
c++:

delete [] flagged;
does. Delete the array starting at flagged.

Pointers are an advanced part of the language, so reading up on them is probably a good idea before trying to modify my code.

Ok, so flagged is an array of booleans where flagged[0] through flagged[max] are all valid positions.

string &s means that s is a reference to the variable that you pass, so that any changes we make to s are made to the original varaible as well.

c++:

swap = (rand() % (max-min))+min;        // get a random swap index
tmp = s[current];                                  // save teh current character
s[current] = s[swap];                            // copy the swap character
s[swap] = tmp;                                     // copy the original character
flagged[swap] = true;


This is actually strait forward if you can visualize it; basically we chose a random position between the current character and the end of the string and we swap the current character and that character.

Line 1 gets a random character, lines 2 through 4 do the swap, and line 5 sets flagged to true for the swaped character so we don't move it again later.

To see how the swap works make a table with three columns one for s[current], one for s[swap] and one for tmp.

Here's the startign state:
code:

s[current]  |  s[swap]  |  tmp  |  line #
=========================
a              |     b         |          |   start

now after the first line of the swap:
code:

s[current]  |  s[swap]  |  tmp  |  line #
=========================
a              |     b         |         |   start
a              |     b         |   a     |   1

the second:
code:

s[current]  |  s[swap]  |  tmp  |  line #
=========================
a              |     b         |         |   start
a              |     b         |   a     |   1
b              |     b         |   a     |   2


and the third:
code:

s[current]  |  s[swap]  |  tmp  |  line #
=========================
a              |     b         |         |   start
a              |     b         |   a     |   1
b              |     b         |   a     |   2
b              |     a         |   a     |   3

As you can see after the third line s[current] and s[swap] have been exchanged.

the flagged[swap] = true part is basically for efficency. But as I didn't really think to hard on it it actually only helps a little Embarassed If you want I can explain the theory behind it, but I'll need to revise the code a bit first.
Author:  wtd [ Thu May 12, 2005 3:11 pm ]
Post subject: 
jamonathin wrote:
wtd:
Im not too sure what stringstream does, im guessing it makes it easier to play with string variables, but how?

Im guessing that scramble << thing [hold] is the same as the += when using stringstream

And now do we have to use scramble.str(); when we cout becasue we're using stringstream?


C++ strings (using the std::string class) are immutable. Thus we can't just add something onto the end of an existing string. Instead we have to add the new string to the old string, which gives us a new string, then assign that string to the variable. This allocates new objects and costs CPU and memory.

To get the effect of mutable strings (and other benefits), we can use the std::stringstream class. This avoids unnecessary creation of extra objects.

The "str()" method of the stringstream class gets the current std::string representation of the stringstream.

jamonathin wrote:
One last thing, What C-Style casts did I use, so I don't do them in the future (i know nothing about C)


C-style casts are like:

code:
double d(42.3);
int i((double)d);


These are fraught with peril since they avoid a lot of sane checks on whether or not the cast is even appropriate. Instead, we generally use:

code:
double d(42.3);
int i(static_cast<double>(d));



jamonathin wrote:
Cornflake:
Can you explain this to me a little more bool *flagged = new bool[max+1]; Just what the *flagged means and how it can be equal to new bool [max+1], which is 1 + the length of the string, like why we use new bool.


There are no true arrays in C or C++. There are only pointers to blocks of memory.

code:
bool *flagged


Declares a pointer to a boolean.

code:
new bool[max + 1]


Allocates a block of memory that can hold "max + 1" boolean values.

code:
delete [] flagged;


Then frees that block of memory.[/quote]

Your time really would be well-spent figuring out how to use the STL as I did. Smile
Author:  wtd [ Thu May 12, 2005 3:14 pm ]
Post subject: 
A good example of the STL in action:

Cornflake was talking about swapping.

c++:
#include <algorithm>

int main()
{
   int a(1), b(2);

   std::swap(a, b);

   return 0;
}


Yes, it really is that easy.
Author:  md [ Thu May 12, 2005 7:54 pm ]
Post subject: 
Yeah, but that's not nearly as fun as doing it the hard way Razz

And it's not that arrays are not defined in C and C++, it's just that their really just shortcuts to pointer arithmatic.
Author:  wtd [ Thu May 12, 2005 8:10 pm ]
Post subject: 
Cornflake wrote:
Yeah, but that's not nearly as fun as doing it the hard way Razz

And it's not that arrays are not defined in C and C++, it's just that their really just shortcuts to pointer arithmatic.


Well, real arrays have things like bounds checking. Smile
Author:  jamonathin [ Fri May 13, 2005 12:03 pm ]
Post subject: 
Thanks for all your helps guys. I shoudl have just looked a lil harder at the swap, cuz now I see and I realize how simple and straight forward it really is...
code:
hold = x
x = y
y = hold

And everything you guys said makes a lot of sense, now I just need to come up with some ideas of useless programs that could use that stuff you guys showed me. If you guys have any ideas of some that'd be great. I couldn't care less what the idea is, i juss need to practice it now Razz .

Thanks again for your help guys. Smile
Author:  wtd [ Fri May 13, 2005 1:10 pm ]
Post subject: 
Any program you write in C++ will be a good exercise in proper coding style.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy