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

bigredteam2000
New poster
Posts: 11
Joined: Sat Nov 17, 2001 2:00 am

Post by bigredteam2000 »

We are getting time limit exceeded to this one. we reduced the sentences down to 12 basic types and if the sentence give is not one of these types then we do not accept it. We tried different test cases and it worked with all of them. I am wondering can a sentence contains capitals in it ( but even if it does our program shoul five a wrong answer).

Thank YOU!

//@begin_of_source_code

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

struct tp
{
char n[4];
char w[5][3];
};

tp tb[5]=
{
{"A", {"a", "e", "i", "o", "u" }},
{"MOD",{"ga","ge","gi","go","gu",}},
{"BA", {"ba","be","bi","bo","bu",}},
{"DA", {"da","de","di","do","du",}},
{"LA", {"la","le","li","lo","lu",}}
};

char tg[12][100]=
{
"LA<PS>MOD<PS>",
"LA<PS>MOD<PS>LA<PS>",
"LA<PS>MOD<PS>NAM",
"NAMMOD<PS>",
"NAMMOD<PS>LA<PS>",
"NAMMOD<PS>NAM",
"LA<PS>BA<PS>",
"LA<PS>BA<PD>",
"NAMBA<PS>",
"NAMBA<PD>",
"DA<PS>",
"DA<PD>"
};

char sentence[2000][8];
int cnt;

bool NAM(char str[])
{
switch (str[strlen(str)-1])
{
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
return false;
break;
}
return true;
}

bool PREDA(char str[])
{
char word[6];
int i;

if (strlen(str)!=5) return false;
for (i=0;i<5;i++)
{
switch (str)
{
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
word='V';
break;
default:
word='C';
break;
}
}
word='';
if ((strcmp(word,"CCVCV")==0) || (strcmp(word,"CVCCV")==0)) return true;
return false;
}

void convert(char str[])
{
int i,j;

if (NAM(str))
{
strcpy(str,"NAM");
return;
}
if (strlen(str)<=2)
{
for (i=0;i<5;i++)
for (j=0;j<5;j++)
{
if (strcmp(str,tb.w[j])==0)
{
strcpy(str,tb.n);
return;
}
}
}
else
{
if (PREDA(str))
{
strcpy(str,"PREDA");
return;
}
}
str[0]='';
return;
}

int find(char str[])
{
int i;

for (i=0;i<=cnt;i++)
{
if (strcmp(str,sentence)==0) return i;
}
return -1;
}

void connect(char sent[])
{
int i;

sent[0]='';
for (i=0;i<=cnt;i++)
{
if (sentence[0]!='')
{
strcat(sent,sentence);
}
}
}

int search(int pos)
{
int i;
for (i=pos;i>=0;i--)
{
if ((sentence[0])!='') return i;
}
return -1;
}

bool grammar()
{
char sent[100];
int i,j;

i=find("PREDA");
while (i!=-1)
{
strcpy(sentence[i],"<PS>");
i++;
while (strcmp(sentence[i],"PREDA")==0)
{
sentence[i][0]='';
i++;
}
i=find("PREDA");
}

i=find("A");
while (i!=-1)
{
j = search(i-1);
if (j!=-1)
if (((strcmp(sentence[j],"<PS>")==0) || (strcmp(sentence[j],"<PD>")==0)) && (strcmp(sentence[i+1],"<PS>")==0))
{
sentence[j][0]='';
sentence[i][0]='';
strcpy(sentence[i+1],"<PD>");
}
i=find("A");
}

connect(sent);
for (i=0;i<12;i++)
{
if (strcmp(sent,tg[i])==0) return true;
}
return false;
}

void main()
{
char str[100];
bool flag,broken;
int i,j;

cin >> str;
while (str[0]!='#')
{
cnt=0;
flag=true;
broken=false;
while (flag)
{
if (str[strlen(str)-1]=='.')
{
str[strlen(str)-1]='';
flag=false;
}
convert(str);
if (str[0]!='')
{
strcpy(sentence[cnt++],str);
}
else
{
cout << "Bad!" << endl;
broken=true;
while (str[strlen(str)-1]=='.') cin >> str;
cin >> str;
break;
}
cin >> str;
}
if (broken) continue;
cnt--;
if (grammar()) cout << "Good" << endl;
else cout << "Bad!" <<endl;
}
}

//@end_of_source_code

bigredteam2000
New poster
Posts: 11
Joined: Sat Nov 17, 2001 2:00 am

Post by bigredteam2000 »

We are getting time limit exceeded to this one. we reduced the sentences down to 12 basic types and if the sentence give is not one of these types then we do not accept it. We tried different test cases and it worked with all of them. I am wondering can a sentence contains capitals in it ( but even if it does our program should give a wrong answer).

Thank YOU!

//@begin_of_source_code

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

struct tp
{
char n[4];
char w[5][3];
};

tp tb[5]=
{
{"A", {"a", "e", "i", "o", "u" }},
{"MOD",{"ga","ge","gi","go","gu",}},
{"BA", {"ba","be","bi","bo","bu",}},
{"DA", {"da","de","di","do","du",}},
{"LA", {"la","le","li","lo","lu",}}
};

char tg[12][100]=
{
"LA<PS>MOD<PS>",
"LA<PS>MOD<PS>LA<PS>",
"LA<PS>MOD<PS>NAM",
"NAMMOD<PS>",
"NAMMOD<PS>LA<PS>",
"NAMMOD<PS>NAM",
"LA<PS>BA<PS>",
"LA<PS>BA<PD>",
"NAMBA<PS>",
"NAMBA<PD>",
"DA<PS>",
"DA<PD>"
};

char sentence[2000][8];
int cnt;

bool NAM(char str[])
{
switch (str[strlen(str)-1])
{
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
return false;
break;
}
return true;
}

bool PREDA(char str[])
{
char word[6];
int i;

if (strlen(str)!=5) return false;
for (i=0;i<5;i++)
{
switch (str)
{
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
word='V';
break;
default:
word='C';
break;
}
}
word='';
if ((strcmp(word,"CCVCV")==0) || (strcmp(word,"CVCCV")==0)) return true;
return false;
}

void convert(char str[])
{
int i,j;

if (NAM(str))
{
strcpy(str,"NAM");
return;
}
if (strlen(str)<=2)
{
for (i=0;i<5;i++)
for (j=0;j<5;j++)
{
if (strcmp(str,tb.w[j])==0)
{
strcpy(str,tb.n);
return;
}
}
}
else
{
if (PREDA(str))
{
strcpy(str,"PREDA");
return;
}
}
str[0]='';
return;
}

int find(char str[])
{
int i;

for (i=0;i<=cnt;i++)
{
if (strcmp(str,sentence)==0) return i;
}
return -1;
}

void connect(char sent[])
{
int i;

sent[0]='';
for (i=0;i<=cnt;i++)
{
if (sentence[0]!='')
{
strcat(sent,sentence);
}
}
}

int search(int pos)
{
int i;
for (i=pos;i>=0;i--)
{
if ((sentence[0])!='') return i;
}
return -1;
}

bool grammar()
{
char sent[100];
int i,j;

i=find("PREDA");
while (i!=-1)
{
strcpy(sentence[i],"<PS>");
i++;
while (strcmp(sentence[i],"PREDA")==0)
{
sentence[i][0]='';
i++;
}
i=find("PREDA");
}

i=find("A");
while (i!=-1)
{
j = search(i-1);
if (j!=-1)
if (((strcmp(sentence[j],"<PS>")==0) || (strcmp(sentence[j],"<PD>")==0)) && (strcmp(sentence[i+1],"<PS>")==0))
{
sentence[j][0]='';
sentence[i][0]='';
strcpy(sentence[i+1],"<PD>");
}
i=find("A");
}

connect(sent);
for (i=0;i<12;i++)
{
if (strcmp(sent,tg[i])==0) return true;
}
return false;
}

void main()
{
char str[100];
bool flag,broken;
int i,j;

cin >> str;
while (str[0]!='#')
{
cnt=0;
flag=true;
broken=false;
while (flag)
{
if (str[strlen(str)-1]=='.')
{
str[strlen(str)-1]='';
flag=false;
}
convert(str);
if (str[0]!='')
{
strcpy(sentence[cnt++],str);
}
else
{
cout << "Bad!" << endl;
broken=true;
while (str[strlen(str)-1]=='.') cin >> str;
cin >> str;
break;
}
cin >> str;
}
if (broken) continue;
cnt--;
if (grammar()) cout << "Good" << endl;
else cout << "Bad!" <<endl;
}
}

//@end_of_source_code

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak »

i got WA too.

isn't it a bit weird when the problem description said "You can assume that all words will be correctly formed.", but you still will get some strange words ended with a vowel. but not a name or A LA etc. ?

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even »

Try this one...

la mutce bunbo mrenu bi ditca.
la fumna bi le mrenu.
djan ga vedma le
negro ketpi.
la fumna bi ditca.
la fumna bi ditca
djan ga vedsa le negro ketpi.
djan be vedsa a vedma a ketpi.
.
#

it's answer is...

Good
Bad!
Good
Good
Bad!
Good
Bad!

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 »

how big is the maximum input sentence?
my program can handle your test case but still got WA :(
or is there any other special test case?

cole
New poster
Posts: 1
Joined: Mon Sep 09, 2002 8:37 pm

Post by cole »

[quote="wyvmak"]i got WA too.

isn't it a bit weird when the problem description said "You can assume that all words will be correctly formed.", but you still will get some strange words ended with a vowel. but not a name or A LA etc. ?[/quote]

I did some test and found there are non-Loglan words that
end with a vowel. However, I don't know how to deal with
them and still get WA too.

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 »

i've passed this problem several weeks ago...
the last thing i remember was i add the ability to handle multiple line input, like this:

Code: Select all

la mutce 
bunbo
mrenu 
bi ditca. 
i think you should check it too, it's harder than it looks :-?

potato
New poster
Posts: 9
Joined: Tue Feb 25, 2003 8:13 am

134 - Loglan-A Logical Language

Post by potato »

I have checked my program for a long time, but failed to find any mistake. Are there any tricks in this problem?

There is my testcase:

INPUT:
le bcade ga fgiho.
le bcade ge fgiho le bcade.
le bcade gi fgiho li bcade.
le bcade go fgiho lo bcade.
le bcade gu fgiho lu bcade.
foobar ge juklo li manpi.
lo qrase ba tviwu a xiyzu.
lo qrase ba tviwu a xiyzu e futye i
futno o blara u jukko.
da ztoya.
de ztoya i grota u thomo.
di ztoya.
do ztoya a brute.
du ztoya.
la mutce
bunbo mrenu ba ditca a ghoto.
futon be ditca.
gruton bi ditca.
le blara bunbo mrenu bo ditca.
jhqdhjqdwhjqwdhjqdjhwefdjhqwedhjwefzz bu ditca.
djb ba bbaba.
djan ga vedma le negro ketpi.
bad starts now.
la fumna bi le mrenu.
dja blarg.
djb ba.
.
le bcad ga fgiho.
le bcade gn fgiho le bcade.
le bcade gi fgiho ly bcade.
le bcade go fgiho lo bcadf.
bcade gu fgiho lu bcade.
lo qrase ba tviwu x xiyzu.
lo qrase ba tviwu a xiyzu e futye i
futno o blara u jukk.
la ztoya.
ge ztoya i grota u thomo.
bi ztoya.
do ztoya a bruten.
du zaoya.
futon e ditca.
gruton li ditca.
le blar bunbo mrenu bo ditca.
djan da vedma le negro ketpi.
#

My OUTPUT:
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Good
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!
Bad!

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang »

Have you tried having the period "." as a single word?
Something like
le_bcade_ga_fgiho_.
where the underscore "_" is space.
The output should be "Good"

Hope this helps.

potato
New poster
Posts: 9
Joined: Tue Feb 25, 2003 8:13 am

Post by potato »

junjieliang wrote:Have you tried having the period "." as a single word?
Something like
le_bcade_ga_fgiho_.
where the underscore "_" is space.
The output should be "Good"

Hope this helps.
my program gave the correct answer to such cases :(

potato
New poster
Posts: 9
Joined: Tue Feb 25, 2003 8:13 am

two more questions

Post by potato »

I've got two more questions here:

1. Should A, E, I, O, U be considered as vowels as a, e, i, o, u? Also, is 'GA' a MOD just like 'ga'?

2. If a word contains some non-alpha characters, should this characters be considered as consonant, or just consider the sentence to be a Bad one?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

1. vowels 'a' and 'A' (and so on) are the same so mAma and mAmA are to be considered as correct.

2. I use scanf() to read words from stdin, so I think, that not letter characters should be considered as consonants ... but I think that such input doesn't exist ....

I don't know how you write your code, but you must create grammar (from problem statement) which you can easy parse :)) i.e.
it's dificult to parse grammar like
A ->BCD | BCE | BF
but it's easier to parse something like
A -> BA'
A' -> CA'' | F
A'' -> D | E
If you don't do this - think about that (it's possible, that you avoid a lot of problems, when you transform grammar in such way :) )

Good luck
Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

potato
New poster
Posts: 9
Joined: Tue Feb 25, 2003 8:13 am

Post by potato »

I still failed to find any mistake in my program :(
Here it is
[cpp]
#include <stdio.h>
#include <strstream>
#include <string.h>
#include <ctype.h>
#define ISVOWEL(x) ( (x)=='a' || (x)=='e' || (x)=='i' || (x)=='o' || (x)=='u' )
#define NOTVOWEL(x) ( (x)!='a' && (x)!='e' && (x)!='i' && (x)!='o' && (x)!='u' )

using namespace std;

int main() {
char line[10000], word[500];

#ifndef ONLINE_JUDGE
freopen("134.in", "r+", stdin);
freopen("134.out", "w+", stdout);
#endif

for ( ; ; ) {
memset(line, 0, sizeof(line));
scanf(" %c", &line[0]);
if ( line[0]=='#' )
break;

for ( ; ; ) {
char ch = getchar();
if ( ch=='.' )
break;
ch=( ch=='\n' ? ' ' : tolower(ch) );
strncat(line, &ch, 1);
}

int nitem = 0, item[10000];
bool valid = true;

istrstream strin(line);
while ( strin >> word ) {
int len = (int)strlen(word);

if ( len==1 && ISVOWEL(word[0]) )
if ( nitem && item[nitem-1]==6 )
if ( nitem<2 || item[nitem-2]!=7 )
item[nitem-1]=7; // predstring + A
else
--nitem;
else
item[nitem++]=0; // A
else if ( len==2 && word[0]=='g' && ISVOWEL(word[1]) )
item[nitem++]=1; // MOD
else if ( len==2 && word[0]=='b' && ISVOWEL(word[1]) )
item[nitem++]=2; // BA
else if ( len==2 && word[0]=='d' && ISVOWEL(word[1]) )
item[nitem++]=3; // DA
else if ( len==2 && word[0]=='l' && ISVOWEL(word[1]) )
item[nitem++]=4; // LA
else if ( NOTVOWEL(word[len-1]) )
item[nitem++]=5; // NAM
else if ( len==5 &&
(NOTVOWEL(word[0]) && NOTVOWEL(word[1]) && ISVOWEL(word[2]) && NOTVOWEL(word[3]) && ISVOWEL(word[4]) ||
NOTVOWEL(word[0]) && ISVOWEL(word[1]) && NOTVOWEL(word[2]) && NOTVOWEL(word[3]) && ISVOWEL(word[4])) ) {
if ( nitem==0 )
item[nitem++]=6;
else if ( item[nitem-1]==4 )
item[nitem-1]=8; // LA + predstring
else if ( item[nitem-1]!=6 && item[nitem-1]!=8 )
item[nitem++]=6;
}
else {
valid=false; break;
}
}

for ( int i=0; i<nitem; ++i )
if ( item==8 )
item=5;

if ( valid ) {
valid=false;

if ( nitem==3 && item[0]==5 && item[1]==1 && item[2]==6 )
valid=true;
else if ( nitem==4 && item[0]==5 && item[1]==1 && item[2]==6 && item[3]==5 )
valid=true;
else if ( nitem==3 && item[0]==5 && item[1]==2 && item[2]==6 )
valid=true;
else if ( nitem==4 && item[0]==5 && item[1]==2 && item[2]==7 && item[3]==6 )
valid=true;
else if ( nitem==2 && item[0]==3 && item[1]==6 )
valid=true;
else if ( nitem==3 && item[0]==3 && item[1]==7 && item[2]==6 )
valid=true;
}

printf(valid ? "Good\n" : "Bad!\n");
fgets(line, 10000, stdin);
}

#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif

return 0;
}
[/cpp]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

Are you sure that you correct handle inputs like:

Code: Select all

la 
mutce
      bunbo 
mrenu bi 
ditca
.
Output should be "Good"

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

potato
New poster
Posts: 9
Joined: Tue Feb 25, 2003 8:13 am

Post by potato »

Dominik Michniewski wrote:Are you sure that you correct handle inputs like:

Code: Select all

la 
mutce
      bunbo 
mrenu bi 
ditca
.
Output should be "Good"

Dominik
My program does give the correct answer for this testcase...

Post Reply

Return to “Volume 1 (100-199)”