134 - Loglan-A Logical Language

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

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

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

uha
New poster
Posts: 12
Joined: Mon Mar 22, 2004 3:35 am

Post by uha »

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

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
New poster
Posts: 12
Joined: Mon Mar 22, 2004 3:35 am

Post by uha »

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

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.
Ami ekhono shopno dekhi...
HomePage

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

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

Output:
Bad!
Bad!
Bad!
Bad!

Hope this helps.

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

Post by Jan »

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..
Ami ekhono shopno dekhi...
HomePage

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

I got Accepted :)

Thank u again to make the problem clear...
Ami ekhono shopno dekhi...
HomePage

lantimilan
New poster
Posts: 11
Joined: Sat Mar 19, 2005 11:12 am
Location: HKU
Contact:

Some fine points

Post by lantimilan »

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 .
-- This is Unix, any explanatory error message is seen as a sign of weakness

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

WA 134

Post by shanto86 »

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
Self judging is the best judging!

danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Spaces after the period

Post by danielrocha »

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.
Daniel
UFRN HDD-1
Brasil

danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Spaces after the period

Post by danielrocha »

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.
Daniel
UFRN HDD-1
Brasil

Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

134 WA

Post by Yu Fan »

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
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 »

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
Sleep enough after death, it is the time to work.
Mostafa Saad

Post Reply

Return to “Volume 1 (100-199)”