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 ![]() ![]() |
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.
That said... learn to use the power of the Standard Template Library.
|
Author: | md [ Thu May 12, 2005 1:22 pm ] | ||||
Post subject: | |||||
Here's the code for reference:
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:
**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 ![]() 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 ![]() ![]() |
Author: | md [ Thu May 12, 2005 2:16 pm ] | ||||||||||||||
Post subject: | |||||||||||||||
Sure
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 ![]()
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.
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:
now after the first line of the swap:
the second:
and the third:
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 ![]() |
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:
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:
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.
Declares a pointer to a boolean.
Allocates a block of memory that can hold "max + 1" boolean values.
Then frees that block of memory.[/quote] Your time really would be well-spent figuring out how to use the STL as I did. ![]() |
Author: | wtd [ Thu May 12, 2005 3:14 pm ] | ||
Post subject: | |||
A good example of the STL in action: Cornflake was talking about swapping.
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 ![]() 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
![]() 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. ![]() |
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...
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. ![]() |
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. |