Word Scrambler

[jamonathin]

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 . Here it is, and if anyone knows a faster way, I'm curious to know

[wtd]

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; }

[md]

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...

[jamonathin]

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

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 ] It'd be greatly appreciated.

[md]

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 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 If you want I can explain the theory behind it, but I'll need to revise the code a bit first.

[wtd]

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.

[wtd]

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.

[md]

Yeah, but that's not nearly as fun as doing it the hard way

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

[wtd]

Cornflake wrote:

Yeah, but that's not nearly as fun as doing it the hard way

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.

[jamonathin]

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 .

Thanks again for your help guys.

[wtd]

Any program you write in C++ will be a good exercise in proper coding style.