Un árbol divisor estéticamente agradable es un árbol de divisores de entrada n
que, para cualquier número compuesto m
, tiene dos nodos hijos que son el par de divisores más cercanos a la raíz cuadrada de m
. El nodo izquierdo debería ser el divisor más pequeño de m
y el nodo derecho debería ser el divisor más grande de m
. Un número primo en el árbol no debe tener nodos secundarios. Su árbol puede estar en forma de arte de texto o una imagen. Las reglas para la salida de arte de texto son las siguientes.
Reglas de espaciado
Para espaciar los nodos en el árbol, tenemos las siguientes reglas:
- Los nodos a una profundidad dada desde la raíz deben estar todos en la misma línea de texto en la salida.
/ \ NOT / \ / \ / 3 2 3 2
- Para los nodos izquierdos, la rama entrante debe estar en la esquina superior derecha si el nodo es un número de un solo dígito, de lo contrario, justo arriba del último dígito. Ejemplo:
/ Y / 3 720
- Para los nodos derechos, la rama entrante debe estar en la esquina superior izquierda si el nodo es un número de un solo dígito, de lo contrario, justo arriba del primer dígito. Ejemplo:
\ Y \ 7 243
- Para las ramas izquierdas salientes, la rama debe comenzar un espacio a la izquierda del número. Ejemplo:
275 / / 11
- Para las ramas derechas salientes, la rama debe comenzar un espacio a la derecha del número. Ejemplo:
275 \ 25
- Cualquiera de los dos nodos en el mismo nivel del árbol debe tener un mínimo de dos espacios entre ellos. Al mismo tiempo, cualquiera de los dos subárboles en el mismo nivel del árbol debe tener el menor espacio posible entre ellos.
Este árbol no funciona porque los ** subárboles ** están demasiado cerca. 504 / \ / \ / \ / \ 21) 24 / \. / \ / \. / \ 3 7. 4 6 . / \ / \ .2 2 2 3 Si bien este árbol tiene suficiente espacio entre sus ramas. 504 / \ / \ / \ / \ / \ 21 ... 24 / \ ... / \ / \ ... / \ 3 7 ... 4 6 ... / \ / \ ... 2 2 2 3
- Si dos subárboles están demasiado juntos en un árbol, se pueden separar agregando otra fila de ramas
/\
al árbol sobre los padres.
441 / \ La última fila aún no se ha completado y ya nos hemos quedado sin espacio. 21 21 / \ / \ Agrega otra fila de ramas 441 / \ Casi, pero el 7 y el 3 están demasiado juntos. / \ Una fila más debería hacerlo. 21 21 / \ / \ 3 7 3 7 Agrega otra fila de ramas 441 / \ Y hemos terminado. / \ / \ 21 21 / \ / \ 3 7 3 7
Ejemplos
Como ejemplo completo, el árbol divisor de 24 se verá así:
24
/ \
/ \
4 6
/ \ / \
2 2 2 3
4 y 6 son el par de divisores más cercanos a la raíz cuadrada de 24. 4 está a la izquierda, porque es más pequeño. En la siguiente línea, el número 2 a la izquierda del 3, porque es más pequeño.
El árbol divisor para 63 debería verse así:
63 and NOT like this 63
/ \ / \
7 9 3 21
/ \ / \
3 3 7 3
En el árbol incorrecto, 3 y 21 no son el par de divisores más cercanos a la raíz cuadrada de 63, y 3 y 7 no están ordenados correctamente. Sin embargo, la colocación de la rama en el 21 es correcta.
Para 42, deberías tener:
42 and NOT 42
/ \ / \
6 7 21 2
/ \ / \
2 3 3 7
Echemos un vistazo a 720. Tenga en cuenta que necesitamos cinco niveles de ramas 720
para que los subárboles 24
y 30
estén correctamente espaciados. Además, tenga en cuenta que 24
y 30
tiene dos niveles de ramas porque 4
y 6
tiene nodos hijos que necesitan un espaciado correcto y los nodos hijos de 30
deben estar en el mismo nivel que los nodos hijos de 24
.
720
/ \
/ \
/ \
/ \
/ \
24 30
/ \ / \
/ \ / \
4 6 5 6
/ \ / \ / \
2 2 2 3 2 3
El reto
- Su tarea es construir un árbol divisor estéticamente agradable correctamente espaciado para la entrada
n
, donden
es un entero positivo mayor que 1. - Su salida puede contener espacios iniciales y finales y nuevas líneas iniciales y finales, pero por lo demás debe cumplir con las reglas de espacio proporcionadas anteriormente.
- Su salida puede ser: texto, una imagen (otros formatos para agregar, si es necesario).
- Para las imágenes, asegúrese de que los nodos de su árbol estén bien espaciados y que los nodos a la misma altura del árbol estén a la misma altura en la imagen.
- Este es el código de golf. El menor número de bytes (o equivalente) gana.
Gracias a Stewie Griffin por pensar en esta idea, y muchas gracias a Peter Taylor, Martin Ender, Mego y Eᴀsᴛᴇʀʟʏ Iʀᴋ por su ayuda en la reescritura de la especificación. Como de costumbre, cualquier sugerencia o corrección es muy apreciada. ¡Buena suerte y buen golf!
Más casos de prueba:
2
4
/ \
2 2
20
/ \
4 5
/ \
2 2
323
/ \
17 19
362880
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
576 630
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
24 24 21 30
/ \ / \ / \ / \
/ \ / \ / \ / \
4 6 4 6 3 7 5 6
/ \ / \ / \ / \ / \
2 2 2 3 2 2 2 3 2 3
1286250
/ \
/ \
/ \
/ \
/ \
1050 1225
/ \ / \
/ \ / \
/ \ / \
30 35 35 35
/ \ / \ / \ / \
5 6 5 7 5 7 5 7
/ \
2 3
fuente
Respuestas:
Python 2 ,
711651575559554547539540530522 bytesDespués de cuatro meses de intentar escribir esta respuesta, tropezar con una pared, dejarla durante una semana, enjuagar, repetir, finalmente he terminado una respuesta de arte ASCII adecuada para este desafío. Todo lo que queda es el golf, por lo que las sugerencias de golf son bienvenidas. Pruébalo en línea!
Golfs: -60 bytes para renombrar algunas funciones de uso frecuente y cambiar la forma en que se devuelve el resultado. -73 bytes de cambiar cómo se verifican las alturas de los subárboles, cómo se calculan las variables de espaciado y cómo se devuelve el resultado. -3 bytes del
isdigit()
reemplazo de FlipTack . -16 bytes jugando al golfisdigit()
aún más y reemplazando "" conE
. -5 bytes de mejoras menores y cambio de Python 3 a Python 2. -7 bytes de modificar cómo se devuelve el resultado. -8 bytes desde un pequeño cambio en cómoA
se define,cambiando cómo, eliminandoT
se define y agregandoW
, usando la hipótesis de que cualquier subárbol con al menos una rama más larga que su contraparte, es necesariamente más largo en general que su contraparteQ
en conjunto, y editando cómo se devuelve el resultado. -10 bytes de uso enA<10
lugar deL(S(A))<2
paraA
yB
. -8 bytes de cambiar el valor predeterminadoH
a[0]
ya que el código evita el problema de los argumentos predeterminados mutables al nunca mutarH
, cambiar cómoq
se define mediante el uso en(B>9)
lugar de1-(B<10)
, eliminar porp
completo y crearF
como un reemplazo parap+q-M
.Corrección de errores: la hipótesis era incorrecta, contraejemplo
11**9 = 2357947691
. +1 byteExplicación
Toda la función se puede reducir a unos cuatro pasos:
n
,A
yB
.A
yB
, redibujando según sea necesario.Recorreré cada paso en orden.
Paso 1. Este es el paso más fácil, francamente. Verifica
z
la divisibilidad en cada número entre 1 y la raíz cuadradan
y toma el más grandez
yn//z
que coincida. Regrese solostr(n)
sin
es primo (ya seaA==1
oB==n
)Paso 2. Dibujar los subárboles de
A
yB
y obtener el número de/\
ramas entre los nodos en los subárboles. Para hacer esto, obtenemos los índices de cada paso que tiene dígitos, obtenemos las primeras diferencias de los índices y restamos 1 nuevamente. Una vez que tenemos las alturas, las comparamos para obtener la más grande y redibujamos los subárboles con las nuevas alturas.Tengo una sospecha furtiva de que el subárbol que es más alto en general siempre tiene ramas tan largas o iguales a las ramas en el subárbol más corto, y puedo usar eso para desarrollar el código, pero aún no tengo pruebas de esto.Contraejemplo en11**9 = 2357947691
.Paso 3. Este paso es lo que tomó meses para escribir. El paso 2 tomó unos días para escribir y depurar, pero encontrar las fórmulas correctas para el espaciado tomó años. Veré si puedo condensar lo que descubrí en unos pocos párrafos. Tenga en cuenta que parte del código de esta explicación se ha eliminado del código real.
En primer lugar,
p
,q
,h
,P
,Q
,s
yM
.p
es el número de caracteres desde el final de la rama izquierda/
hasta el extremo derecho del subárbol izquierdo.q
es el número de caracteres desde el extremo izquierdo del subárbol derecho hasta el final de la rama derecha/
.h
es el número de ramas entre la raíz y los subárboles.P
yQ
son sólo las inversas dep
eq
y son útiles para la colocación de los espacios alrededor de/\
las ramas hasta la raízn
.s
es el número de espacios que se suman entre los dos subárboles.M
es más simple es la longitud den
. Poner gráficamente:La fórmula para determinar
p
es esta:p = len(x[0]) - x[0].rindex(str(A)[-1]) - (A<10)
la longitud, menos el índice cero del último carácter en A, menos una corrección paraA
s de un solo dígito .La fórmula para determinar
q
es esta:q = y[0].index(str(B)[0]) + (B>9)
el índice del primer carácter en B, más una corrección para indexación cero, menos una corrección paraB
s de un solo dígito (combinado en una corrección para s de varios dígitosB
).La fórmula para determinar
h
es la siguiente:h = H[0] or (p+q+M%2+2-M)//2 or 1
. O tomamos un valor predefinido, loH
que significa que estamos redibujando el árbol, usamos(from_the_left + from_the_right + parity_space + 2 - len(root)) // 2)
o usamos el número mínimo de niveles de ramas, 1.La fórmula para determinar
s
es la siguiente:s = 2*h+M-p-q
. Restamosp
yq
del número de espacios entre las ramas de la raíz en su punto más ancho2*h + M
.Paso 4. Y finalmente lo juntamos todo. Primero hacemos la raíz,
[" "*(P+h)+Z+" "*(Q+h)]
y luego ponemos en las ramas hasta las sub-estructuras,[" "*(P+J)+"/"+" "*(2*h+M-2*J-2)+"\\"+" "*(Q+J)for J in G(h)][::-1]
y, finalmente, nos ponemos en nuestros subárboles adecuadamente espaciados,[(" "*(2*h+M-p-q)).join([(I<L(w)and w[I]or" "*L(w[0]))for w in(x,y)])for I in G(max(L(x),L(y)))]
.Et voilà! ¡Tenemos un árbol divisor estéticamente agradable!
No golfista:
fuente
isdigit
cheque'/'<x[i].strip()[0]<':'
?Mathematica,
9686817978 bytesGracias @MartinEnder por 2 bytes.
La salida se ve así:
Explicación
Genere la lista de divisores de la entrada. Encuentre el elemento más cercano a la raíz cuadrada de la entrada. (
Max
es para aplanar la salida)Encuentre el otro divisor dividiendo la entrada por el divisor que se encuentra arriba, aplique la entrada como la cabeza del resultado.
Repite el proceso.
Si la entrada es primo, no hagas nada.
Formatear la salida.
Editar: una versión más estética (258 bytes)
La salida se ve así:
fuente
Sqrt@#
->#^.5
(por supuesto, entonces no puedes usar la notación infijaNearest
pero sí puedes usarMax@
).Carbón , 302 bytes
Pruébalo en línea! El enlace es a la versión detallada del código. Como la versión detallada es muy detallada, es una transcripción de JavaScript del algoritmo principal:
fuente