GCJ 2009: Alien Language
Aliens are here again, after their numbers it’s the language turn. Googlers must like them very much, this was the first problem for the qualification round:
You can find the original text here (registration may be required)
Here is my solution in python:
#!/usr/bin/python import sys import re import psyco psyco.full() rdl = sys.stdin.readline def process(case): """precessing case #""" pattern = rdl().replace('(','[').replace(')',']') count = 0 reg = re.compile(pattern) for w in words: if reg.match(w): count += 1 return str(count) L, D, cases = [int(i) for i in rdl().split()] words = [rdl() for dumb in xrange(D)] for case in xrange(1, cases+1): print "Case #%d:"%case, process(case)
The problem was about simple pattern matching, so what tool is better than regex? I simply replaced each ( with a [ and each ) with a ], made a list of words and testing all words against each pattern.
Compiling each regex before the for loop make time of execution drop from 9s to 3s for large input files. This one was very very simple to solve this way.
How did/would you solve this?
September 15th, 2009 at 3:36 pm
[…] I say that maybe Googlers like aliens? Of course they do! Actually they like also to make cool, not so hidden, citations, but […]
September 21st, 2009 at 12:54 am
Same here. I did use the same technique. Compiling the regex also improved the running time a lot in Java.
I felt like cheating
October 12th, 2009 at 6:56 pm
I felt like that too, but that’s not cheating, it’s using the right tool for the right job
November 17th, 2009 at 3:28 am
thats wrong…
isnt [az] … is (a|z). a OR z, not a to z.
November 17th, 2009 at 3:51 pm
@Mathias Grimm: it works in both ways.
(a|z) is a group and means match a OR z.
[az] is a character class, it means match any of the character in the list “az”, and it’s equivalent to a OR z.
If you wanted a TO z inside a character class you need to use [a-z] with the “-”.
Thanks for stopping by