Posts Tagged ‘regex’
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?