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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Tue Mar 28, 2006 2:57 pm

congratulations! :D
and what was the problem,Roby?

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » Wed Mar 29, 2006 6:03 am

My comparison function did wrong comparison. So, I changed the comparison function into this one:

Code: Select all

int comparer( const void * a, const void * b )
{
 char * va = ( char * ) a;
 char * vb = ( char * ) b;
 char bigA, bigB;

 bigA = islower(*va) ? (*va)-32 : (*va);
 bigB = islower(*vb) ? (*vb)-32 : (*vb);

 if ( bigA != bigB )
 	return bigA-bigB;
 else
    return (*va)-(*vb);
}
And my problem is gone forever :)

My program was failed with this input:

Code: Select all

1
AaB
It should produce these:

Code: Select all

AaB
ABa
aAB
aBA
BAa
BaA
But the fact, my program was producing different output.

Once again thanx for your help (especially for the hint to use islower function, it's inspiring me much) :)

Daredevil
New poster
Posts: 19
Joined: Tue Apr 01, 2003 7:47 am
Location: Earth

195 - Anagrams Why WA?

Post by Daredevil » Sun Jul 02, 2006 1:27 pm

I don't understand why WA.

Here's my code:

#include<stdio.h>
#include<string.h>

int count,n,len;
char num[200],string[300],s[300];

void permute(){
int i;

/*Uppercase letters*/

for(i=65;i<91;i++){
if(num){
string[count++]=i;
num--;
if(count==len) printf("%s\n",string);
else permute();
num++;
string[--count]=0;
}
}



/*lowercase letters*/

for(i=97;i<123;i++){
if(num){
string[count++]=i;
num--;
if(count==len) printf("%s\n",string);
else permute();
num++;
string[--count]=0;
}
}
}



void main(){
int i;
scanf("%i",&n);
while(n--){
scanf("%s",&s);
len=strlen(s);
for(i=0;i<len;i++) num[s]++;
permute();
memset(num,0,190);
}
}

/*end of code*/

taskin
New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
Location: Bangladesh

Post by taskin » Fri Jul 14, 2006 10:41 pm

"the words should be output in alphabetically ascending order".
check this input:
1
aB

output:
aB
Ba

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Post by Rocky » Sat Jul 15, 2006 8:50 am

in this problem the order is A,a,B,b......

Rocky

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Wed Sep 13, 2006 11:36 pm

hello, how to avoid repeated permutations?

Code: Select all


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE 10000


void swap( char *x, char *y )
{
	char tmp = *x;
	*x = *y;
	*y = tmp;
}


int ch_cmp( const void *a, const void *b )
{
	return *((char *)a) - *((char *)b);
} 


int fact( int n )
{
	return (n == 1) ? 1 : n*fact(n-1);
}


void next_permutation( char *seq, int last )
{
	int j, k, r, s;

	j = last-1;
	while( seq[j] > seq[j+1] ) j--;

	k = last;
	while( seq[j] > seq[k] ) k--;
	swap( &seq[j], &seq[k] );

	r = last;
	s = j + 1;
	while( r > s )
	{
		swap( &seq[r], &seq[s] );
		r--;
		s++;
	}
}



int main()
{
	char seq[MAX_SIZE] = {0};
	int slen, np, ntest;

	scanf( "%d", &ntest );
	while( ntest-- )
	{
		scanf( "%s", seq );
		slen = strlen(seq);
		qsort( seq, slen, sizeof(char), ch_cmp );
		np = fact(slen)-1;
		printf( "%s\n", seq );		
		while( np-- )
		{
			next_permutation( seq, slen-1 );
			printf( "%s\n", seq );
		}
	}

	return 0;
}
thanks
"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor

harrym
New poster
Posts: 5
Joined: Thu Sep 07, 2006 8:48 pm

Post by harrym » Sun Sep 17, 2006 6:59 pm

You should use the <algorithm> library, as in
sort(seq,seq+slen,ch_cmp);
....
while(next_permutation(seq,seq+slen,ch_cmp))

next_permutation will permute all elements between the 2 pointers (arg0,arg1) either by operator< or by arg2 (if provided) and will return 0 when there is no lexicorgraphicly next_permutation possible.

acm4fun
New poster
Posts: 1
Joined: Sat Jan 20, 2007 9:22 am

195 - TLE??

Post by acm4fun » Sat Jan 20, 2007 9:28 am

I got TLE in anagram...

Here is my solution (in C++):
1) use a vector to store all characters of string input,
2) sort the character using sort()
3)

do {

// form a string from characters
// if the string is not found in a vector of "appeared string"
// print it out, store the string in "appeared string"

} while (next_permutation(...))

Will the above algorithm cause TLE? Thanks...!!

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sun Jan 21, 2007 5:17 am

yes, you will need to do permutation with repetition smarter, and generate them in a manner that you don't need to worry about re-appearance. i.e.: The way they are generated is such that no word will reappear, even if the input has multiple copies of the same letter.

Astimodeus
New poster
Posts: 2
Joined: Mon May 07, 2007 10:47 pm

195 Compiler Error

Post by Astimodeus » Mon May 07, 2007 10:50 pm

I get this compiler output:

Code: Select all

05565437_24.c: In function `prenditesto':
05565437_24.c:53: parse error before `char'
05565437_24.c:56: `arg' undeclared (first use in this function)
05565437_24.c:56: (Each undeclared identifier is reported only once
05565437_24.c:56: for each function it appears in.)
05565437_24.c: In function `purge':
05565437_24.c:68: parse error before `int'
05565437_24.c:71: `i' undeclared (first use in this function)
05565437_24.c:73: `res' undeclared (first use in this function)
with this C code:

Code: Select all

#include <stdio.h>
#include <string.h>

int len=0;

void purge(char *arr);
void prenditesto();
void permuta(char *parola, int n);
void stampa(char *parola);

int main()
{
	prenditesto();
	return 0;
}

void permuta(char *parola, int n)
{
	if(n==len-1)
		stampa(parola);
	else
	{
		int i;
		for(i=n;i<len;i++)
		{
			int temp = parola[i];
			parola[i] = parola[n];
			parola[n] = temp;
			permuta(parola,n+1);
			temp = parola[i];
			parola[i] = parola[n];
			parola[n] = temp;
		}
	}
}

void stampa(char *parola)
{
	int i;
	for(i=0;parola[i]!='\0';i++)
	{
		printf("%c", parola[i]);
	}
	printf("%c", '\n');
}

void prenditesto()
{
	int num;
	int i;
	scanf("%d", &num);
	char *arg[num];
	for(i=0;i<num;i++)
	{
		scanf("%s", arg[i]);
	}
	for(i=0;i<num;i++)
	{
		purge(arg[i]);
		permuta(arg[i],0);
	}
}

void purge(char *arr)
{
	len=strlen(arr);
	int i;
	char res[len];
	
	for(i=0;i<len;i++)
	{
		res[i]=arr[i];
	}
	arr=res;
}
I'm puzzled, can you help me out?

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue May 08, 2007 12:19 pm

Code: Select all

char *arg[num]; 
You can not declare array like this. num must be a constant, or you need to allocate memory dynamically by using malloc().

The code will however compile if you specify C++ as the language.

reemuskumar
New poster
Posts: 4
Joined: Wed Jun 14, 2006 3:55 pm

pbm 195

Post by reemuskumar » Tue May 08, 2007 2:17 pm

What is wrong with this code ? I'm getting signal error while submitting, it is runs fine in my system. Pls let me know what is the stress input.

Code: Select all

#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

int charmap[256];
void print_str(char*);

class node {
        private:
                char data[100];
                node *next;

    public:
                friend class linklist;
};

class linklist {
        private:
                node *first;

        public:
                linklist():first(0){}
                void insert(char *);
                void destroy();
                void display();
};

void linklist::insert(char *str) {
        node *tmp;

        tmp=new node();
        strcpy(tmp->data,str);
        tmp->next=first;

        if(first==0) {
                first=tmp;
                return;
        }

        if(strcmp(first->data,tmp->data)==0) return;

        if(strcmp(first->data,tmp->data)>0) {
                tmp->next=first;
                first=tmp;
                return;
        }

        node *curr=first;

        while(curr->next && strcmp(curr->next->data,tmp->data)<0) {
                curr=curr->next;
        }
    
        if(curr->next && strcmp(curr->next->data,tmp->data)==0) return;
        if(strcmp(curr->data,tmp->data)==0) return;
        tmp->next=curr->next;
        curr->next=tmp;
}

void linklist::display() {
        for(node *curr=first;curr;curr=curr->next)
          print_str(curr->data);
}

void linklist::destroy() {
        node *curr=first,*next;

        while(curr) {
                next=curr->next;
                delete curr;
                curr=next;
        }
        first=0;
}


void swap(char *str, int x, int y) {
  char tmp=str[x];
  str[x]=str[y];
  str[y]=tmp;
}

void print_str(char *str) {
        int len=strlen(str);

        for(int i=0;i<len;i++)
           for(int j=0;j<charmap[str[i]];j++)
                   cout<<str[i];
    cout<<endl;
}

int comp_char(const void *a, const void *b) {
        char *p=(char*)a, *q=(char*)b;
        return *p-*q;
}

void HeapPermute(char *str, int n, linklist& l)
{
  if (n == 1) 
    l.insert(str);
  else {
    for (int i = 0; i < n; i++) {
      HeapPermute(str, n-1,l);
      if (n % 2 == 1) // if n is odd
        swap(str, 0, n-1);
      else // if n is even
        swap(str, i, n-1);
    }
  }
}


int main() {
  int num;
  char word[20][100];
  linklist l;
  
  // Get the Number of Words
  cin>>num;
  for(int i=0;i<num;i++){
        cin>>word[i];
  }

  // Process & Display Anagram for each word
  for(int i=0;i<num;i++) {
        int len=strlen(word[i]);
        for(int j=0;j<256;j++) charmap[j]=0;
        for(int j=0;j<len;j++) charmap[word[i][j]]++;
        qsort((void*)word[i],len,1,comp_char);
        // Shrink word[i];
        int r,w=0;
        for(r=1;r<len;r++){
                if(word[i][w]==word[i][r]) {
                } else {
                   word[i][++w]=word[i][r];
                }
        }
        word[i][++w]=0;
        len=strlen(word[i]);
        HeapPermute(word[i],len,l);
        l.display();
        l.destroy();
  }
  return 0;
}


Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue May 08, 2007 2:24 pm

Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

Astimodeus
New poster
Posts: 2
Joined: Mon May 07, 2007 10:47 pm

Post by Astimodeus » Tue May 08, 2007 9:09 pm

shamim wrote:

Code: Select all

char *arg[num]; 
You can not declare array like this. num must be a constant, or you need to allocate memory dynamically by using malloc().

The code will however compile if you specify C++ as the language.
No it won't :lol:
Tnx anyway! I've forgot the judge uses a pre c99 compiler :)

SARKAR
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 pm

plzzzzzzz help.......195

Post by SARKAR » Fri May 25, 2007 10:03 pm

MY code is running fine for test cases......
but i am getting WA plzzz see wat is the bug

OR PROVIDE ME WITH SOME CRITICAL TEST CASES

Code: Select all

code removed
Last edited by SARKAR on Sat May 26, 2007 5:24 pm, edited 1 time in total.

Post Reply

Return to “Volume 1 (100-199)”