Blog

Navegando em grids em Python (desafios de programação)

23 Dec 2017

No problema de ontem do Advent of Code, era preciso navegar em um grid infinito. Muitos problemas de desafios de programação envolvem navegar em um grid.

Um grid é um tipo de grafo que representa um espaço 2D. Pode ser representada por uma matrix. Para acessar o elemento que está na posição (x, y) é só acessar o elemento arr[y][x] da matrix arr. Então as posições dos elementos no grid ficam dispostas da seguinte maneira:

(0,0) (1,0) (2,0)
(0,1) (1,1) (2,1)
(0,2) (1,2) (2,2)
     

Em geral só é possível andar em quatro direções, mas algumas vezes é possível andar diagonalmente também. Note que para representar como uma tabela nós invertemos os eixos. O y que é a linha da matrix cresce para baixo. Assim a posição acima do ponto (x,y) é (x,y-1).

No problema de ontem, o grid era infinito. Isso complica um pouco o problema. Se você sabe o tamanho máximo do grid é só criar uma tabela grande e navegar normalmente (listas em Python aceitam índices negativos, em outra linguagem é só usar o módulo).

Para simplificar as coisas eu uso um dicionário para representar o grid. Assim as chaves no dicionário são tuplas. Para acessar o elemento que está na posição (x, y) é só acessar o elemento dic[(x,y)] do dicionário dic. Assim não precisamos saber o tamanho final que terá o dicionário. Se você precisar imprimir o grid na tela é só guardar o x e y mínimos que foram usados.

Movendo-se no grid

Partindo de uma posição inicial x,y é possível se mover somando-se valores nessas coordenadas. Assim as quatro direções são:

dirs = [(0,-1), (-1,0), (0,1), (1,0)]

Guardar as direções numa lista é útil também quando queremos pegar todos os vizinhos de uma certa posição:

def neighbors(x, y): 
    return [ (x + x1, y + y1) for x1, y1 in [(0,-1), (-1,0), (0,1), (1,0)]]

Virando a direita ou a esquerda

Se mantivermos as direções em uma lista ordenada é possível rotacionar a direção navegando na lista:

dirs = [(0,-1), (-1,0), (0,1), (1,0)]
dir = 0 # direção inicial é para cima
# virando a direita (90 graus)
dir = (dir - 1) % 3
# virando a esquerda (270 graus)
dir = (dir + 1) % 3
# virando 180 graus
dir = (dir + 2) % 3

Esse é o básico de como lidar com grids em desafios de programação, se você quiser ver mais posts como esse por aqui deixe um comentário.


Python Cheat Sheet

09 Dec 2017

Profissionalmente eu uso C++. Mas para desafios de programação como o Project Euler e Advent of Code, eu costumo usar Python. O problema é mudar de contexto e lembrar como fazer as coisas em python. Por isso eu fiz essa pequena cola de Python para uso pessoal. Espero que isso possa ajudar alguém também.

Com o tempo eu vou editar e adicionar mais coisas a essa lista.

Estrututras de dados

O Defaultdict é um dicionário que não lança uma exceção quando não acha alguma chave, ele retorna um valor padrão:

from collections import defaultdict

dd = defaultdict(int)

Flat de uma matriz (um nível):

list(itertools.chain.from_iterable([[1,2], [3]])) # [1,2,3]

Rotacionar uma matrix:

def rotate(m): return list(map(list, zip(*list(m)[::-1])))

rotate([[1,2],[3,4]]) # [[3, 1], [4, 2]]

Tamanho de únicos em uma lista:

len(set([1,2,2])) == 2

Contar elementos:

[1,2,2].count(2) == 2

Percorrer lista com índices:

for i, value in enumerate([1,2]): print(i, value)

Percorrer dicionário:

for key, value in d.items(): print(key, value)

Pegar o máximo de uma lista de acordo com uma função:

max(arr, key=f)

Strings

','.join([1,2,3]) == '1,2,3'

Detectando se uma string é um inteiro

# não detecta números negativos
"12".isdigit()
# pode ser substituído por float
try:
    return int(y)
except ValueError:
    # faz outra coisa

Lendo a entrada

import sys
sys.stdin.readlines()
input() # read string
eval(input()) #parse next argument
# lê entrada pa/53
p = re.search(r'p([a-p])/(\d+)', move)
a, b = p.group(1), p.group(2)

Funcional

from functools import reduce

reduce(lambda s, x: s + x], [1,2,3], 0) == 6

itertools

O módulo itertools é muito útil. Aqui algumas funções úteis:

import itertools

list(itertools.combinations([1,2,3], 2)) # [(1, 2), (1, 3), (2, 3)]
list(itertools.permutations([1,2,3], 2)) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

Arquivo do blog

Nov 26, 2017 Como a análise de algoritmos vai te fazer um programador melhor
Mar 12, 2017 Links semanais - Untrusted, ES6 e Migrações
Mar 4, 2017 Automatize a criação de mocks com cachemock
Jan 22, 2017 Desenvolvedores não são pagos para escrever código
Nov 22, 2016 Código sagaz
Nov 4, 2016 Percorrendo árvores com generators e com o iteradores em ES6
Sep 17, 2016 O que eu aprendi escrevendo código por 100 dias
Aug 28, 2016 Design Patterns em Javascript - Decorator
Jul 24, 2016 Super no ES2015 não funciona bem como você acha que funciona
Jun 22, 2016 Jogo com múltiplas salas com global-state
Jun 15, 2016 Como funciona e como usar o global-state
Jun 2, 2016 Projeto Open-Source: global-state
Jan 25, 2016 Algoritmos em Javascript: Força Bruta
Nov 2, 2015 TDC, BrazilJS e Clube da Batalha
Aug 15, 2015 Dependência circular entre teoria e prática
Jul 27, 2015 Chat em Angular
Jun 7, 2015 The Start-Up of You - resenha do livro
May 16, 2015 RSJS 2015
Apr 20, 2015 Chat com Backbone.js e Express.js
Apr 18, 2015 Dissertação de Mestrado
Apr 5, 2015 Usando a API do CPLEX para C++
Feb 13, 2015 Trocando make por rake
Feb 12, 2015 Deployment Contínuo
Jul 20, 2013 Tuplas em C++