Nota: El título de esta pregunta debe ser "Loop It", pero debido a que el título debe tener al menos 15 caracteres, hay algunos espacios invisibles. Esta nota es tal que se puede buscar el desafío.
Reto
Dada una lista finita de puntos integrales únicos en el plano, encuentre un polígono cuyos vértices sean exactamente esos puntos, que no se intersecan por sí mismos.
Detalles
- Como entrada puede tomar, por ejemplo, dos listas con cada una de las coordenadas x e y o una lista de pares.
- La lista de entrada contiene al menos 3 puntos.
- Tenga en cuenta que esto significa que nunca hay una solución única.
- Se puede suponer que la lista de entradas no es co-lineal (los puntos no pueden estar contenidos en una línea), esto significa que en realidad existe un polígono que no se auto-intersecta.
- Los ángulos en cada vértice son arbitrarios, esto incluye 180 °.
- Para una entrada de longitud
n
, la salida debe ser una permutación(p1,p2,p3,...,pn)
de(1,2,3,...,n)
donde lak
entrada -thpk
representa elp
punto -th en la lista de entrada. Esto significa que tenemos una línea desdep1
hastap2
, una línea desdep2
hastap3
etc., así como una línea desdepn
hastap1
. (También puede usar los índices basados en 0). Alternativamente , puede simplemente generar la lista de puntos de entrada en el orden correcto.
Ejemplos
Digamos que tenemos los puntos [(0,0),(0,1),(1,0),(-1,0),(0,-1)]
y queremos representar la siguiente ruta:
Esto significa que sacaríamos la lista [5,1,4,2,3]
Aquí hay más sugerencias para probar (recomiendo mirar las parcelas correspondientes para verificar los objetivos).
Triangle
[(0,0),(0,1),(1,0)]
S-Curve
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(2,0),(2,1),(2,2),(2,3),(2,4),(3,4),(4,0),(4,1),(4,2),(4,3),(4,4)]
L-Shape
[(4,0),(1,0),(3,0),(0,0),(2,0),(0,1)]
Menger Sponge
[(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(9,1),(10,1),(11,1),(12,1),(13,1),(14,1),(15,1),(16,1),(17,1),(18,1),(19,1),(20,1),(21,1),(22,1),(23,1),(24,1),(25,1),(26,1),(27,1),(1,2),(3,2),(4,2),(6,2),(7,2),(9,2),(10,2),(12,2),(13,2),(15,2),(16,2),(18,2),(19,2),(21,2),(22,2),(24,2),(25,2),(27,2),(1,3),(2,3),(3,3),(4,3),(5,3),(6,3),(7,3),(8,3),(9,3),(10,3),(11,3),(12,3),(13,3),(14,3),(15,3),(16,3),(17,3),(18,3),(19,3),(20,3),(21,3),(22,3),(23,3),(24,3),(25,3),(26,3),(27,3),(1,4),(2,4),(3,4),(7,4),(8,4),(9,4),(10,4),(11,4),(12,4),(16,4),(17,4),(18,4),(19,4),(20,4),(21,4),(25,4),(26,4),(27,4),(1,5),(3,5),(7,5),(9,5),(10,5),(12,5),(16,5),(18,5),(19,5),(21,5),(25,5),(27,5),(1,6),(2,6),(3,6),(7,6),(8,6),(9,6),(10,6),(11,6),(12,6),(16,6),(17,6),(18,6),(19,6),(20,6),(21,6),(25,6),(26,6),(27,6),(1,7),(2,7),(3,7),(4,7),(5,7),(6,7),(7,7),(8,7),(9,7),(10,7),(11,7),(12,7),(13,7),(14,7),(15,7),(16,7),(17,7),(18,7),(19,7),(20,7),(21,7),(22,7),(23,7),(24,7),(25,7),(26,7),(27,7),(1,8),(3,8),(4,8),(6,8),(7,8),(9,8),(10,8),(12,8),(13,8),(15,8),(16,8),(18,8),(19,8),(21,8),(22,8),(24,8),(25,8),(27,8),(1,9),(2,9),(3,9),(4,9),(5,9),(6,9),(7,9),(8,9),(9,9),(10,9),(11,9),(12,9),(13,9),(14,9),(15,9),(16,9),(17,9),(18,9),(19,9),(20,9),(21,9),(22,9),(23,9),(24,9),(25,9),(26,9),(27,9),(1,10),(2,10),(3,10),(4,10),(5,10),(6,10),(7,10),(8,10),(9,10),(19,10),(20,10),(21,10),(22,10),(23,10),(24,10),(25,10),(26,10),(27,10),(1,11),(3,11),(4,11),(6,11),(7,11),(9,11),(19,11),(21,11),(22,11),(24,11),(25,11),(27,11),(1,12),(2,12),(3,12),(4,12),(5,12),(6,12),(7,12),(8,12),(9,12),(19,12),(20,12),(21,12),(22,12),(23,12),(24,12),(25,12),(26,12),(27,12),(1,13),(2,13),(3,13),(7,13),(8,13),(9,13),(19,13),(20,13),(21,13),(25,13),(26,13),(27,13),(1,14),(3,14),(7,14),(9,14),(19,14),(21,14),(25,14),(27,14),(1,15),(2,15),(3,15),(7,15),(8,15),(9,15),(19,15),(20,15),(21,15),(25,15),(26,15),(27,15),(1,16),(2,16),(3,16),(4,16),(5,16),(6,16),(7,16),(8,16),(9,16),(19,16),(20,16),(21,16),(22,16),(23,16),(24,16),(25,16),(26,16),(27,16),(1,17),(3,17),(4,17),(6,17),(7,17),(9,17),(19,17),(21,17),(22,17),(24,17),(25,17),(27,17),(1,18),(2,18),(3,18),(4,18),(5,18),(6,18),(7,18),(8,18),(9,18),(19,18),(20,18),(21,18),(22,18),(23,18),(24,18),(25,18),(26,18),(27,18),(1,19),(2,19),(3,19),(4,19),(5,19),(6,19),(7,19),(8,19),(9,19),(10,19),(11,19),(12,19),(13,19),(14,19),(15,19),(16,19),(17,19),(18,19),(19,19),(20,19),(21,19),(22,19),(23,19),(24,19),(25,19),(26,19),(27,19),(1,20),(3,20),(4,20),(6,20),(7,20),(9,20),(10,20),(12,20),(13,20),(15,20),(16,20),(18,20),(19,20),(21,20),(22,20),(24,20),(25,20),(27,20),(1,21),(2,21),(3,21),(4,21),(5,21),(6,21),(7,21),(8,21),(9,21),(10,21),(11,21),(12,21),(13,21),(14,21),(15,21),(16,21),(17,21),(18,21),(19,21),(20,21),(21,21),(22,21),(23,21),(24,21),(25,21),(26,21),(27,21),(1,22),(2,22),(3,22),(7,22),(8,22),(9,22),(10,22),(11,22),(12,22),(16,22),(17,22),(18,22),(19,22),(20,22),(21,22),(25,22),(26,22),(27,22),(1,23),(3,23),(7,23),(9,23),(10,23),(12,23),(16,23),(18,23),(19,23),(21,23),(25,23),(27,23),(1,24),(2,24),(3,24),(7,24),(8,24),(9,24),(10,24),(11,24),(12,24),(16,24),(17,24),(18,24),(19,24),(20,24),(21,24),(25,24),(26,24),(27,24),(1,25),(2,25),(3,25),(4,25),(5,25),(6,25),(7,25),(8,25),(9,25),(10,25),(11,25),(12,25),(13,25),(14,25),(15,25),(16,25),(17,25),(18,25),(19,25),(20,25),(21,25),(22,25),(23,25),(24,25),(25,25),(26,25),(27,25),(1,26),(3,26),(4,26),(6,26),(7,26),(9,26),(10,26),(12,26),(13,26),(15,26),(16,26),(18,26),(19,26),(21,26),(22,26),(24,26),(25,26),(27,26),(1,27),(2,27),(3,27),(4,27),(5,27),(6,27),(7,27),(8,27),(9,27),(10,27),(11,27),(12,27),(13,27),(14,27),(15,27),(16,27),(17,27),(18,27),(19,27),(20,27),(21,27),(22,27),(23,27),(24,27),(25,27),(26,27),(27,27)]
Respuestas:
Mathematica
2928 BytesFindShortestTour
(16 Bytes) hace el truco pero entrega información extraña no solicitada (la longitud de la ruta y un retorno al punto de partida).da solo la respuesta (-1 byte gracias a @ user202729)
Para visualizar, use
Graphics@Line[g[[%]]]
, donde%
es la permutación que se encuentra arriba yg es la lista de puntos original.Aquí está la visualización de la solución para la esponja Menger:
Aquí hay una solución en 1000 puntos aleatorios:
La clave aquí es saber que la solución más corta para el problema del recorrido o del vendedor ambulante nunca producirá intersecciones cuando la distancia euclidiana se use como métrica. Uno de los pasos para localizar una solución y garantizar la óptima es eliminar tales intersecciones.
fuente
@*
Parece guardar un byte.JavaScript (ES6),
365341 bytesSin ningún elemento incorporado, resultó ser mucho más largo de lo que esperaba. Se gastan muchos bytes para detectar segmentos superpuestos colineales.
Toma la entrada como una matriz de
[x,y]
coordenadas. Devuelve una permutación de la entrada.Manifestación
Este fragmento registra la salida y dibuja la ruta correspondiente en un lienzo.
Mostrar fragmento de código
¿Cómo?
Aquí está la estructura de la función recursiva principal f () , dejando de lado el código de prueba de intersección por ahora:
A continuación se muestra el detalle de la prueba de intersección () . Esta página proporciona una explicación completa sobre el algoritmo utilizado.
Finalmente, aquí está la definición de la función auxiliar o () :
fuente
APL (Dyalog Classic) ,
4238 bytesPruébalo en línea!
La entrada es una lista de pares de coordenadas. La salida es una permutación basada en 0.
⍵
es la lista de puntos: el argumento para{ }
⍵[⊃⍋↑⍵]
es el punto más bajo más a la izquierda⍵-
traduce todos los puntos para que el extremo inferior izquierdo esté en el origen del sistema de coordenadas0j1
la unidad imaginaria i = sqrt (-1)0j1⊥¨
decodifica las coordenadas como si fueran dígitos en un sistema de números base-i, es decir, convierte (x, y) en un número complejo ix + yz←
asignar az
12○
calcula los argumentos de los números complejos, también conocidos como ángulos theta o función circular APL 12(⍪,(|z)ׯ1*⊢=⌈/)
es un tren que calcula una máscara booleana de donde los ángulos están al máximo (⊢=⌈/
), convierte el 0 1 en la máscara en 1 ¯1 al elevar ¯1 a la potencia correspondiente (¯1*
), se multiplica por las magnitudes de los números complejos|z
, y concatena eso a la derecha (,
) de una matriz alta y delgada de 1 columna (⍪
) de los ángulos.⍋
grado: devuelve la permutación que ordenaría las filas de la matriz lexicográficamente en orden ascendentefuente