10058 - Jimmi's Riddles

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Thu Mar 01, 2007 1:09 pm

It is easier to think of critical test cases if you give us overview of your approach. It is a typical Grammar Problem. All other approaches may result in Wrong Answers.
Where's the "Any" key?

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

Post by Jan » Thu Mar 01, 2007 1:23 pm

Try the cases...

Input:

Code: Select all

the tom and the jerry and goofy and mickey like cat and mouse
tom likes jerry, jerry and goofy hate mickey
jimmy knows a cat, the cat likes mouse, the mouse hates the cat
goofy hates cats
a goofy loves a jimmy
a goofy loves a jimmy and the cat, mouse hates cat
a goofy loves the a jimmy
Output:

Code: Select all

YES I WILL
YES I WILL
YES I WILL
NO I WON'T
YES I WILL
YES I WILL
NO I WON'T
Hope these help.
Ami ekhono shopno dekhi...
HomePage

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Thu Mar 01, 2007 3:59 pm

I too really think it as a typical grammar problem... Thanks for the I?O set. my code pass all these test cases .. But still wrong answer though :(
my grammar look like this:

Code: Select all


S -> A|A,A
A -> LVL
L -> C and C| C
C -> N|RN
R -> a|the
N -> all noun
V -> all verb|Vs

s = statement
a = action
l = action list
c = actor
R = article 
 
did i miss something ??

Thanks in advance
Time that gone is gone forever ...

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

Post by Jan » Thu Mar 01, 2007 4:09 pm

Try the cases...

Input:

Code: Select all

tom hatessssssssssssss jerry
tom hatessssssssssssss jerry,
tom hatessssssssssssss jerry, , tom hatessssssssssssss jerry

tom hates jerry jerry hates tom
Output:

Code: Select all

YES I WILL
NO I WON'T
NO I WON'T
NO I WON'T
NO I WON'T
Hope these help. If your code passes, you can post your code.
Ami ekhono shopno dekhi...
HomePage

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Thu Mar 01, 2007 4:51 pm

HERE MY DUMP CODE :-?

Code: Select all



#include<stdio.h>
#include<string.h>

#define N 100

void match(char s[N]);
void get_next();
void Noun();
void L();
void S();
void R();
void C();
void A();
void V();

char lookahead[N];
int index;
int len;
char str[N];
int flag;


void V()
{

	int i;
	int tmp_len;
	int mark;
	char temp[N],tok[N],tmp[N];
	char ch;
	
	mark = 1;


	//refill it in two parts
	strcpy(temp,lookahead);
	tmp_len = strlen(lookahead);

	for(i=0;i<tmp_len;i++)
	{
		ch = lookahead[i];
		if(ch=='s')
		{
			mark = 0;
			break;
		}
		tok[i]=ch;
	}
	tok[i]='\0';

	if(strcmp(tok,"hate")==0)
	{}
		//match(tok);
	else if(strcmp(tok,"love")==0)
	{}	//match(tok);
	else if(strcmp(tok,"know")==0)
	{}	//match(tok);
	else if(strcmp(tok,"like")==0)
	{}	//match(tok);
	else
		flag = 0;

	
	//match(tok);
	if(!mark && flag)
	{
		strcpy(tmp,&temp[i]);
		tmp_len = strlen(tmp);
		i = 0;
		while(i<tmp_len)
		{
			ch = tmp[i];
			if(ch!='s')
			{
				flag = 0;
				break;
			}
			i++;
		}
	}

	if(flag)
		get_next();

	return;
}

void get_next()
{

	int tag = 0;
	int i;
	char ch;

	for(i=0;index<len;index++,i++)
	{
		ch = str[index];
		if(ch==' ')
		{
			index++;
			if(tag)
				break;
			else
				continue;
		}
		else if(ch==',' && tag==1)
		{
			break;
		}
		if(tag==0)
			tag=1;
		lookahead[i]=ch;
	}

	lookahead[i]='\0';

}

void match(char s[])
{
	if(strcmp(lookahead,s)==0)
		get_next();
	else
		flag = 0;
	return;
}

void Noun()
{
	if(strcmp(lookahead,"tom")==0)
		match("tom");
	else if(strcmp(lookahead,"jerry")==0)
		match("jerry");
	else if(strcmp(lookahead,"goofy")==0)
		match("goofy");
	else if(strcmp(lookahead,"mickey")==0)
		match("mickey");
	else if(strcmp(lookahead,"jimmy")==0)
		match("jimmy");
	else if(strcmp(lookahead,"dog")==0)
		match("dog");
	else if(strcmp(lookahead,"cat")==0)
		match("cat");
	else if(strcmp(lookahead,"mouse")==0)
		match("mouse");
	else 
		flag = 0;
	return;
}


void S()
{
	A();
	if(flag)
	{
		while(strcmp(lookahead,",")==0)
		{
			match(",");
			A();
		}
	}
	
	return;
}

void A()
{

	L();
	if(flag)
	{
		V();
		if(flag)
			L();
		else
			return;
	}

	return;
}

void L()
{

	C();
	if(flag)
	{
		while(strcmp(lookahead,"and")==0)
		{
			match("and");
			if(flag)
				C();
		}
	}

}

void C()
{

	if( (strcmp(lookahead,"a")==0) || (strcmp(lookahead,"the")==0) )
		R();
	if(flag)
		Noun();

	return;
}

void R()
{
	if( (strcmp(lookahead,"a")==0) || (strcmp(lookahead,"the")==0) )
		match(lookahead);
	else
		flag = 0;
	return;
}

int main()
{


	while(gets(str))
	{
	
		index=0;
		flag = 1;
		len = strlen(str);
		get_next();
		S();

		if(flag && strcmp(lookahead,"")!=0 )
			flag = 0;
		
		if(flag)
			printf("YES I WILL\n");
		else
			printf("NO I WON'T\n");

	
	}

	return 0;
}

Time that gone is gone forever ...

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

Post by Jan » Fri Mar 02, 2007 9:51 am

Your code returns wrong output when the sentences are seperated by comma(s), look at the samples

Input:

Code: Select all

tom hates jerry  , tom and jerry and goofy like jimmy
tom hates jerry  , tom and jerry and goofy hate jimmy
Output:

Code: Select all

YES I WILL
YES I WILL
And another thing, you can use the return type of the functions as 'bool' rather than 'void'. Then it would be easier to keep track of your work.
Ami ekhono shopno dekhi...
HomePage

peterkwan
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Post by peterkwan » Sun Feb 24, 2008 4:30 pm

I tested my program and all the test cases in the sample and in this thread are passed. However, I still get WA all the time? could somebody help?

Code: Select all

#include <iostream>
#include <string>
using namespace std;

string trim(string s) {
	s.erase(0,s.find_first_not_of(" "));
	s.erase(s.find_last_not_of(" ")+1);
	return s;
}

bool isNoun(string s) {
	return s=="tom" || s=="jerry" || s=="goofy" || s=="mickey" || s=="jimmy" || s=="dog" || s=="cat" || s=="mouse";
}

bool isArticle(string s) {
	return s=="a" || s=="the";
}

bool isVerb(string s) {
	if (s.length()<4) return false;
	if (s=="hate" || s=="love" || s=="know" || s=="like") return true;
	if (s[s.length()-1] != 's') return false;
	s=s.substr(0,s.length()-1);
	return isVerb(s);
}

bool isActor(string s) {
	s=trim(s);
	if (isNoun(s)) return true;
	size_t i = s.find_first_of(" ");
	if (i==string::npos) return false;
	string s1=trim(s.substr(0,i));
	string s2=trim(s.substr(i+1));
	return isArticle(s1) && isNoun(s2);
}

bool isActiveList(string s) {
	s=trim(s);
	if (isActor(s)) return true;
	size_t i=s.rfind(" and ");
	if (i==string::npos) return false;
	string s1=trim(s.substr(0,i));
	string s2=trim(s.substr(i+5));
	return isActiveList(s1) && isActor(s2);
}

bool isAction(string s) {
	s=trim(s);

	size_t i1=s.find(" hate"),i2=s.find(" know"),i3=s.find(" love"),i4=s.find(" like");
	
	if (i1!=string::npos) {
		string s1=trim(s.substr(0,i1));
		string s2=trim(s.substr(i1+1));
		if (!isActiveList(s1)) return false;
		size_t i=s2.find(" ");
		if (i==string::npos) return false;
		string s3=trim(s2.substr(0, i));
		string s4=trim(s2.substr(i+1));
		return isVerb(s3) && isActiveList(s4);
	}
	else if (i2!=string::npos) {
		string s1=trim(s.substr(0,i2));
		string s2=trim(s.substr(i2+1));
		if (!isActiveList(s1)) return false;
		size_t i=s2.find(" ");
		if (i==string::npos) return false;
		string s3=trim(s2.substr(0, i));
		string s4=trim(s2.substr(i+1));
		return isVerb(s3) && isActiveList(s4);
	}
	else if (i3!=string::npos) {
		string s1=trim(s.substr(0,i3));
		string s2=trim(s.substr(i3+1));
		if (!isActiveList(s1)) return false;
		size_t i=s2.find(" ");
		if (i==string::npos) return false;
		string s3=trim(s2.substr(0, i));
		string s4=trim(s2.substr(i+1));
		return isVerb(s3) && isActiveList(s4);
	}
	else if (i4!=string::npos) {
		string s1=trim(s.substr(0,i4));
		string s2=trim(s.substr(i4+1));
		if (!isActiveList(s1)) return false;
		size_t i=s2.find(" ");
		if (i==string::npos) return false;
		string s3=trim(s2.substr(0, i));
		string s4=trim(s2.substr(i+1));
		return isVerb(s3) && isActiveList(s4);
	}

	return false;
}

bool isStatement(string s) {
	s=trim(s);
	if (isAction(s)) return true;
  size_t i=s.rfind(",");
	if (i==string::npos) return false;
	string s1=trim(s.substr(0,i));
	string s2=trim(s.substr(i+1));
	return isStatement(s1) && isAction(s2);
}

main() {
	string s;

	while (getline(cin, s)) {
		if (cin.eof())  
			break;
		if (isStatement(s))
			cout << "YES I WILL" << endl;
		else
			cout << "NO I WON'T" << endl;
	}

	return 0;
}
Thanks a lot.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re:

Post by DD » Sat Nov 15, 2008 6:53 am

arc16 wrote:hi,
yes, there might be LOT OF whitespace, including before eol.
so there would be something like:

Code: Select all

___tom__hatess___jerry___,_____mickey loves goofy______
'_' is whitespace
In the WON'T, it's ascii #39.

you could also try this:

Code: Select all

mickey lovess goofy and jerry , tom loves goofy and mickey and jerry,the jerry loves a goofy and a tom and a mickey and the jerry and the tom and the mickey and a jerry and a tom and a mickey,  tom loves a cat  ,jerry loves a dog
the answer is YES
It is interesting that My A.C. program outputs NO for your input. So I guess that there must be spaces before and after a comma in the Judge's inputs.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “Volume 100 (10000-10099)”