zefacts Blog do Zé

Code Jam: Alien Language

O problema é esse: você tem uma lista de palavras, e dadas algumas expressões, você quer saber a quantidade de palavras que ela pode formar:

lista: abc, bbc
expressão: (abc)(bd)c
número: 2

Simples não? Pois bem, fui resolver o problema.

Minha primeira preocupação foi em transformar a expressão em uma lista de palavras. Para isso fiz uma função recursiva. Nada muito complicado... exceto que python não é a linguagem mais rápida que existe. E se estourar a memória? Afinal as entradas eram grandinhas. Outro problema é a performance: por que comparar no caso acima cbc e cdc se eu sei que não existe palavra que começa com c?

O que fiz: criei uma árvore para comparar e dado uma string, ele me diz se é uma palavra ou parte de uma palavra.

Eis o programa:

import sys
from bisect import bisect


class Node(object):

    def __init__(self, name):
        self._name = name
        self._children = []

    def add(self, word):
        if not word:
            return
        a = word[0]
        node = None
        for item in self._children:
            if item._name == a:
                node = item
                break

        if not node:
            node = Node(a)
            self._children.append(node)
            self._children.sort()
        node.add(word[1:])

    def search(self, word):
        if not word:
            return True

        a = word[0]
        a = Node(a)
        i = bisect(self._children, a) - 1
        if i < 0:
            return False
        node = self._children[i]
        if a != node:
            return False
        return node.search(word[1:])

    def __cmp__(self, other):
        return cmp(self._name, other._name)


def parse_words(to_parse, parsed):
    global tree
    if not to_parse:
        if tree.search(parsed):
            return 1
        else:
            return 0

    if not tree.search(parsed):
        #print "discarded:", parsed
        return 0

    if to_parse.startswith('('):
        end = to_parse.find(')')
        sub = to_parse[end + 1:]
        ret = 0
        for item in to_parse[1:end]:
            ret += parse_words(sub, parsed + item)
        return ret
    else:
        return parse_words(to_parse[1:], parsed + to_parse[0])

if __name__ == '__main__':
    input = sys.stdin.readline()
    input = input.split()

    tree = Node('')

    for i in range(0, int(input[1])):
        word = sys.stdin.readline()
        tree.add(word)

    for i in range(1, int(input[2]) + 1):
        line = sys.stdin.readline()
        line = line.strip()
        ret = parse_words(line, '')
        print("Case #%d: %d" % (i, ret))

 Legal, resolvi até que rápido e a solução ficou até bonitinha. Só que a segunda entrada demorou 30 minutos pra processar! Usando "python -m cProfile alien_language.py" descobri que o gargalo era a comparação.

Fiz a mesma solução em Java e ela demorava 1 minuto e meio para executar. Bem melhor, mas será que todo mundo fez assim?

Olhando na internet, vi que as soluções mais comuns eram muitos mais simples que a minha: sabendo o tamanho da lista e o tamanho das palavras, é só criar uma matriz com todas as alternativas possíveis e depois comparar. Sem recursão, sem medo de estourar a memória (já sabemos o tamanho de antemão) nem nenhuma outra complicação! E executa rapidão.

A melhor solução que encontrei no entanto foi essa, em python mesmo:

import re
import sys

input = sys.stdin.readline()
input = input.split()

list = []

for i in range(0, int(input[1])):
    word = sys.stdin.readline()
    list.append(word)

for i in range(1, int(input[2]) + 1):
    line = sys.stdin.readline()
    line = line.strip()
    line = line.replace('(', '[')
    line = line.replace(')', ']')
    ret = 0
    m = re.compile(line)
    for item in list:
        if m.match(item):
            ret += 1
    print("Case #%d: %d" % (i, ret))

Bem mais simples não? E bem rápida

Posted at 01:18PM Dez 12, 2009 by ze in Python  |  Comments[0]