134 - Loglan-A Logical Language

junbin · Post by **junbin** » Mon Mar 22, 2004 6:09 am

If I'm not wrong, there won't be such cases.

uha · Post by **uha** » Mon Mar 22, 2004 7:54 am

I suspect there are such cases.

Let me explain why.

The test for predicates is the most complicated so in my first attempt I simply tested for MOD, A, BA, DA, LA, and NAM then I assumed PREDA if it was none of the above. That is reasonable if all words have to fit in one of those classes. However I got a WA. When I redid my program to test explicitly for predicates and return an error if it came upon an invalid word I got AC. It seems to me that the judge's test cases include non-loglan words when the specs say it wouldn't.

junbin · Post by **junbin** » Mon Mar 22, 2004 11:25 am

Does your program have any problems with the following:

1) Extra spaces between words
2) Extra spaces at the END of the sentence (before the period)
3) Extra spaces at the START of the sentence
4) Extra letters AFTER the period
5) Extra spaces AFTER the period

etc.

uha · Post by **uha** » Mon Mar 22, 2004 5:05 pm

junbin wrote:Does your program have any problems with the following:

1) Extra spaces between words
2) Extra spaces at the END of the sentence (before the period)
3) Extra spaces at the START of the sentence
4) Extra letters AFTER the period
5) Extra spaces AFTER the period

etc.

No 4. will trick my program. However, even when I fix that problem, I get a wrong answer if I assume that all words are valid. So I still think there are invalid words in the test cases. That would be ok, if the problem didn't say there would be no such words.

This always works:

[cpp]

bool predicate(std::string& word)
{
//returns true if word is a predicate
}

token get_next_token(const std::string& word)
{
if(word == ".")
return token(END, word);
else if(word=="a" || word=="e" || word=="i" || word=="o" || word=="u")
return token(A, word);
else if(word=="ga" || word=="ge" || word=="gi" || word=="go" || word=="gu")
return token(MOD, word);
else if(word=="ba" || word=="be" || word=="bi" || word=="bo" || word=="bu")
return token(BA, word);
else if(word=="da" || word=="de" || word=="di" || word=="do" || word=="du")
return token(DA, word);
else if(word=="la" || word=="le" || word=="li" || word=="lo" || word=="lu")
return token(LA, word);
else if(!vowel(word[word.length()-1]))
return token(NAM, word);
else if(predicate(word))
return token(PREDA, word);
else
return token(BAD, word);

}

[/cpp]

and this doesn't work:

[cpp]

token get_next_token(const std::string& word)
{
if(word == ".")
return token(END, word);
else if(word=="a" || word=="e" || word=="i" || word=="o" || word=="u")
return token(A, word);
else if(word=="ga" || word=="ge" || word=="gi" || word=="go" || word=="gu")
return token(MOD, word);
else if(word=="ba" || word=="be" || word=="bi" || word=="bo" || word=="bu")
return token(BA, word);
else if(word=="da" || word=="de" || word=="di" || word=="do" || word=="du")
return token(DA, word);
else if(word=="la" || word=="le" || word=="li" || word=="lo" || word=="lu")
return token(LA, word);
else if(!vowel(word[word.length()-1]))
return token(NAM, word);
else
return token(PREDA, word);

}

[/cpp]

Jan · Post by **Jan** » Sat Jul 23, 2005 6:14 am

What is the output of the following input set..

Input:

Code: Select all

abcdcbda nmnmnna.
bbbbbbbba bbbbbbba.
la la la la la li la.
abededed.
#

Thanks in advance.

chunyi81 · Post by **chunyi81** » Sat Jul 23, 2005 9:28 am

Jan, my AC program outputs the following for your input.

Output:
Bad!
Bad!
Bad!
Bad!

Hope this helps.

Jan · Post by **Jan** » Sun Jul 24, 2005 8:48 pm

Thanks chunyi, But can you explain something...

The problem says..

Loglan words all end with a vowel; names, which are derived extra-linguistically, end with a consonant. Loglan words are divided into two classes--little words which specify the structure of a sentence, and predicates which have the form CCVCV or CVCCV where C represents a consonant and V represents a vowel

Therefore if we have a Loglan little word (which ends with a vowel but not a predicate) then do we skip it? or do we produce 'Bad!' ?

.....

Suppose we have the following input

Input:

Code: Select all

le bcade ga fgiho.
le bcade ga fgiho hnjhshaa.
#

Output:

Code: Select all

Good
Bad!

But the problem says...

Loglan words are divided into two classes--little words which specify the structure of a sentence

So why we are producing 'Bad!' for a little word?

Thank u again..

chunyi81 · Post by **chunyi81** » Wed Jul 27, 2005 4:29 am

The problem description also states the subset of grammar considered. We are supposed to consider only the Loglan little words specified in the given grammar. No need to make things that complicated. So for the example you have given, the output will be:

Output:
Good
Bad!

Jan · Post by **Jan** » Thu Jul 28, 2005 4:15 am

I got Accepted

Thank u again to make the problem clear...

lantimilan · Post by **lantimilan** » Wed Aug 17, 2005 2:42 pm

1. There is BAD formed words, words that are NOT in the grammar. This is very unfortunate because the problem statement says "you can assume all words will be correctly formed". I checked this by an assertion which catches bad words.

2. There is NO upper case characters. So you don't have to worry about case .

shanto86 · Post by **shanto86** » Wed Sep 14, 2005 12:50 pm

I am getting WA. here is my code:

#include<stdio.h>
#include<string.h>
int nword,type[1000];
char list[1000][100];

int VOW(char ch)
{
if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u')
return 1;
return 0;
}

int TAKE_PREDNAME(int s)
{
int i;
if(type[s]==7)
return s+1;

if(type[s]==5)
{
if(s==nword) return -1;

for(i=s+1;i<=nword;i++)
if(type[i]!=6)
break;

if(i==s+1) return -1;

return i;
}

return -1;
}

int TAKE_VERBPRED(int s)
{
int i;
if(type[s]!=2) return -1;

if(s==nword) return -1;

for(i=s+1;i<=nword;i++)
if(type[i]!=6)
break;

if(i==s+1) return -1;

return i;
}

int SENTENCE()
{
int k;
k=TAKE_PREDNAME(0);

if(k==-1 || k>nword) return 0;

k=TAKE_VERBPRED(k);

if(k==-1) return 0;
if(k>nword) return 1;

k=TAKE_PREDNAME(k);

if(k==-1 || k<=nword) return 0;
return 1;
}

int TAKE_PREDS(int s)
{
int i;
if(type[s]!=6) return -1;

for(i=s+1;i<=nword;i++)
if(type[i]!=1 && type[i]!=6)
break;

return i;
}

int PRODCLAIM()
{
int i,k;

TYPE1:
{
k=TAKE_PREDNAME(0);

if(k==-1) goto TYPE2;

if(type[k]!=3) goto TYPE2;
else k++;

if(k>nword) goto TYPE2;

k=TAKE_PREDS(k);

if(k==-1 || k<=nword) goto TYPE2;
else return 1;
}

TYPE2:
{
if(type[0]!=4) goto TYPE3;

k=TAKE_PREDS(1);

if(k==-1 || k<=nword) goto TYPE3;
else return 1;
}

TYPE3:
return 0;
}

int main()
{
int len,i,FALSE;
char ch,word[100];
freopen("test.in","r",stdin);
while(1)
{
len=-1;
nword=-1;
scanf("%c",&ch);
while( ch==' ')
scanf("%c",&ch);
while(ch!='#' && ch!='.')
{
if(ch=='\n')
{
scanf("%c",&ch);
continue;
}

if(ch==' ' && len>=0)
{
nword++;
word[len+1]='\0';
strcpy(list[nword],word);
scanf("%c",&ch);
len=-1;
continue;
}
if(ch==' ' && len<0)
{
scanf("%c",&ch);
continue;
}
len++;
if(ch>='A' && ch<='Z') ch=ch-'A'+'a';
word[len]=ch;
scanf("%c",&ch);
}

if(ch=='#')
break;

if(ch=='.' && len>=0)
{
nword++;
word[len+1]='\0';
strcpy(list[nword],word);
len=0;
}
FALSE=0;
/*if(ch=='.' && len==0)
{printf("Good\n"); continue;}*/
for(i=0;i<=nword;i++)
{
len=strlen(list[i]);
if(len==1 && VOW(list[i][0]))
type[i]=1;//A
else if(len==2 && list[i][0]=='g' && VOW(list[i][1]))
type[i]=2;//MOD
else if(len==2 && list[i][0]=='b' && VOW(list[i][1]))
type[i]=3;//BA
else if(len==2 && list[i][0]=='d' && VOW(list[i][1]))
type[i]=4;//DA
else if(len==2 && list[i][0]=='l' && VOW(list[i][1]))
type[i]=5;//LA
else if(len==5 && !VOW(list[i][0]) && !VOW(list[i][1]) && VOW(list[i][2]) && !VOW(list[i][3]) && VOW(list[i][4]))
type[i]=6;//PREDA
else if(len==5 && !VOW(list[i][0]) && VOW(list[i][1]) && !VOW(list[i][2]) && !VOW(list[i][3]) && VOW(list[i][4]))
type[i]=6;//PREDA
else
type[i]=7;//NAM
}

if((SENTENCE() || PRODCLAIM()))
printf("Good\n");
else
printf("Bad!\n");
}
return 0;
}

can any1 hlp me with debugging or can give me some cases??

(I have checked all the cases given in def posts!

Mahbub

danielrocha · Post by **danielrocha** » Mon Oct 03, 2005 3:27 am

I would just like to warn everyone who's trying to solve this problem that there are spaces after the period. Since this is not clearly stated in the input specification I think it should be mentioned here.

danielrocha · Post by **danielrocha** » Mon Oct 03, 2005 3:30 am

I would just like to warn everyone who's trying to solve this problem that there are spaces after the period. Since this is not clearly stated in the input specification I think it should be mentioned here.

Yu Fan · Post by **Yu Fan** » Tue Jul 25, 2006 9:16 am

I've got mant WAs in this problem, and I've viewed all the topics in this forum but still can't find the error.
Could anyone help me find the bug or give me some test cases?
Thanks in advance;

Code: Select all

#include <stdio.h>
#include <string.h>
#define UNCHECK 0
#define A 1
#define MOD 2
#define BA 3
#define DA 4
#define LA 5
#define NAM 6
#define PREDA 7
#define ERR 8

bool vowel(char p) {
	switch (p) {
		case 'a': case 'e': case 'i': case 'o': case 'u':
		case 'A': case 'E': case 'I': case 'O': case 'U': return 1;
		default: return 0;
	}
}

int type(char* p) {
	if (!vowel(p[strlen(p) - 1]))
		return NAM;
		
	if (strlen(p) == 1)
		return A;

	if (strlen(p) == 2)
		switch(p[0]) {
			case 'g': return MOD;
			case 'b': return BA;
			case 'd': return DA;
			case 'l': return LA;
			default: return NAM;
		}

	if (strlen(p) == 5) {
		if (!vowel(p[0]) && !vowel(p[1]) && vowel(p[2]) && !vowel(p[3]))
			return PREDA;
		if (!vowel(p[0]) && vowel(p[1]) && !vowel(p[2]) && !vowel(p[3]))
			return PREDA;
	}
	return NAM;
}


char p[1000][100];
int n;

bool predclaim() {
	int i;
	if (type(p[0]) == LA && type(p[1]) == PREDA) {
		i = 2;
		while (type(p[i]) == PREDA)
			i++;
		if (type(p[i++]) != BA)
			return 0;
	} else if (type(p[0]) == NAM && type(p[1]) == BA)
		i = 2;
	else if (type(p[0]) == DA)
		i = 1;
	else
		return 0;
		
	if (i == n)
		return 0;
		
	while (type(p[i]) == PREDA)
		i++;
	while (type(p[i]) == A) {
		i++;
		if (type(p[i++]) != PREDA)
			return 0;
		while (type(p[i]) == PREDA)
			i++;
	}
	return i == n;
}
bool statement() {
	int i;
	if (type(p[0]) == LA && type(p[1]) == PREDA) {
		i = 2;
		while (type(p[i]) == PREDA)
			i++;
	} else if (type(p[0]) == NAM)
		i = 1;
	else
		return 0;
	
	if (type(p[i]) == MOD && type(p[i + 1]) == PREDA) {
		i += 2;
		while (type(p[i]) == PREDA)
			i++;
	} else
		return 0;
	if (i == n)
		return 1;
	if (type(p[i]) == LA && type(p[i + 1]) == PREDA) {
		i += 2;
		while (type(p[i]) == PREDA)
			i++;
	} else if (type(p[i]) == NAM)
		i++;
	
	return i == n;
}

bool sentence() {
	return statement() || predclaim();
}

int main() {
	int i, l;
	char q[200];
	while (scanf("%s", &p[0]) && strcmp(p[0], "#")) {
		if (p[0][strlen(p[0]) - 1] == '.') {
			printf("Bad!\n");
			continue;	
		}
		for (i = 1; i < 200; i++)
			p[i][0] = 0;
		n = 1;
		while (scanf("%s", &p[n])) {
			l = strlen(p[n]);
			for (i = 0; i < l && p[n][i] != '.'; i++);
			if (i < l) {
				p[n][i + 1] = 0;
				gets(q);
				break;
			}
			n++;
		}
			
		if (p[n][0] != '.')
			p[n][strlen(p[n++]) - 1] = 0;
//		for (i = 0; i < n; i++)
//			printf("%s| %d\n", p[i], type(p[i]));
		printf("%s\n", sentence() ? "Good": "Bad!");
	}
	return 0;
}

898989 · Post by **898989** » Wed Aug 02, 2006 11:04 pm

I did not read your code carefully....Where is your comments???

in any case is this your preds code

Code: Select all

while (type(p[i]) == PREDA) 
      i++; 
   while (type(p[i]) == A) { 
      i++; 
      if (type(p[i++]) != PREDA) 
         return 0; 
      while (type(p[i]) == PREDA) 
         i++; 
   }

If yes i think it is not valid
preds may be
predstring ||
predstring A predstring ||
predstring A predstring A predstring ||
predstring A predstring A predstring A predstring||

So it must end with predstring....

Also make sure in the end that you finish all strings

OJ Board

134 - Loglan-A Logical Language

Some fine points

WA 134

Spaces after the period

Spaces after the period

134 WA