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

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

Post by Dominik Michniewski »

If I think, that's part of your program check if sentence is proper sentence in given grammar:

Code: Select all

      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;
      }
But what's happend when sentence will be very long ? Maybe 100 words? You check only 5 first of them (or I miss something) ....
Try to generate such long sentence - I think, that's your problem.

Last I don't see how you read input ;-) and now I see that you read it correctly :D. But I still think, that analyse word by word (by finite state automata, or parser) is easier :))

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)

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

Post by Dominik Michniewski »

Sorry for delay, but I was outside my city :(

One mistake :)) in found

Try this input "." -> only dot in line, as first character, after that enter ....

Happy debugging :) It was nice mistake hehehe

Dominik

PS. So I still think, that reading word by word is better - you avoid this problem in such way :))
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:Sorry for delay, but I was outside my city :(

One mistake :)) in found

Try this input "." -> only dot in line, as first character, after that enter ....

Happy debugging :) It was nice mistake hehehe

Dominik

PS. So I still think, that reading word by word is better - you avoid this problem in such way :))
Thank you very much! I got AC :)
Since I always read one character, so my program consider two "." as one :(

maurelio1234
New poster
Posts: 3
Joined: Sat Sep 13, 2003 5:31 pm
Location: Brazil
Contact:

Post by maurelio1234 »

I don't know what's wrong with my code, I tested it with all inputs here and in the program especification and it ran well, what's wrong with it?

[cpp]

#include <iostream>
#include <cstdlib>
#include <cstdio>

#define MAX_PAL 80
#define NUM_PAL 5000
#define cm(x) (strcmp(x,p)==0)

#define v(x) (x=='a' || x=='e' || x=='i' || x=='o' || x=='u')
#define c(x) (!(v(x)))

#define cc(x) (c(p[x]))
#define vv(x) (v(p[x]))

using namespace std;

bool testa_A();
bool testa_MOD();
bool testa_BA();
bool testa_DA();
bool testa_LA();
bool testa_NAM();
bool testa_sentence();
bool testa_predclaim();
bool testa_preds();
bool testa_predname();
bool testa_predstring();
bool testa_statement();
bool testa_verbpred();

char pal[NUM_PAL][MAX_PAL]/* {"la", "mutce", "bunbo", "mrenu", "bi", "ditca", NULL}*/;
int pos;
int sz;

bool testa_A() {
char *p = pal[pos];
if (*p==NULL) return false;

if (cm("a") || cm("e") || cm("i") || cm("o") || cm("u")) {
++pos;
return true;
} else return false;
}

bool testa_MOD() {
char *p = pal[pos];
if (*p==NULL) return false;

if (cm("ga") || cm("ge") || cm("gi") || cm("go") || cm("gu")) {
++pos;
return true;
} else return false;
}

bool testa_BA() {
char *p = pal[pos];
if (*p==NULL) return false;

if (cm("ba") || cm("be") || cm("bi") || cm("bo") || cm("bu")) {
++pos;
return true;
} else return false;
}

bool testa_DA() {
char *p = pal[pos];
if (*p==NULL) return false;

if (cm("da") || cm("de") || cm("di") || cm("do") || cm("du")) {
++pos;
return true;
} else return false;
}

bool testa_LA() {
char *p = pal[pos];
if (*p==NULL) return false;

if (cm("la") || cm("le") || cm("li") || cm("lo") || cm("lu")) {
++pos;
return true;
} else return false;
}

bool testa_NAM() {
char *p = pal[pos];
if (*p==NULL) return false;

if (c(p[strlen(p)-1])) {
++pos;
return true;
}
return false;
}

bool testa_PREDA() {
char *p = pal[pos];
if (*p==NULL) return false;

if (strlen(p)==5) {
bool r = ((cc(0) && cc(1) && vv(2) && cc(3) && vv(4))
||
(cc(0) && vv(1) && cc(2) && cc(3) && vv(4)))
;
if (r) {
++pos;
return true;
}
}

return false;
}

bool testa_sentence() {
int pos_antes = pos;
char *p = pal[pos];

if (*p==NULL) return false;

if (testa_statement()) {
return true;
} else {
pos = pos_antes;
bool r = testa_predclaim();

if (r) {
return true;
} else {
pos = pos_antes;
return false;
}
}
}

bool testa_predclaim() {
int pos_antes = pos;
char *p = pal[pos];

if (*p==NULL) return false;

if (testa_DA()) {
bool r = testa_preds();
if (r) {
return true;
} else {
pos = pos_antes;
}
}

if (testa_predname()) {
if (testa_BA()) {
if (testa_preds()) {
return true;
}
}
}
pos = pos_antes;
return false;
}

bool testa_preds() {
char *p = pal[pos];
if (*p==NULL) return false;

if (testa_predstring()) {
if (testa_A()) {
testa_preds();
}
return true;
} else return false;
}

bool testa_predname() {
int pos_antes = pos;
char *p = pal[pos];

if (*p==NULL) return false;

if (testa_LA()) {

if (testa_predstring()) {
return true;
}
}
pos = pos_antes;
return (testa_NAM());
}

bool testa_predstring() {
char *p = pal[pos];
if (*p==NULL) return false;

if (testa_PREDA()) {
testa_predstring();
return true;
} else return false;
}

bool testa_verbpred() {
int pos_antes = pos;
char *p = pal[pos];

if (*p==NULL) return false;

if (testa_MOD()) {
if (testa_predstring()) {
return true;
}
}

pos = pos_antes;
return false;
}

bool testa_statement() {
int pos_antes = pos;
char *p = pal[pos];

if (*p==NULL) return false;

if (testa_predname()) {
if (testa_verbpred()) {
pos_antes = pos;
if (testa_predname()) {
return true;
}
pos = pos_antes;
return true;
}
}
pos = pos_antes;
return false;
}

bool testa() {
pos = 0;
if (pos==sz) return true;
if (testa_sentence()) {
if (pos==sz) {
return true;
}
}
return false;
}

void readNext() {
int p = 0;
char c;
bool word = false;

sz = -1;
while(true) {
scanf("%c", &c);
if (c=='#') exit(0);
if (c=='. ') {
if (word) pal[sz][p] = 0;
break;
}

if ((c==' ' || c=='\n') && word) { /* se a palavra acabou */
pal[sz][p] = 0;
word = false;
}

if ((c!=' ' && c!='\n') && !word) { /* comecou uma nova palavra */
++sz;
p = 0;
word = true;
}

if (word) {
if (c>='A' && c<='Z') c = c + 'a' - 'A';
pal[sz][p] = c;
}

++p;
}
pal[++sz][0] = 0;
}



int main() {

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

while(true) {
readNext();
if (testa()) {
cout << "Good\n";
} else {
cout << "Bad!\n";
}
}
return 0;
}

[/cpp]

Thanks in advance.

User avatar
ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

134 Loglan Logical Language

Post by ezra »

hello everyone,
i try to solve this prob but i continously got WA. Please anyone be kind to share some important sample input so i can repair my program mistakes.
Thank you.

cplusplus
New poster
Posts: 13
Joined: Fri Feb 07, 2003 10:20 pm

Post by cplusplus »

I search this forum and find a topic about P134
here are some test cases...
I got WA, too...

And can anyone please tell me why the answer of the test case
"du zaoya. " is "BAD!" ??
It is the grammar "DA PREDS",isn't it?? Do I misundertand anything??

thank you all very much... :)

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 »

predicates which have the form CCVCV or CVCCV where C represents a consonant and V represents a vowel
"zaoya" is not a predicate under this rule.

As for the test cases it appears correct (tested it with AC program), but somehow I got one more "Bad!" output than yours. Perhaps you missed one line when you pasted the output? :D

User avatar
ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

Post by ezra »

it's weird,my program gave same result as junjieliang said but it's still WA.
I used the logic that separate the sentence into pattern of words and check the structure of the pattern from the beginning of the sentence.
Looks like i should post my code here.
here it is
[cpp]
#include<iostream>
#include<string>
using namespace std;

class word
{
string s;
public:
void read();
int resolve();
bool empty();
bool predicate();
bool detectdot();
bool detectend();
friend bool isvocal(char );
};

bool word::empty()
{
if(s.empty())
return true;
return false;
}

void word::read()
{
cin >> s;
}

bool isvocal(char c)
{
if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o'||c=='A'||c=='I'||c=='U'||c=='E'||c=='O')
return true;
return false;
}

bool word::predicate()
{
if(s.length()==5)
{
if(isvocal(s[0])==false&&isvocal(s[1])==false&&isvocal(s[2])==true&&isvocal(s[3])==false&&isvocal(s[4])==true)
return true;
if(isvocal(s[0])==false&&isvocal(s[1])==true&&isvocal(s[2])==false&&isvocal(s[3])==false&&isvocal(s[4])==true)
return true;
}
return false;
}

int word::resolve()
{
if(s=="a" || s=="e" || s=="i" || s=="o" || s=="u")
return 1;
if(s=="ga" || s=="ge" || s=="gi" || s=="go" || s=="gu")
return 2;
if(s=="ba" || s=="be" || s=="bi" || s=="bo" || s=="bu")
return 3;
if(s=="da" || s=="de" || s=="di" || s=="do" || s=="du")
return 4;
if(s=="la" || s=="le" || s=="li" || s=="lo" || s=="lu")
return 5;
if(predicate())
return 7;
if(isvocal(s[s.length()-1])==false)
return 6;
return 0;
}

bool word::detectdot()
{
if(s[s.length()-1]=='.')
{
s=s.substr(0,s.length()-1);
return true;
}
return false;
}

bool word::detectend()
{
if(s[0]=='#')
return true;
return false;
}

class loglan
{
int pattern[2000];
int curr;
int size;
public:
loglan(){size=0;curr=0;}
void readpattern(word &);
bool sentence();
bool predclaim();
bool preds();
bool predname();
bool predstring();
bool statement();
bool verbpred();
};

void loglan::readpattern(word & w)
{
if(!w.empty())
pattern[size++]=w.resolve();
}

bool loglan::verbpred()
{
int rec=curr;
if(pattern[curr++]==2&&predstring())
return true;
curr=rec;
return false;
}

bool loglan::predname()
{
int rec=curr;
if(pattern[curr++]==5&&predstring())
return true;
curr=rec;
if(pattern[curr]==6)
{
curr++;
return true;
}
return false;
}

bool loglan::predstring()
{
if(pattern[curr]==7)
{
curr++;
while(pattern[curr]==7)
{curr++;}
return true;
}
return false;
}

bool loglan::preds()
{
int rec=curr;
if(predstring())
{
while(pattern[curr]==1)
{
curr++;
if(!predstring())
{
curr=rec;
return false;

}
}
return true;
}
curr=rec;
return false;
}

bool loglan::statement()
{
int rec=curr;
if(predname()&&verbpred()&&predname())
return true;
curr=rec;
if(predname()&&verbpred())
return true;
curr=rec;
return false;
}

bool loglan::predclaim()
{
int rec=curr;
if(predname()&&pattern[curr]==3)
{
curr++;
if(preds())
return true;
}
curr=rec;
if(pattern[curr++]==4&&preds())
return true;
curr=rec;
return false;
}

bool loglan::sentence()
{
if(statement()||predclaim())
if(curr==size)
return true;
return false;
}

int main()
{
word w;
loglan *l;
bool EndProgram,EndSentence;
w.read();
EndSentence=w.detectdot();
EndProgram=w.detectend();
while(!EndProgram)
{
l=new loglan;
l->readpattern(w);
while(!EndSentence)
{
w.read();
EndSentence=w.detectdot();
l->readpattern(w);
}
if(l->sentence())
cout<<"Good";
else
cout<<"Bad!";
cout<<endl;
delete l;
w.read();
EndSentence=w.detectdot();
EndProgram=w.detectend();
}
return 0;
}
[/cpp]
please help me. I'll really grateful for your help. Thanks b4.

cplusplus
New poster
Posts: 13
Joined: Fri Feb 07, 2003 10:20 pm

Post by cplusplus »

junjieliang wrote:
predicates which have the form CCVCV or CVCCV where C represents a consonant and V represents a vowel
"zaoya" is not a predicate under this rule.

As for the test cases it appears correct (tested it with AC program), but somehow I got one more "Bad!" output than yours. Perhaps you missed one line when you pasted the output? :D
:) thank you very much , I forgot that I have fixed that bug before I paste these test cases. :P
...so still..I got WA again and again...

Can anyone give me some more test cases or some hints ,please ?? Thank you.... :wink:

cplusplus
New poster
Posts: 13
Joined: Fri Feb 07, 2003 10:20 pm

Post by cplusplus »

junjieliang wrote:
predicates which have the form CCVCV or CVCCV where C represents a consonant and V represents a vowel
"zaoya" is not a predicate under this rule.

As for the test cases it appears correct (tested it with AC program), but somehow I got one more "Bad!" output than yours. Perhaps you missed one line when you pasted the output? :D
OK...I got AC now...
if a word ends with a vovel but is not a A,GA....MOD, or PREDA....
it will be considered a NAM....
I just return "BAD!" before....I hope this helps you...

User avatar
ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

Post by ezra »

i still get wa on this prob. Is there any input like cplusplus said that a word ends with vowel but not include to one of any loglan words? For my code ,i already posted it,please help me check it. Thank you very much for helping.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

Tabs are considered "spaces" too. *sigh*

User avatar
ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

Post by ezra »

i dont understand. what do you mean about "tabs" ?
Please explain me,i really dont understand,thanks.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

The problem statement has been corrected to reflect the input. Please consider carefully what "whitespace" signifies.

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

134: misleading specification?

Post by uha »

I did 134 (loglan) and got a WA the first time. This line of the problem statement was the culprit.

"You can assume that all words will be correctly formed."

It shouldn't say that becuase the judge's test cases contain words that are neither MOD, A, BA, LA, DA, NAM or PRED (example 'zaoya'). If all words are 'correctly formed' loglan words something like 'zaoya' should not be among the test cases. Unless I'm interpreting the statement incorrectly.

Post Reply

Return to “Volume 1 (100-199)”