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.
- 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.
- 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
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
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.
The sample input has
AA
NA
Shouldn't it be
A
ANA
?
inside is full of those things like CFG
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...
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.
<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.
BBANASANAS
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.
Can you have double or triple brackets made up of B S.
Is the 'N' optional after the 'A' or it must be there?
2: What do you mean? Attention to line:
monkey words are joined together by 'N'
Also, some monkey words start with 'B' but must end in 'S'
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.