2005 Canadian Computing Competition, Stage 1

Problem J5: Bananas

The term “code monkey” is sometimes used to refer to a programmer who doesn't know much about programming. This is unfair to monkeys, because contrary to popular belief, monkeys are quite smart. They have just been misunderstood. This may be because monkeys do not speak English, but only monkey language. Your job is to help humans and monkeys understand each other by writing a monkey language dictionary. For each word that is typed in, your program must determine whether it is a valid monkey language word.

Unlike in English, spelling in monkey language is very simple. Every word in monkey language satisfies the following rules, and every word satisfying the following rules is a monkey language word.

  1. A monkey language word is a special type of word called an A-word, which may be optionally followed by the letter N and a monkey language word.
  2. An A-word is either only the single letter A, or the letter B followed by a monkey language word followed by the letter S.

Here are some examples:

  • The word “A”' is a monkey language word because it is an A-word.
  • The word “ANA” is a monkey language word because it is the A-word “A” followed by the letter N and the monkey language word “A”.
  • The word “ANANA” is a monkey language word because it is the A-word “A” followed by the letter N and the monkey language word “ANA”.
  • The word “BANANAS” is a monkey language word because it is an A-word, since it is the letter B followed by the monkey language word “ANANA” followed by the letter S.

Write a program which accepts words, one word on each line, and for each word prints YES if the word is a monkey language word, and NO if the word is not a monkey language word. The input word “X” indicates the program should terminate, and there is no output for word “X” (even though it is not a monkey word).

Sample Input

A
ANA
ANANA
BANANAS
BANANA
X

Sample Output

YES
YES
YES
YES
NO

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 04, 2008

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

<
1
2
>

Is there any way to catch errors in Ruby without getting a runtime error? I tested using CEMC data on my machine and it all worked fine, but the grader is giving RE. I realize my solution is.... pretty hacky (I prefer the word 'elegant')

Haha that took me way too long to figure out. Guess my Ruby is rusty...

Your problem is with Kernel#exit!, not with rescue. Kernel#exit! by default will result in an exit failure (a nonzero exit code on *nix), whereas Kernel#exit will result in a successful exit. Kernel#exit! is really more like an abort; you should really only be calling it when something has gone horribly wrong.

To fix, replace your Kernel#exit! with either Kernel#exit or just a break. Or, you could call exit!(true) to force returning an exit success code.

That did the trick, thanks

Well I was looking at this problem and there seems to be a typo?

The sample input has

AA
NA

Shouldn't it be

A
ANA

?


ah this problem reminds me of a book i bought for 7 dollars in the US called Compiler Construction
inside is full of those things like CFG

Why are people constantly asking about whether or not things are monkey language words???
It's been explained several times, both in the problem itself and in many comments below. If you can't understand after all that, then you honestly just shouldn't be doing this problem yet...

but shouldnt this be possible?:

BASNBASNANANA

Because it says that an a-word can be followed by an N, and an a-word could be defined has having a B in front and an S at the end.

Yes, that is a valid monkey language word.

<monkey-word> ::= <a-word> | <a-word> "N" <monkey-word>
<a-word> ::= A | "B" <monkey-word> "S"

Or, if greater conciseness is desired,
<monkey-word> ::= "A" | "B" <monkey-word> "S" | <monkey-word> "N" <monkey-word>

(Challenge: Prove that these two grammars are equivalent.)

You should not be having any trouble understanding the problem statement. The problem statement is very clear. If you don't understand it, you can't be trying hard enough - especially considering the amount of discussion on this problem.

so is this possible?

BBANASANAS

No, BBANASANAS is not a monkey language word. If we assume that it is B + monkey word + S, then the monkey language word within must be BANASANA. Here, the B and S must be matched, so it must have BANAS as a smaller monkey language word contained within. But look, it is followed by ANA. A monkey language word can never be followed by A to form another monkey language word; it has to be followed by either S (if it is preceded by A) or N (if the N is then followed by another monkey language word.)

If, on the other hand, we consider it to be two monkey language words joined together with a 'N' between them, we get the possibilities:
BBA + N + ASANAS
BBANASA + N + AS
In each case, the numbers of B and S are unbalanced, so these are obviously incorrect.

Having found no way to decompose BBANASANAS into smaller monkey language words according to the given rules, we conclude that it is not a monkey language word.

I still have 2 questions:

Can you have double or triple brackets made up of B S.

Is the 'N' optional after the 'A' or it must be there?

1: As in BBANASS? Yes.

2: What do you mean? Attention to line:
A monkey language word is a special type of word called an A-word, which may be optionally followed by the letter N and a monkey language word.
Therefore, 'A' is a monkey language word.

what if the inputted string is in lowercase - does it matter?

I don't think there are any such cases. Whatever the case may be, assume that they're all uppercase.


No it is not, it has to contain at least one letter A.

monkey words are joined together by 'N'
Also, some monkey words start with 'B' but must end in 'S'

darn it scott, you're supposed to let him figure it out himself.

LOL, all you did was restate the problem statement...

nope, I reworded it here and there.

A monkey language word is a special type of word called an A-word, which may be optionally followed by a "N" or a monkey language word.

An A-word is either:
1) The Letter "A"
2) B followed by a monkey language word followed by an "s".

Using these rules, it can be determined whether or not "BNBNBNBNS" is a monkey language word.

Nope, If it has a B it has to have a S to enclose the monkey word, think of the B and S as brackets. You can't have an open bracket that doesn't have a close bracket.