195 - Anagram

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 » Thu Jul 04, 2002 6:43 am

Thanks
now i understand what the problem is saying regarding the order of the elements.

I could handle it by writing a function.

But in my latest prog since i am storing all the strings hence it gives segmentation fault as i increase MAX1 to store all the strings,say of elements >9.

I will have to follow your advice by modifying my comb() .
I will try to use your advice.
Thanks again

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 » Thu Jul 04, 2002 12:09 pm

THANKS TO ALL OF U .
I have solved the problem with just presentation error( i always get this).

Few days back,I had posted my prog for prob 124 in this volumeI forum.
Now I will try to put this algo in that prob also

I had also tried to do Prob no 101 but failed.
I had put my problem (prog) in this forum.
But till now, no one has helped me.
Please also help me in doing that prob.

Special thanks for picard

waffle
New poster
Posts: 1
Joined: Sat Jul 06, 2002 10:09 pm

195 - Too slow.

Post by waffle » Sat Jul 06, 2002 10:14 pm

As far as I can tell, my program for 195 does everything it needs to do, including removing redudant entries and getting the correct sorting. However, it is much too slow. Can anyone help me fix my algortihm?

[cpp]/* @JUDGE_ID: 20852KJ 195 C++ "Recurse+Kludges" */

#include <iostream>
#include <string.h>
#include <string>
#include <set>

using std::string;

struct cmp
{

bool
operator () (const string one, const string two) const
{
return (one < two);
}
};

set < string, cmp > THESET;


void
clearlist ();
void
addlist (string x);
bool
checklist (string x);
/*string
list[5000];
int
list_index =
0;
*/

int
compare (string one, string two);

void
anagram (string pre, string post);

int
main ()
{
int
number;
string input[100];
cin >> number;
int
length;
int
i,
j,
z,
y;
string
min;
char
temp;

if (number < 0)
{
cout << "negative number of words to do?!?!?!" << endl;
return (0);
}
// Get inputs
for (i = 0; i < number; i++)
{
cin >> input;
}

//Sort inputs.
for (i = 0; i < number; i++)
{
for (int z = 0; z < input.size () - 1; z++)
{
y = z;
min = input.substr (y, 1);
for (j = z + 1; j < input.size (); j++)
{
if (compare (min, input.substr (j, 1)))
{
y = j;
min = input.substr (y, 1);
}

}
input[y] = input[z];
input[z] = min[0];
}

}
//Process and do output
for (i = 0; i < number; i++)
{
clearlist ();
anagram ("", input);
}
}


void
anagram (string pre, string post)
{
int
i,
j;
string one, two, temp;
if (post.size () > 2)
{
for (i = 0; i < post.size (); i++)
{
one = pre;
one += post.substr (i, 1);

two = post;
two.erase (i, 1);


// If string = ABCD, call Anagram 4 times:
// anagram(A, BCD)
// anagram(B, ACD)
// anagram(C, ABD)
// anagram(D, ABC)
//
// anagram(A, BCD) would call these:
// anagram(AB, CD)
// anagram(AC, BD)
// anagram(AD, BC)

anagram (one, two);
}
}
else if (post.size () == 2)
{
// Base case. POST is 2 characters.
// Display PRE+POST and then PRE+(reversed POST)

temp = pre + post;


if (checklist (temp) == false)
{
cout << temp << endl;
addlist (temp);
}

temp = pre + post[1] + post[0];

if (checklist (temp) == false)
{
cout << temp << endl;
addlist (temp);
}
return;
}
else
{
cout << "undefined";
}
}

int
compare (string one, string two)
{
char
a,
b;
a = one[0];
b = two[0];
if (toupper (a) != toupper (b))
return (toupper (a) > toupper (b));
else
return (a > b);

}



void
clearlist ()
{
THESET.clear ();
}

void
addlist (string x)
{
THESET.insert (x);
}

bool
checklist (string x)
{

set < string, cmp >::iterator it = THESET.find (x); // O(Log N) or O(N)??
// Hash table would
// provide O(1).
if (it == THESET.end ())
return false;
return true;
}
[/cpp]

irmen
New poster
Posts: 5
Joined: Sat Jul 13, 2002 11:05 pm

195: anagram, wrong answer

Post by irmen » Sat Jul 13, 2002 11:09 pm

Hi I keep getting "wrong answer" although I'm pretty sure my output is correct. What do I miss here?

I've kludged with the input code to accept even empty lines (empty words) but this didn't help.

Here's my program:
(as you see, it uses STL algorithms, so there should be nothing wrong with the algorithm)
[cpp]
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>

using namespace std;


int main(int argc, char** argv)
{
int amount;
cin >> amount;
cin.get();

for(int i=0; i<amount; ++i)
{
char buf[10000];
cin.getline(buf,'\n');
string word(buf);

sort(word.begin(), word.end());

cout << word<<endl;
while(next_permutation(word.begin(),word.end()))
{
cout <<word <<endl;
}
}

return 0;
}
[/cpp[/cpp][/code]

rascle
New poster
Posts: 20
Joined: Wed Mar 06, 2002 2:00 am

Post by rascle » Sun Jul 14, 2002 6:38 am

Sorry,my program language background is poor.
So I can't understand you code.

But the only problem that I ran into is the sequence is

A<a<B<b<C<c.....<Z<z

Wish this suggestion can help you ....

irmen
New poster
Posts: 5
Joined: Sat Jul 13, 2002 11:05 pm

sorting... that must be it

Post by irmen » Sun Jul 14, 2002 1:21 pm

Argh ofcourse now I'm reading the problem description again,
and I see my sorting is not quite right :P Thanks

(edit)
GRR :evil: I changed the sorting and still a Wrong Answer.
with input: 1 aabB my program outputs:
aaBb
aabB
aBab
aBba
abaB
abBa
Baab
Baba
Bbaa
baaB
baBa
bBaa

I think I covered all cases here: my program accepts empty
words, it doesn't print duplicates when letters occur >1x, and the sorting
is correct, right? (A<a<B<b<....<Z<z). What else is going on!?

rascle
New poster
Posts: 20
Joined: Wed Mar 06, 2002 2:00 am

Post by rascle » Sun Jul 14, 2002 3:49 pm

The last thing I can thought is ....

" Initialize.."

You can try these cases

3
aaBBe
bb
eeeb

At my first time,"bb" case has five characters.

irmen
New poster
Posts: 5
Joined: Sat Jul 13, 2002 11:05 pm

Post by irmen » Sun Jul 14, 2002 4:00 pm

Initialization is ok,
rascle wrote:You can try these cases

3
aaBBe
bb
eeeb
I get the following output with this test case:

aaBBe
aaBeB
aaeBB
aBaBe
aBaeB
aBBae
aBBea
aBeaB
aBeBa
aeaBB
aeBaB
aeBBa
BaaBe
BaaeB
BaBae
BaBea
BaeaB
BaeBa
BBaae
BBaea
BBeaa
BeaaB
BeaBa
BeBaa
eaaBB
eaBaB
eaBBa
eBaaB
eBaBa
eBBaa
bb
beee
ebee
eebe
eeeb


This is correct, right? I'm beginning to think there is something fishy in the input test case of the judge, that breaks my program... but what? I can accept 10,000 char words and even empty words....?

rascle
New poster
Posts: 20
Joined: Wed Mar 06, 2002 2:00 am

Post by rascle » Mon Jul 15, 2002 3:35 am

Sorry,I don't know what's wrong with your code..
You can get my code,and test many inputs on your code and mine...
Maybe you will get a detection from the answers between them ..

Good lock...

If you want my code ..please mail to

u891504@oz.nthu.edu.tw

I will send my code to you as soon as possible..

rascle
New poster
Posts: 20
Joined: Wed Mar 06, 2002 2:00 am

Post by rascle » Tue Jul 16, 2002 3:59 am

Hi

I've sent you my code 195.c

I implemented the problem 10098 yesterday,it is same as 195,the only
difference is the A<B<C <..<Z<a<b...<z and A<a<B<b<C<c..<Z<z

I found the problems are only initializaion and noting the order.


^^..

karl
New poster
Posts: 11
Joined: Tue Jul 16, 2002 1:03 pm

195 - WA again and again

Post by karl » Tue Jul 16, 2002 1:11 pm

It's terrible, always WA WA WA.
I studied your advices given before very carefully; I guess, my prog generates no duplicates and sorting is okay.
Do you have any hints or more test data???

[code]
#include <strstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


char line[8192];
char z;
int z_mod;

int n_of_runs;
int run;


void do_the_job()
{
vector<char> v;
char i;

gets(line);
istrstream mystream1(line);
while (mystream1 >> z)
{
z_mod=(int) z;
if ((z_mod>55) && (z_mod<91))
v.push_back((z_mod-65)*2+1);
else
v.push_back((z_mod-96)*2);
}
sort(v.begin(), v.end());
for (i=0; i<v.size(); i++)
{
if ((v[i])%2==1)
cout << ((char)(((v[i]-1)/2)+65));
else
cout << ((char)(((v[i])/2)+96));
}
cout << endl;

while (next_permutation(v.begin(), v.end()))
{
for (i=0; i<v.size(); i++)
{
if ((v[i])%2==1)
cout << ((char)(((v[i]-1)/2)+65));
else
cout << ((char)(((v[i])/2)+96));
}
cout << endl;
}
cout << endl;
}



int main()
{

cin >> n_of_runs;
for (run=0; run<n_of_runs; run++)
do_the_job();

return 0;
}

[/code]


Any help welcome!!![/cpp]

irmen
New poster
Posts: 5
Joined: Sat Jul 13, 2002 11:05 pm

Re: 195 - WA again and again

Post by irmen » Tue Jul 16, 2002 8:16 pm

Your prog doesn't compile here without changing #include <strstream.h> to #include <strstream>

After that, I can't get your prog to read a basic input file:

1
test

It doesn't read the word. Just exits...

karl
New poster
Posts: 11
Joined: Tue Jul 16, 2002 1:03 pm

Post by karl » Wed Jul 17, 2002 8:13 am

:D

I got it!!!
Problem was: How to deal with empty lines...

I changed input handling to

[cpp] do
{
gets(line);
} while (strlen(line)==0);
[/cpp]


Thanks a lot!!!

bundy
New poster
Posts: 10
Joined: Tue Jul 23, 2002 2:39 pm
Location: Findlay, Oh
Contact:

Post by bundy » Wed Jul 24, 2002 4:36 pm

ok I think I have finally figured this out. I wrote my own compare routine for the sort algorithm to call. the program compiles on my system (win 2k and vc++) but I get a few compile errors from the judge. here are the errors I am getting.

00973177_24.c: In function `bool bSorted(basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >, basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >)':
00973177_24.c:74: implicit declaration of function `int _strdup(...)'
00973177_24.c:76: implicit declaration of function `int _strupr(...)'

I thought _strdup and _strupr was declared in string.h. I also had an earlier error where i ended up having to do a cast because it was return an int when i expected a char*.

Here is my code. Any help is appreciated.

[cpp]
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <malloc.h>

using namespace std;

string toString(vector<char> &data);
bool bSorted(string x, string y);
void printEntry(vector<string> &data);


int main()
{

int numberOfWords = 0;
int count = 0;
vector<char> combo;
string input = "";
vector<string> output;


cin >> numberOfWords;

while (count++ < numberOfWords)
{
int i = 0;

combo.clear();
output.clear();
input = "";

cin >> input;

for (;i < input.size();i++)
combo.push_back(input);

sort(combo.begin(), combo.end());
output.push_back(toString(combo));

while(next_permutation(combo.begin(),combo.end()))
{
output.push_back(toString(combo));
}

sort(output.begin(),output.end(),bSorted);
printEntry(output);
}

//cout << "in test " << ("e" < "b") << endl;
//cout << bSorted("eaaBB","BBaae");


return 0;
}

void printEntry(vector<string> &data)
{
for(int i = 0; i < data.size(); i++)
cout << data << endl;
return;
}

bool bSorted(string x, string y)
{
char *xCopy;
char *yCopy;
char *xCap;
char *yCap;

xCopy = reinterpret_cast<char*> (_strdup(x.c_str()));
yCopy = reinterpret_cast<char*> (_strdup(y.c_str()));
xCap = reinterpret_cast<char*> (_strupr(xCopy));
yCap = reinterpret_cast<char*> (_strupr(yCopy));

if (x == y)
{
//cout << "equal" << endl;
return true;
}
else
{
if ( strcmp(xCap,yCap) == 0)
{

if (x < y)
{
//cout << "caps equal and x less than" << endl;
return true;
}
else
{
//cout << "caps equal and x greater than" << endl;
return false;
}
}
else
{
if (x < y)
{
//cout << "caps less than" << endl;
return true;
}
else
{
//cout << "caps greater than" << endl;
return false;
}

}
}

free(xCopy);
free(yCopy);
free(xCap);
free(yCap);
}


string toString(vector<char> &data)
{
string temp = "";
for (int i = 0; i < data.size();i++)
temp += data;
return temp;
}


[/cpp]

LawrenceT
New poster
Posts: 14
Joined: Sun Feb 24, 2002 2:00 am
Location: Singapore
Contact:

Post by LawrenceT » Wed Jul 24, 2002 6:13 pm

my guess is that you are programming in windows.. probably using microsoft visual c or some variant...

cos these functions starting with '_' do not exist in ANSI C, which is generally (with a few exceptions - for example, the long long int type) what the judge is running...

so, use other functions that have the same effect...

Post Reply

Return to “Volume 1 (100-199)”