zefacts Blog do Zé

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]