Word unscrambling

I was wondering how to make a program that would;

1) Read a text file with about ten scrambled words in it, seperated by a line each.

2) Somehow unscrable the words using a wordlist given to me by my tutor, which contains some random words (eg. s4t4sff)

3) Finally, output all of them to a text file, in the form "firstword secondword thirdword etc"

I have been trying to do this for a while now but have failed.

Thanks in advance.

P.S - I have searched the forums numerous times, but haven't really found anything that specific. Thanks again.

Tell us more about the order of the words once the sorting has finished. Do they need to be in alphabetical order, or some other order?

They have to be in the order in which they are written in the text file. For example, the jumbled words would be like this;

word1

word2

word3

And unscrambled would have to look like this;

word1 word2 word3

Thanks for your fast reply!

Your confusing me. In that example, the words are not scrambled. Do you mean something like this:

file.txt - (scrambled)
cat
animal
bear

new_file.txt - (unscrambled)
animal
bear
cat


That would be in alphabetical order...

Quote:

---

eg. s4t4sff

---

Erm that's not a word.

I'm sorry, this is what I mean.

File.txt (scrambled)
atc
malnia
erab

new_file.txt(unscrambled)

cat animal bear

I agree it's confusing, I told my tutor that but he insists :(

Okay, to do that you need instructons from a file so that your program knows how to unscramble.

If not, this would work:

Loop it to switch every two letters. For an example:

Code:

---

int i;
char storage;
for(i = 1; i < FILE_SIZE; i = i + 2)
{
  if(((FileBuffer[i] == ' ') || (FileBuffer[i] == '\0')) || ((FileBuffer[i - 1] == ' ') || (FileBuffer[i - 1] == '\0')))
        continue;
  storage = FileBuffer[i] + 0;
  FileBuffer[i] = FileBuffer[i - 1] + 0;
  FileBuffer[i - 1] = storage + 0;
}

---

It might need a little more help but that should get you started.

So now this:
noe wto htere ofru ifev isx esevn iehgt inen ten

Would look like this:
one two three four five six seven eight nine ten

Hope that helps, August.

Are you allowed to check it against a common dictionary file?

Thats exactly what I mean :)

To Treenef - Yes I know, I meant they are random charactors. I should have explained it better. And he gave me a text file with all the unjumbled "words" (if you can call them that) in it. There are thousands in there.

Ok, so what ideas do you have, I've done this before, but seeing as this is homework, you're going to have to do most of the work.


One other thing. To make this absolutely clear, are there any numbers in the list such as the examples provided by Cool-August?

Code:

---

file.txt - (scrambled)
owr1d
w2odr

new_file.txt - (unscrambled)
word1 word2

---

Well, I know how to read strings from a text file using something like

Code:

---

ifstream b_file

---

But it only reads the first string. I don't know how to make it go to the next one after it has done the first one.

I also know have a low level of understanding how to find all possible combinations of letters from a string. Like tree would be
tree, eert, tere, teer etc. I found this using search.

He also said something like : "make it into an array of null terminated strings." as a hint.

P.S - Yes there are. Some aren't even real words, like 45nws3 and some are just numbers like; 45225

Try somthing like this:

Code:

---

char word[MAX_WORD_SIZE][FILE_SIZE];
ifstream b_file;
int i;
for(i =0; i < FILE_SIZE; i++)
b_file.in >> word[i];

---

Quote:

---

P.S - Yes there are. Some aren't even real words, like 45nws3.

---

Ok, and what is the length of the largest word in your file?
This is a very important question, because you would either be using a permutation generator or a letter frequency counter.

The biggest word is 15 charectors.

Thanks for your help people, it is very appreciated.

Ok since the largest word is of length 15 it means you cannot use a permuation generator...

Do you know what a letter frequency counter is?

Well the file is large so I found the largest one I could (12 charectors) but said 15 to be sure. Sorry if this complicates things I didn't realise how important it is. I though it was like when you declare integers larger then you need to prevent overflows.

No we haven't studied letter frequency counter.

Thanks again.

The reason why the length of the largest word to be unscrambled is important is due to the time complexity problem.

If you are using a brute force, i.e a permutation generator then a word with 12 letters in it would take a long time to solve.

Whereas, with a letter frequency counter can solve any word of any length.

I see. So this means that my program will take along time to solve all ten?

>> I see. So this means that my program will take along time to solve all ten?

That totaly depends.

Yes, since if you use a permutation generator, then by its very nature you are using a brute force algorithm.

The concept of Letter Frequency counting is explained here:

http://www.codeproject.com/cpp/Jumble.asp

Which is initially where I got my idea to create an efficient word unscrambling utility.

Ok. From one of your previous posts, you said to use

Code:

---


char word[MAX_WORD_SIZE][FILE_SIZE];
ifstream b_file;
int i;
for(i =0; i < FILE_SIZE; i++)
b_file.in >> word[i];

---

This is what I think each line means.

First line - Declare a char variable with the size of the largest word and the size of the file with the unscrambled words (i think)

second line - Open the unscramble file
third line - declare i as an integer variable
fourth line - Set i as o, as long as i is smaller then the file size, increase i by 1 each loop
fifth - Not sure. I think it sets the variable "word" to read the next string every loop. Is that right?


P.S - Thanks treenef :D I'll read this page through and hopefuly understand it.

Quote:

---

char word[MAX_WORD_SIZE][FILE_SIZE];

---

Do you have to use char arrays or string literals?


***If you have any problems post them here. I've done this before.

What I'd recommend is you read that link and think about a solution to your problem. When you have given it enough thought. Come back here.

Reading files in and out is not a problem. Worry about that later.

Thank you so much :D This page looks very useful. He didn't specify how to do it, he just told us to do how ever we want :S

I'll do as you said and come back if I need more help. Once again, thank you so much it really is alot to me.

I've run into a problem. At

Code:

---

for (vai = all->begin(); vai != all->end(); vai++, cnt++)                       
cout << cnt + 1 << " " << *vai << endl;                       
char *strcpy ( char ans, const char *vai );                           
ofstream a_file ( "answer.txt", ios::app );
a_file<< *vai <<",";
a_file.close();

---

it messes up. I tried to make it write the answers to the text file, but it always ends up being squares. I think it's becuase it's writing the memory address to the file so I tried writing vai without the asterix. But it wont compile. Does anyone know why?
Thanks in advance

Just hang on a minute there.

Don't use the code from my link. It's perhaps a little too complicated for you anyway.

What I wanted you to do was actually read the concept behind a letter frequency counter.

Here's what you need to think about.

Let's say I give you a word:-

Code:

---

treenef

---

I want you to write a program which will spits out the letter frequency count for a specific word.

So...

Code:

---

t = 1
r = 1
e =3
n =1
f  =1

---

And as I've said before don't worry about file input/output until we've finished this.

No wait, I didn't copy it. I read the whole thing, and got an understanding of it and then tried to make his one do what my one has to do. His one couldn't write it to a file. I am not going to use his one trust me, my tutor would notice :D and I would learn nothing from it. I simply want to know how it would write to a file.

Good, don't use that code.

I said worry about file input/output later...

but here's a link anyway
http://www.cprogramming.com/tutorial/lesson10.html

Quote:

---

Originally Posted by treenef

Good, don't use that code.

I said worry about file input/output later...

but here's a link anyway
http://www.cprogramming.com/tutorial/lesson10.html

---

That's what I was reading!

never mind about that think about the letter frequency counter...

What have you got?

Code:

---

#include <iostream>

using namespace std;

int main()
{
    char array[100]="treenef";
   
    cout<<array[0];
    cout<<array[1];
   
    //letter count prog goes here
   
    cin.get();
    return 0;
}

---

I don't quite understand it, so I'm going to re-read it quick.

Ok. So, is the ctrie part the letter count thing?

Also, do you have msn? It would be easy to talk that way :)

And thanks again for the help :D

ok let's go back to basics:


Do you know how to loop through an array of characters?

So let's say I have an array

char array[100] = "treenef";

Code:

---

+--+--+--+--+--+--+--+
| t|r |e |e |n |e | f|
+--+--+--+--+--+--+--+
 
 0  1  2  3  4  5  6

---

to loop through each character I would do this:

Code:

---

for (int i=0; i<7; i++)
{
  cout<<array[i]<<endl;
}

---

Or better yet

Code:

---

#include <cstring>

size_t len = strlen(array);
for(size_t i = 0; i < len; i ++) {
    cout << array[i] << endl;
}

---

And then, instead of couting the characters, you could count them . . .

Code:

---

#include <climits>
#include <cstring>
#include <cctype>

unsigned charcount[UCHAR_MAX] = {0};
size_t len = strlen(array);

for(size_t i = 0; i < len; i ++) {
    charcount[array[i]] ++;
}

for(int x = 0; x < UCHAR_MAX; x ++) {
    if(charcount[x]) {
        cout << '\'' << isprint(x) ? x : '-' << "': " << charcount[x] << endl;
    }
}

---

Yes I understand that, It would print all 7 charactors stored in the array.

OK, that's good.

So the word treenef...

has three 'e's
one 'f'
one 't'

etc.

Would you know how to write a program to do that?

My first post would [edit]"print all 7 charectors stored in the array"[/edit], and treenef's one would too, but not my most recent one. My previous post would print something like

Code:

---

e: 3
f: 1
n: 1
r: 1
t: 1

---

Quote:

---

Would you know how to write a program to do that?

---

Too late. :)

I see. No I don't think I could. My tutor is looking pretty bad right now. He taught us nothing like that.

To dwk: I'm not sure that I understand your code.

Sorry to be a pain people :(

I see...

Erm in regards to dwks code, it's probably a bit too complicated.

You need something more intuitive...

Have a look at this and see if you understand the concept behind it:

Code:

---

#include <iostream>
#include <string>

using namespace std;

int main()
{
    char array[100]="treenef";
   
    int size = strlen(array);
   
    char alphabet[50]="abcdefghijklmnopqrstuvwxyz";
   
    int letter_count[26];
    for(int i=0; i<26; i++)
    {
        letter_count[i]=0;
    }
       
   
    for(int i=0; i<size; i++)
    {
        for(int j=0; j<=26; j++)
        {
            if(array[i]==alphabet[j])
            {
                letter_count[j]++;
            }
        }
    }           
       
      for(int j=0; j<26; j++)
        {
           
          cout<<alphabet[j]<<" "<<letter_count[j]++<<endl;
           
        }
   
    cin.get();
    return 0;
}

---

Ok I'll try to explain your code to show how much I understand.

Code:

---


char array[100]="treenef"; //Declares a charactor array called array,
 of 100 bytes and saves treenaf into it
   
    int size = strlen(array); //Declares an integer called size,
 Then it assigns its value as the length of the array called array
   
    char alphabet[50]="abcdefghijklmnopqrstuvwxyz"; // Declares
 a charactor array called alphabet, of 50 bytes. Then it saves the aphabet into it.
   
    int letter_count[26]; // Declares an integer called letter_count, consisting of 26 bytes.

    for(int i=0; i<26; i++) // A loop. It creates an integer called i
and assigns it a value of 0. It then says that as long as i is under
26 to run the next code. The i++ makes the integer i increase by 1 each loop.

    {
        letter_count[i]=0; // Im not sure. It looks like it assigns each

 letter of the alphabet to 0?
    }
       
   
    for(int i=0; i<size; i++) //Another loop. Assigns integer i to 0,
loops if i is under the variable size, and i increases by 1 each loop.


    {
        for(int j=0; j<=26; j++) //Another loop. Sets j to 0, loops if j
is bigger or equal to 26, j increases by 1 each loop

        {
            if(array[i]==alphabet[j]) //Hrm. Another loop, if value i
array is eqaul  to alphabet value j then do the next code.

            {
                letter_count[j]++; //Not sure
            }
        }
    }           
       
      for(int j=0; j<26; j++) //Same as the one above
        {
           
          cout<<alphabet[j]<<" "<<letter_count[j]++<<endl; // Print
the alphabet value j, a space, then the letter_count j. Not sure
what this means.
           
        }
   
    cin.get();
    return 0;
}

---

Hrm, I understand quite a bit (I think, and hope) but theres still a
bit I don't quite get. Sorry about the way its layed out :S

Yeah some of what u got is right some wrong.

Draw out a flow chart to and follow each bit with your finger.

Think about it for a day or so and then come back. I'll explain any stuff you don't understand

I've got to go now.

However, you should be able to see the reason why a letter frequency count is useful for your problem.

Code:

---

treenef,  feneert,  eertnef,

---

All have the same letter frequency count.

Ok thanks. I understand why I need it now. Thanks for all the help. If I need more I'll come and ask, as for now, I got some learning to do!

Thanks and bye people.
Thanks alot treenef, your help has been invaluable, so was everyone elses.