São Paulo em 1972
Realmente para viver em São Paulo é preciso saber driblar o trânsito.
Tentei a bicicleta, mas pela falta de chuveiro onde trabalho a coisa fica desconfortável, principalmente no verão.
Agora meu problema não é só o trânsito, também tem o stress dos motoristas, porque carro não foi feito para ficar parado, nem foi para isso que o cidadão comprou. Isso irrita eles e eles me irritam.
Minha solução atual: ônibus. Não chegarei mais rápido ao trabalho, mas pelo menos chegarei menos irritado, e ainda economizo uns trocos do preço do estacionamento.
Essa é a minha promessa de ano novo. Para ela se efetivar é fácil: basta parar de pagar o estacionamento.
Vou ver no que dá.
Peguei a foto da seguinte reportagem: São Paulo precisaria de 125 avenidas Paulistas por ano para absorver carros novos, afirma especialista.
Posted at 01:43PM Dez 23, 2009 by ze in Trânsito | Comments[0]
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]
