Desafío
Escriba un programa que, dada una matriz booleana bidimensional (equivalentemente, un mapa de bits monocromático), emite una serie de polígonos que describen el esquema de la región que es "verdadero" (1).
La entrada se proporciona como una secuencia de caracteres '#'
(hash), ' '
(espacio) y \n
(nueva línea). Las líneas pueden diferir en longitud, en cuyo caso se supone que las partes faltantes son espacios. La salida debe ser una lista de polígonos (separados por una nueva línea), cada polígono representado por una lista de coordenadas (separadas por comas).
Ejemplos y requisitos
Las coordenadas deben estar listadas en el sentido de las agujas del reloj. Entrada:
#
Los resultados aceptables incluyen:
(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)
Las regiones disjuntas deben devolver múltiples polígonos. Entrada:
# #
Ejemplo de salida (la salida real debe constar de dos líneas):
(0,0), (1,0), (1,1), (0,1) (2,0), (3,0), (3,1), (2,1)
Los agujeros en un polígono se deben enumerar como un polígono separado, pero en orden antihorario. Entrada:
### # # ###
Salida de ejemplo:
(0,0), (3,0), (3,3), (0,3) (1,1), (1,2), (2,2), (2,1)
Usted es libre de elegir si los vértices adyacentes en diagonal se unen o no. Entrada:
# #
Salida de ejemplo:
(0,0), (1,0), (1,1), (0,1) (1,1), (2,1), (2,2), (1,2)
o
(0,0), (1,0), (1,1), (2,1), (2,2), (1,2), (1,1), (0, 1)
Las listas de coordenadas no necesitan ser óptimamente cortas. Por ejemplo:
##
Salidas aceptables:
(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 de costumbre, el programa más corto "gana".
Respuestas:
Perl,
345311265 caracteresLimitaciones
Asume que la entrada no tiene más de 64 caracteres (pero su altura es en principio ilimitada). Esto puede extenderse a 512 u 8192 o cualquier otra potencia de dos cambiando las constantes relevantes, haciendo que el código solo sea un poco más largo.
Versión ligeramente más legible
Algo de crédito va a la mafia porque la primera línea es mi reutilización de su idea en los láseres . El resto es completamente mi trabajo.
Ediciones
$x
al tomar un turno porque la próxima iteración ya lo hará1
= abajo,2
= izquierda a1
= izquierda,2
= abajo y actualizar a$d
través de XOR en lugar de directamentefuente
Python, 607 caracteres
El código funciona manteniendo una lista de los límites descubiertos en la medida en que procesa # símbolos en orden de entrada. Los límites se almacenan en una tabla E que asigna bordes (4-tuplas de x_start, y_start, x_end, y_end) a una lista de bordes que forman el límite de un polígono. A medida que procesamos cada nuevo #, puede estar conectado a un polígono arriba (p) o a su izquierda (q). El código encuentra p y q usando E y luego combina el límite del # (r) actual con p y q, si existen. El caso donde p == q genera agujeros.
fuente