Woburn Challenge 1996

Problem 3: Hidden Geography

Remember those old puzzles where a word was hidden inside a seeming innocuous sentence? For example, "Should I jump on to the red target, or on to the blue one?" contains the hidden word "Toronto" (... red target, or on to the...) Given a line of text, your task is to search for a hidden province of Canada in it: British Columbia, Alberta, Saskatchewan, Manitoba, Ontario, Quebec, Nova Scotia, Newfoundland, New Brunswick, PEI. The hidden word may appear anywhere in the text with its letters will be in the correct order, may contain upper and/or lower case letters, and may have any non-letter characters such as punctuation or characters in between.

Input

There will be five lines in the input, each containing a line of text which your program must search for provinces in.

Output

For each input print the name of the hidden province: British Columbia, Alberta, Saskatchewan, Manitoba, Ontario, Quebec, Nova Scotia, Newfoundland, New Brunswick, PEI. If no province is found then output NO PROVINCE FOUND.

Sample Input

For the best value in food and amusements, ask at Chew and View.
The protesters are prepared to confront a riot squad.
Should I jump on to the red target, or on to the blue one?
This line is a particularly wasteful and not too productive test case, methinks.

(and 1 more data set)

Sample Output

Saskatchewan
Ontario
NO PROVINCE FOUND
NO PROVINCE FOUND

All Submissions
Best Solutions


Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008

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

Comments (Search)

There is an error in the 4th line: 'This line is a particularly wasteful and not too productive test case, methinks.'

The output should not be 'NO PROVINCE FOUND', but 'PEI'.

I don't see why. Can you point out where the PEI occurs?

particularly wasteful methinks

There may only be non-letter characters between letters of the hidden word.

Thank you for clarifying the question,

Can you also fix this:

The hidden word may appear anywhere in the text with its letters will be in the correct order, may contain upper and/or lower case letters, and may have any non-letter characters such as punctuation or characters in between

It should probably say:
There may only be non-letter characters between letters of the hidden word