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.