Alien Language - GCJ 2009

...Just finished the qualification round of 'Google Code Jam - 2009', passed through and just thought of posting this simple solution to the first problem, called 'Alien Language'. Here's the problem description:


Problem Statement
-----------------

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.

Input
-----

The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.

Output
------

For each test case, output Case #X: K where X is the test case number, starting from 1, and K indicates how many words in the alien language match the pattern.

Limits
------

Small dataset
-------------

1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10

Large dataset
-------------

1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500

Sample Input
------------

3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc

Output
------

Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0


The solution to this problem is pretty simple, if you could figure it out, that its tailor-made for regular expressions. I used Java. So, I could create a solution, with just a couple of code statements. Here's the solution:

4 comments:

  1. thats wrong!!!

    for input mno and test (az)(az)(az)

    this will be replaced bu [az][az][az]
    can you see dead people?
    this is equivalent to a or b or c or d... or z

    the correct must be (a|z)(a|z)(a|z)

    ReplyDelete
  2. Hello Mathias,
    Looking at your comment, I knew that it was wrong. But anyways, I tried running the program with your test case and other similar inputs, but it works good! The program returns '0' for your test case and '1' for the word 'aza'.

    Apart from this proof, the other proof is that, it passed the 'Google Code Jam' testing phase.

    You can try running that code, with your test case and also other inputs like 'aza' for the pattern, you posted. Thanks for posting the comment! :)

    ReplyDelete
  3. great.. perfect solution !

    ReplyDelete
  4. HOW I GOT MY LOAN (Lexieloancompany@yahoo.com)!!!

    My Name is Nicole Marie, I live in USA and life is worth living comfortably for me and my family now and i really have never seen goodness shown to me this much in my life, As i am a struggling mum with two kids and i have been going through a serious problem as my husband encountered a terrible accident last two weeks, and the doctors stated that he needs to undergo a delicate surgery for him to be able to walk again and i could not afford the bills for his surgery then i went to the bank for a loan and they turn me down stating that i have no credit card, from there i ran to my father and he was not able to help me, then when i was browsing through yahoo answers i came across a God fearing man (Mr Martinez Lexie) who provides loans at an affordable interest rate and i have been hearing about so many scams on the Internet mostly Africa, but at this my desperate situation, i had no choice than to give it an attempt due to the fact that the company is from United State of America, and surprisingly it was all like a dream, i received a loan of $82,000.00 USD and i payed for my husband surgery and thank GOD today he is ok and can walk, my family is happy and i said to myself that i will shout to the world the wonders this great and God fearing Man Mr Martinez Lexie did for me and my family; so if anyone is in genuine and serious need of a loan do contact this GOD fearing man via Email: ( Lexieloancompany@yahoo.com ) or through the Company website: http://lexieloans.bravesites.com OR text: +18168926958 thanks



    ReplyDelete

Note: Only a member of this blog may post a comment.