Construye un árbol divisor estéticamente agradable

43

Un árbol divisor estéticamente agradable es un árbol de divisores de entrada nque, 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 my 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 720para que los subárboles 24y 30estén correctamente espaciados. Además, tenga en cuenta que 24y 30tiene dos niveles de ramas porque 4y 6tiene nodos hijos que necesitan un espaciado correcto y los nodos hijos de 30deben 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, donde nes 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
Sherlock9
fuente
Gracias por este reto. Ahora puedo visualizar estas cosas sin dibujarlas cada vez: D
Conor O'Brien
¿El árbol debe parecerse a los ejemplos o puedo usar la función incorporada de Mathematica? Parece que este , pero con la factorización.
JungHwan Min
@JHM Sabía que debería haber mantenido la etiqueta de salida gráfica . Sí, puede usar eso incorporado. Editaré el desafío.
Sherlock9

Respuestas:

29

Python 2 , 711 651 575 559 554 547 539 540 530 522 bytes

Despué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 golf isdigit()aún más y reemplazando "" con E. -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ómo Ase define, cambiando cómo Tse define y agregando W, 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 contraparte , eliminandoQen conjunto, y editando cómo se devuelve el resultado. -10 bytes de uso en A<10lugar de L(S(A))<2para Ay B. -8 bytes de cambiar el valor predeterminado Ha [0]ya que el código evita el problema de los argumentos predeterminados mutables al nunca mutar H, cambiar cómo qse define mediante el uso en (B>9)lugar de 1-(B<10), eliminar por pcompleto y crear Fcomo un reemplazo para p+q-M.

Corrección de errores: la hipótesis era incorrecta, contraejemplo 11**9 = 2357947691. +1 byte

G=range;L=len;E=" "
def t(n,H=[0]):
 A=max(z*(n%z<1)for z in G(1,int(n**.5)+1));B=n/A;Z=str(n);M=L(Z)
 if A<2:return[Z]
 T=max([i for i in G(L(w))if"/"not in w[i]]for w in(t(A),t(B)));V=H[1:]or[T[k+1]-T[k]-1for k in G(L(T)-1)];x=t(A,V);y=t(B,V);P=x[0].rindex(str(A)[-1])+(A<10);q=y[0].index(str(B)[0])+(B>9);F=L(x[0])-P+q-M;h=H[0]or(F+M%2+2)/2or 1;return[E*(P+J)+(J<h and"/"+E*(2*h+M-2*J-2)+"\\"or Z)+E*(L(y[0])-q+J)for J in G(h,-1,-1)]+[(E*(2*h-F)).join(I<L(w)and w[I]or E*L(w[0])for w in(x,y))for I in G(max(L(x),L(y)))]

Explicación

Toda la función se puede reducir a unos cuatro pasos:

  1. Determine el par divisor más grande de n, Ay B.
  2. Haga los subárboles de Ay B, redibujando según sea necesario.
  3. Determine la cantidad de espacios que deben ir entre los subárboles.
  4. Dibuja y devuelve el nuevo árbol divisor.

Recorreré cada paso en orden.

Paso 1. Este es el paso más fácil, francamente. Verifica zla divisibilidad en cada número entre 1 y la raíz cuadrada ny toma el más grande zy n//zque coincida. Regrese solo str(n)si nes primo (ya sea A==1o B==n)

Paso 2. Dibujar los subárboles de Ay By 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 en 11**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, sy M. pes el número de caracteres desde el final de la rama izquierda /hasta el extremo derecho del subárbol izquierdo. qes el número de caracteres desde el extremo izquierdo del subárbol derecho hasta el final de la rama derecha /. hes el número de ramas entre la raíz y los subárboles. Py Qson sólo las inversas de pe qy son útiles para la colocación de los espacios alrededor de /\las ramas hasta la raíz n. ses el número de espacios que se suman entre los dos subárboles. Mes más simple es la longitud de n. Poner gráficamente:

            M
           ---
           720           
 |        /   \          
 |       /     \         
h|      /       \        
 |     /         \       
 |    /           \      
   P    p    s   q   Q   
------______---____------
     24           30     
    /  \         /  \    
   /    \       /    \   
  4      6     5      6  
 / \    / \          / \ 
2   2  2   3        2   3

La fórmula para determinar pes 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 para As de un solo dígito .

La fórmula para determinar qes 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 para Bs de un solo dígito (combinado en una corrección para s de varios dígitos B).

La fórmula para determinar hes la siguiente: h = H[0] or (p+q+M%2+2-M)//2 or 1. O tomamos un valor predefinido, lo Hque 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 ses la siguiente: s = 2*h+M-p-q. Restamos py qdel número de espacios entre las ramas de la raíz en su punto más ancho 2*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:

def tree(n, H=[0]):
    A = max(z for z in range(1, int(n**.5)+1) if n%z<1)
    B = n/A
    Z = str(n)
    M = len(Z)
    if A < 2:
        return [Z]

    # redraw the tree so that all of the numbers are on the same rows
    x = tree(A)
    y = tree(B)
    for W in [x, y]:
        T = [i for i in range(len(W)) if "/" not in W[i]]
    V = H[1:] or [T[k+1]-T[k]-1 for k in range(len(T)-1)]
    x = tree(A, V)
    y = tree(B, V)

    # get the height of the root from the two trees
    P = x[0].rindex(str(A)[-1]) + (A < 10)
    p = len(x[0]) - P
    q = y[0].index(str(B)[0]) + (B > 9)
    Q = len(y[0]) - q
    h = hs[0] or (p+q+M%2+2-M)/2 or 1

    # and now to put the root down
    R = []
    s = 2*h+M-p-q
    for I in range(max(len(x),len(y))):
        c = I<len(x) and x[I] or " "*len(x[0])
        d = I<len(y) and y[I] or " "*len(y[0])
        R += c + " "*s + d,
    for J in range(h, -1, -1):
        if J<h:
            C = "/" + " "*(2*h+M-2*J-2) + "\\"
        else:
            C = Z
        R += [" "*(P+J) + C + " "*(Q+J)]
    return R
Sherlock9
fuente
¿Podría ser tu isdigitcheque '/'<x[i].strip()[0]<':'?
FlipTack
14

Mathematica, 96 86 81 79 78 bytes

Gracias @MartinEnder por 2 bytes.

TreeForm[If[PrimeQ@#,#,#0/@(#2[#,#2/#]&[Max@Nearest[Divisors@#,#^.5],#])]&@#]&

La salida se ve así:

ingrese la descripción de la imagen aquí

Explicación

Max@Nearest[Divisors@#,#^.5]

Genere la lista de divisores de la entrada. Encuentre el elemento más cercano a la raíz cuadrada de la entrada. ( Maxes para aplanar la salida)

#2[#,#2/#]&

Encuentre el otro divisor dividiendo la entrada por el divisor que se encuentra arriba, aplique la entrada como la cabeza del resultado.

#0/@

Repite el proceso.

If[PrimeQ@#,#, ... ]

Si la entrada es primo, no hagas nada.

TreeForm

Formatear la salida.

Editar: una versión más estética (258 bytes)

TreeForm[#/.{a_,_,_}:>a,VertexRenderingFunction->(#2~Text~#&),VertexCoordinateRules->Cases[#,{_,_},Infinity,Heads->True]]&@(If[PrimeQ@#,{##},{##}@@#0@@@({{#,#3-#4{1,√3}/2,#4/2},{#2/#,#3-#4{-1,√3}/2,#4/2}}&[Max@Nearest[Divisors@#,√#],##])]&[#,{0,0},1])&

La salida se ve así:

ingrese la descripción de la imagen aquí

JungHwan Min
fuente
3
Sqrt@#-> #^.5(por supuesto, entonces no puedes usar la notación infija Nearestpero sí puedes usar Max@).
Martin Ender
55
Sigue las reglas, pero ese árbol está lejos de ser estéticamente agradable xD
Beta Decay
2
La belleza está en el ojo del espectador :)
Nelson
1
No estoy seguro de que esto sea válido. A diferencia de los ejemplos, los nodos en cada fila no están espaciados uniformemente. Además, las líneas no se conectan al dígito correcto.
Mego
1
@Mego Bueno, OP dijo que era válido.
R. Kap
3

Carbón , 302 bytes

≔⟦⟦N⁰θ⁰¦⁰⟧⟧θFθ«≔§ι⁰ζ≔⌈E…·²Xζ·⁵∧¬﹪ζκκη¿η«F⟦η÷ζη⟧«≔⟦κ⊕§ι¹Iκ⁰¦⁰⟧κ⊞ικ⊞θκ»⊞υι»»≔…⁰⌈Eθ§ι¹ηF⮌竧≔ηι⊕⌈⟦⁰⌈Eυ∧⁼§κ¹ι÷Σ⟦¹§§κ⁵¦⁴‹⁹§§κ⁵¦⁰§§κ⁶¦³‹⁹§§κ⁶¦⁰±L§κ²⟧²⟧FυF²§≔κ⁺³λ⁺⁺§ηι∨⊖L§§κ⁺⁵벦¹§§κ⁺⁵λ⁺³λ»Fυ«§≔§ι⁵¦³⁻⁻§ι³§η§ι¹∨⊖L§§ι⁵¦²¦¹§≔§ι⁶¦³⁻⁺⁺§ι³L§ι²§η§ι¹‹⁹§§ι⁶¦⁰»F⊕Lη«Fθ«F⁼§κ¹ι«←⸿M§κ³→F‹⁵Lκ«↙P↙§ηι↗»§κ²↓F‹⁵LκP↘§ηι»»M⊕§ηι↓

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:

u = []; // predefined variable, used as list of branches
q = [[+s, 0, s, 0, 0]]; // list of nodes starts with the root.
for (i of q) { // iterate nodes, includes new nodes
    z = i[0]; // get node value
    h = Math.max(...[...Array(Math.floor(z ** 0.5) + 1).keys()].slice(2).filter(
        k => z % k < 1)); // find largest factor not above square root
    if (h) {
        for (k of [h, z / h]) {
            k = [k, i[1] + 1, `${k}`, 0, 0]; // create child node
            i.push(k); // add each child to parent (indices 5 and 6)
            q.push(k); // and to master nodelist
        }
        u.push(i);
    }
}
h = new Array(Math.max(...q.map(i => i[1]))); // list of branch heights
for (i = h.length; i --> 0; ) {
    // find branch height needed to space immediate children apart at this depth
    h[i] = 1 + Math.max(...u.map(k => k[1] == j && // filter on depth
        1 + k[5][3] + (k[5][0] > 9) + k[6][2] + (k[6][0] > 9) - k[2].length
        >> 1)); // current overlap, halved, rounded up
    // calculate the new margins on all the nodes
    for (k of u) {
        k[3] = h[i] + (k[5][2].length - 1 || 1) + k[5][3]; // left
        k[4] = h[i] + (k[6][2].length - 1 || 1) + k[6][4]; // right
    }
}
// calculate the absolute left margin of all the nodes under the root
for (i of u) {
    i[5][3] = i[3] - h[i[1]] - (i[5][2].length - 1 || 1);
    i[6][3] = i[3] + i[2].length + h[i[1]] - (i[6][0] > 9);
}
// print the nodes (sorry, no transliteration available)
Neil
fuente