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 »

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

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

Post by Roby »

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 »

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 »

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

output:
aB
Ba

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

Post by Rocky »

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 »

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 »

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 »

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 »

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 »

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?

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

Post by shamim »

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 »

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 »

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 »

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 »

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)”