Mudei de banco de dados
Estava usando MySQL para aprender melhor a usar.
Cansei e voltei ao meu preferido: PostgreSQL.
Deve ter alguns erros de acentuação por aí, se alguém achar me avisa.
Posted at 09:26PM Dez 14, 2009 by ze in General | Comments[0]
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]
Complicando as coisas
Por causa do trânsito, na quinta passada fiquei até mais tarde no trabalho e participei do Dojo.
Achei o problema escolhido muito interessante e aproveitei ele para praticar um pouco. Depois de acabar, achei que o código que fiz ficou bem legal, e me empolguei para estudar mais.
Escolhi os problemas do Google Code Jam para resolver. No primeiro problema tudo bem, mas já no segundo percebi que eu complico as coisas: o problema era para ser resolvido com uma matriz, e eu fiz uma árvore. Resultado: meu código demorava 30 minutos na versão Python e 1 minuto e meio na versão Java. De um amigo meu demorava meio minuto, e na versão "ótima" (uma gambiarra total), demorava 5 segundos em Python!
Este aqui é outro exemplo de como eu complico as coisas: o problema é um labirinto, e o programa deve ir marcando o caminho. Como não tem o tamanho do labirinto, eu vou ajustando conforme vou andando. Eis o resultado:
import os
import sys
class Maze(object):
'''Maze object.
(r, c):
(0, 0) (0, 1)
(1, 0) (1, 1)'''
# Direction constants
SOUTH = 0
WEST = 1
NORTH = 2
EAST = 3
def _setDirection(self, value):
self._direction = value % 4
direction = property(lambda s: s._direction, _setDirection, None, None)
def invert(self):
self.direction += 2
self._outside = True
def turnRight(self):
self.direction += 1
def turnLeft(self):
self.direction -= 1
# Wall openings
WO_CLOSED = 0
WO_NORTH = 1
WO_SOUTH = 2
WO_WEST = 4
WO_EAST = 8
wo = {
NORTH: WO_NORTH,
SOUTH: WO_SOUTH,
WEST: WO_WEST,
EAST: WO_EAST}
def __init__(self):
self.map = [[Maze.WO_CLOSED]]
self._direction = Maze.SOUTH
self.position = (-1, 0)
self._outside = True
def walk(self):
self._adjustMap()
self._markLast()
row, column = self.position
if self.direction == Maze.SOUTH:
row += 1
elif self.direction == Maze.WEST:
column -= 1
elif self.direction == Maze.NORTH:
row -= 1
elif self.direction == Maze.EAST:
column += 1
self.position = (row, column)
# Inside maze: ajust map
self._outside = False
def _markLast(self):
if self._outside:
return
opening = Maze.wo[self.direction]
row, column = self.position
self.map[row][column] |= opening
def _adjustMap(self):
if self._outside:
return
size = self.position[0] + 1
if size > len(self.map):
self._addRow()
column = self.position[1]
if column < 0:
self._addColumnLeft()
elif column >= len(self.map[0]):
self._addColumnRight()
def _addRow(self):
size = len(self.map[0])
row = []
while len(row) < size:
row.append(Maze.WO_CLOSED)
self.map.append(row)
def _addColumnLeft(self):
for row in self.map:
row.insert(0, Maze.WO_CLOSED)
row, column = self.position
self.position = (row, column + 1)
def _addColumnRight(self):
for row in self.map:
row.append(Maze.WO_CLOSED)
def __str__(self):
'Print inside representantion'
ret = ''
for i in range(0, len(self.map)):
for j in range(0, len(self.map[0])):
ret += "%x" % self.map[i][j]
ret += os.linesep
return ret
if __name__ == '__main__':
x = sys.stdin.readline()
x = int(x)
for i in range(1, x + 1):
maze = Maze()
input = sys.stdin.readline()
input = input.strip()
for command in input:
if command == 'R':
maze.turnRight()
elif command == 'L':
maze.turnLeft()
elif command == 'W':
maze.walk()
elif command == ' ':
maze.invert()
print "Case #%d:" % i
print maze
O switch faz um pouco de falta no final, mas o mais interessante é ficar ajustando o tamanho do mapa conforme vai andando. Depois olhando na net como outras pessoas fizeram, fiquei realmente chateado: bastava usar um dicionário onde as chaves eram as tuplas das casas ex. (0, 0).
Depois postarei o outro problema para mostrar como eu complico demais as coisas.
Posted at 12:38AM Dez 10, 2009 by ze in Python | Comments[0]
Nerd é fogo...
Consegui estragar a minha agenda de telefones do celular: mandei copiar todos os registro para o celular e ele duplicou tudo.
Grande parte da minha agenda já tinha no meu Mac, então era só mandar de volta. Demorei uns 20 minutos para copiar pro Mac os telefones que ainda não tinha e organizar tudo, apaguei toda a agenda do telefone e mandei via Bluetooth para o celular.
Tudo certo? Não, o celular não tinha a agenda.
O que aconteceu? Percebi que só o primeiro registro foi com sucesso. O segundo estava corrompido? Não, a droga do meu celular (Samsung) só lia um registro.
O que para a maioria das pessoas era caso perdido, nas mãos de um nerd existe esperança. Salvei dois registros em arquivos separados e tentei mandar os 2 arquivos para ver o que rolava. Sucesso! Só que salvar todos os telefones em arquivos separados ia dar trabalho.
Agora a parte mais nerd: exportei toda a minha agenda para um arquivo e fiz um programa que salvava cada registro em um arquivo, assim consegui recuperar a minha agenda.
linhas = open('varcds.vcf').readlines()
registro = []
i = 0
for linha in linhas:
registro.append(linha)
if linha == 'END:VCARD\r\n':
saida = open('%d.vcf' % i, 'w')
saida.writelines(registro)
saida.close()
registro = []
i += 1
Posted at 08:07PM Nov 08, 2009 by ze in General | Comments[1]
Império brasileiro
Gosto de falar de política, mas depois que percebi que ninguém convence ninguém, tento guardar os meus pensamentos só para mim, isso evita discussões bestas com os meus amigos.
Mas blog pessoal é pra isso então vou aproveitar pra falar aqui. Espero não irritar muito meus 02 leitores (tirando eu e o Google).
Uma coisa que vem me incomodando ultimamente é como tudo passa por Brasília. Decisões econômicas, o rumo do país, bom, isso beleza, mas por que o Rodoanel? Metrô de São Paulo???
Pois é. Tudo o que envolve governo hoje está passando por Brasília. Não importa se é uma praça ou a calçada do bairro (estou exagerando!), mas acho péssimo para o país levar discussões regionais para o centro do poder. Não quero saber se existe lei para o gado não passar no meio das cidades do Mato Grosso, sobre detalhes de outras regiões, mas o prefeitos e os governadores parecem com menos poder que antes. Acho que esse país está virando um império rotativo. O cara vira presidente e pode tudo por 4 anos. Bizarro.
Outra coisa que me incomoda, e essa é específica do governo Lula é <ironia>o complexo de inferioridade.</ironia> Por que toda inauguração, discursos, pronunciamentos, é necessário criticar a oposição? Por que precisamos ficar comparando com o passado todo tempo? Pelo que me lembro os outros presidentes aproveitavam essa ocasião para enaltecer seu atos ao invés de ficar criticando os outros. Não podemos pensar para frente? Odeio isso nesse governo, tudo é política, tudo se torna uma luta do bem contra o mal. Coitada da mulher desse cara, ela que deve sofrer. O cara fechou ele no trânsito? "Oposição". Não pode pagar com cartão de crédito? "Oposição". Tudo é contra, que saco! E na verdade isso é o mal do partido, não só do nosso "chefe".
Só espero que quando eu tiver o meu apartamento o síndico não seja petista, pois sei que qualquer um contra a idéia dele virará inimigo mortal.
Posted at 02:16PM Nov 07, 2009 by ze in General | Comments[1]
Ainda na luta pela casa própria
Procurar imóvel nesses tempos está uma droga.
Prova disso é o stress dos corretores de imóveis, que estão apertando o cinto e com um stress que parece de bolsa de valores.
Achei que ontem fosse finalmente ter um ap. meu, concidentemente no mesmo quarteirão de um amigo que foi meu vizinho durante quase 20 anos.
Mas o sonho durou pouco. O proprietário, provavelmente um perdido na vida, resolveu que queria mais. Até aí tudo bem já que se eu achei que estava em um preço bom, significa que ele não estava inflacionado. Só que ele pediu um valor absurdo a mais. Só me fez perder tempo o maluco, que ódio!
Preciso entender melhor o mercado imobiliário: a sensação de gastar uma grana violenta e o medo de que não seja a decisão correta são cosisas muito estressantes.
Posted at 11:00AM Out 30, 2009 by ze in General | Comments[0]
Site de games, principalmente das antigas
Estou fissurado por jogos antigos. Não tenho mais paciência de ficar aprendendo coisas novas. Dois botões são o suficiente para você não pensar e se divertir (obviamente a minha opinião).
Comecei a olhar esse site por causa do Angry Video Game Nerd, um maluco que faz reviews de jogos antigos zoados, principalmente de 8-bits.
Pra quem gosta de jogos, bem legal: ScrewAttack.com
Posted at 02:49PM Out 26, 2009 by ze in General | Comments[0]
Presente
Meu aniversário ainda está longe, mas já vou começar a fazer a lista de coisas que quero.
Posted at 08:08PM Ago 16, 2009 by ze in General | Comments[0]
