Idéia interessante
Wiki crimes: Um wiki para mapearmos o crime nas cidades. Gosto do conceito de cidadãos ajudando o poder público.
Tem uma parte de mobile, mas não tenho celular que consegue abrir essas coisas, mas teríamos a possibilidade de evitar regiões sabendo que ela é perigosa.
Posted at 10:38PM Jan 14, 2010 by ze in General | Comments[0]
Duas semanas sem carro
Senti muita falta do carro nesses dias quentes. Muito ruim andar de ônibus no Sol!
Ainda estou resistindo, no começo foi bem mais difícil, agora já me acostumei um pouco.
Posted at 10:36PM Jan 14, 2010 by ze in Trânsito | Comments[1]
Ano de mudança de hábito
Esse é o ano que deixarei novamente de usar o carro para ir trabalhar. Não usei carro no ano que trabalhei na Paulista, pois realmente demorava mais cruzar a Paulista do que ir de metro e na SAP só usei carro porque o estacionamento era de graça.
Desta vez usarei ônibus ao invés de metro, mas acho que logo me habituo.
Posted at 10:57AM Jan 02, 2010 by ze in Trânsito | Comments[0]
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]
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]
