Fondo
Un triángulo pitagórico es un triángulo rectángulo donde la longitud de cada lado es un número entero (es decir, las longitudes de los lados forman un triple pitagórico ):
Usando los lados de este triángulo, podemos unir dos triángulos pitagóricos no congruentes más de la siguiente manera:
Podemos continuar con este patrón como mejor nos parezca, siempre y cuando no se superpongan dos triángulos y los lados de conexión tengan la misma longitud:
La pregunta es, ¿cuántos triángulos pitagóricos no congruentes podemos caber en un espacio dado?
La entrada
Recibirá dos enteros como entrada W
y H
, a través de argumentos de función, STDIN, cadenas o lo que desee. Los enteros se pueden recibir como decimal, hexadecimal, binario, unario (buena suerte, retina ) o cualquier otra base de enteros. Puedes suponer eso max(W, H) <= 2^15 - 1
.
La salida
Su programa o función debe calcular una lista de triángulos pitagóricos no congruentes conectados no superpuestos y generar una lista de conjuntos de tres coordenadas cada uno, donde las coordenadas en un conjunto forman uno de los triángulos pitagóricos cuando están conectadas por líneas. Las coordenadas deben ser números reales en nuestro espacio ( x
deben estar en el intervalo [0, W]
y y
deben estar en el intervalo [0, H]
), y la distancia debe ser precisa a la precisión de la máquina. El orden de los triángulos y el formato exacto de cada coordenada no es importante.
Debe ser posible "caminar" de un triángulo a otro, solo cruzando los límites conectados.
Usando el diagrama anterior como ejemplo, dejar que sea nuestra entrada W = 60
, H = 60
.
Nuestra salida podría ser la siguiente lista de coordenadas:
(0, 15), (0, 21), (8, 15)
(0, 21), (14.4, 40.2), (8, 15)
(0, 15), (8, 0), (8, 15)
(8, 0), (8, 15), (28, 15)
(8, 15), (28, 15), (28, 36)
(28, 15), (28, 36), (56, 36)
Ahora, 6 triángulos ciertamente no es lo mejor que podemos hacer dado nuestro espacio. ¿Puedes hacerlo mejor?
Reglas y puntuación
Su puntaje para este desafío es la cantidad de triángulos que genera su programa dada la entrada de
W = 1000, H = 1000
. Me reservo el derecho de cambiar esta entrada si sospecho que alguien está codificando este caso.No puede usar los componentes integrados que calculan triples pitagóricos, y no puede codificar una lista de más de 2 triples pitagóricos (si codifica su programa para comenzar siempre con un triángulo (3, 4, 5), o alguna circunstancia de inicio similar, que está bien).
Puede escribir su presentación en cualquier idioma. Se recomienda la legibilidad y los comentarios.
Puede encontrar una lista de triples pitagóricos aquí .
Las lagunas estándar no están permitidas.
fuente
Respuestas:
Pitón 3, 109
Este fue ciertamente un desafío engañosamente difícil. Muchas veces escribiendo el código me encontré cuestionando mis habilidades básicas de geometría. Dicho esto, estoy bastante contento con el resultado. No me esforcé en encontrar un algoritmo complejo para colocar los triángulos, y en cambio mi código simplemente se equivoca al colocar siempre lo más pequeño que puede encontrar. ¡Espero poder mejorar esto más adelante, o mi respuesta despreciará a otros para encontrar un mejor algoritmo! En general, es un problema muy divertido y produce algunas imágenes interesantes.
Aquí está el código:
Aquí hay un gráfico de la salida para
W = 1000
yH = 1000
con 109 triángulos:Aquí está
W = 10000
yH = 10000
con 724 triángulos:Llama a la
matplotlib_graph()
función luegobuild_all_triangles()
para graficar los triángulos.Creo que el código se ejecuta razonablemente rápido: at
W = 1000
yH = 1000
toma 0.66 segundos, y atW = 10000
yH = 10000
toma 45 segundos usando mi computadora portátil.fuente
C ++, 146 triángulos (parte 1/2)
Resultado como imagen
Descripción del algoritmo
Esto utiliza una búsqueda amplia del espacio de solución. En cada paso, comienza con todas las configuraciones únicas de
k
triángulos que caben en el cuadro, y construye todas las configuraciones únicas dek + 1
triángulos enumerando todas las opciones de agregar un triángulo no utilizado a cualquiera de las configuraciones.El algoritmo está configurado básicamente para encontrar el máximo absoluto con un BFS exhaustivo. Y lo hace con éxito para tamaños más pequeños. Por ejemplo, para una caja de 50x50, encuentra el máximo en aproximadamente 1 minuto. Pero para 1000x1000, el espacio de la solución es demasiado grande. Para permitir que termine, recorto la lista de soluciones después de cada paso. El número de soluciones que se mantiene viene dado por un argumento de línea de comando. Para la solución anterior, se usó un valor de 50. Esto dio como resultado un tiempo de ejecución de aproximadamente 10 minutos.
El esquema de los pasos principales se ve así:
Un aspecto crítico en todo el esquema es que las configuraciones generalmente se generarán varias veces, y solo estamos interesados en configuraciones únicas. Por lo tanto, necesitamos una clave única que defina una solución, que debe ser independiente del orden de los triángulos utilizados al generar la solución. Por ejemplo, el uso de coordenadas para la clave no funcionaría en absoluto, ya que pueden ser completamente diferentes si llegamos a la misma solución en múltiples órdenes. Lo que usé es el conjunto de índices de triángulos en la lista global, más un conjunto de objetos "conectores" que definen cómo se conectan los triángulos. Por lo tanto, la clave solo codifica la topología, independientemente del orden de construcción y la posición en el espacio 2D.
Si bien es más un aspecto de implementación, otra parte que no es del todo trivial es decidir si y cómo todo encaja en el cuadro dado. Si realmente quiere empujar los límites, obviamente es necesario permitir que la rotación encaje dentro de la caja.
Intentaré agregar algunos comentarios al código en la parte 2 más adelante, en caso de que alguien quiera profundizar en los detalles de cómo funciona todo esto.
Resultado en formato de texto oficial
Código
Vea la parte 2 para el código. Esto se dividió en 2 partes para evitar los límites de tamaño de las publicaciones.
El código también está disponible en PasteBin .
fuente
C ++, 146 triángulos (parte 2/2)
Continúa de la parte 1. Esto se dividió en 2 partes para evitar los límites de tamaño de las publicaciones.
Código
Comentarios para agregar.
fuente