Desafio
Escreva um programa que, dado um array booleano bidimensional (equivalente a um bitmap monocromático), produz uma série de polígonos que descrevem o contorno da região que é "verdadeiro" (1).
A entrada é fornecida como uma sequência de caracteres '#'
(hash), ' '
(espaço) e \n
(nova linha). As linhas podem diferir em comprimento; nesse caso, as partes ausentes são consideradas espaços. A saída deve ser uma lista (separada por nova linha) de polígonos, cada polígono representado por uma lista de coordenadas (separada por vírgula).
Exemplos e Requisitos
As coordenadas devem ser listadas no sentido horário. Entrada:
#
Saídas aceitáveis incluem:
(0,0), (1,0), (1,1), (0,1) (1,0), (1,1), (0,1), (0,0) (1,1), (0,1), (0,0), (1,0) (0,1), (0,0), (1,0), (1,1)
Regiões separadas devem retornar vários polígonos. Entrada:
# #
Exemplo de saída (a saída real deve consistir em duas linhas):
(0,0), (1,0), (1,1), (0,1) (2,0), (3,0), (3,1), (2,1)
Os furos em um polígono devem ser listados como um polígono separado, mas na ordem anti-horária. Entrada:
### # # ###
Exemplo de saída:
(0,0), (3,0), (3,3), (0,3) (1,1), (1,2), (2,2), (2,1)
Você é livre para escolher se os vértices adjacentes na diagonal se juntam ou não. Entrada:
# #
Exemplo de saída:
(0,0), (1,0), (1,1), (0,1) (1,1), (2,1), (2,2), (1,2)
ou
(0,0), (1,0), (1,1), (2,1), (2,2), (1,2), (1,1), (0, 1)
As listas de coordenadas não precisam ser otimamente curtas. Por exemplo:
##
Saídas aceitáveis:
(0,0), (2,0), (2,1), (0,1) // Redundant coordinates along a straight line are acceptable (0,0), (1,0), (2,0), (2,1), (1,1), (0,1) // Duplicate start- and end-point are acceptable (0,0), (2,0), (2,1), (0,1), (0,0)
Como sempre, o programa mais curto “vence”.
Respostas:
Perl,
345311265 caracteresLimitações
Supõe que a entrada não tenha mais que 64 caracteres (mas sua altura é, em princípio, ilimitada). Isso pode ser estendido para 512 ou 8192 ou qualquer outra potência de duas, alterando as constantes relevantes, tornando o código apenas um pouco mais longo.
Versão um pouco mais legível
Algum crédito vai para a multidão porque a primeira linha é a minha reutilização de sua ideia em lasers . O resto é inteiramente meu trabalho.
Editar% s
$x
ao dar uma volta, porque a próxima iteração já o fará1
= para baixo,2
= da esquerda para1
= para a esquerda,2
= para baixo e atualize$d
via XOR em vez de diretamentefonte
Python, 607 caracteres
O código funciona mantendo uma lista dos limites descobertos, na medida em que processa os símbolos # na ordem de entrada. Os limites são armazenados em uma tabela E que mapeia arestas (4-tuplas de x_start, y_start, x_end, y_end) para uma lista de arestas que formam o limite de um polígono. À medida que processamos cada novo #, ele pode ser conectado a um polígono acima (p) ou à esquerda (q). O código localiza p e q usando E e depois mescla os limites do atual # (r) com p e q, se eles existirem. O caso em que p == q gera furos.
fonte