Estetycznym dzielnik drzewo jest drzewem dzielników wejściowych n, że dla dowolnej liczby kompozytowego m, ma dwoje dzieci węzły, które są parą dzielników , które znajdują się najbliżej do pierwiastka kwadratowego z m. Lewy węzeł powinien być mniejszym dzielnikiem, ma prawy węzeł powinien być większym dzielnikiem m. Liczba pierwsza w drzewie nie powinna mieć węzłów potomnych. Twoje drzewo może być w formie grafiki tekstowej lub obrazu. Zasady wyświetlania grafiki tekstowej są następujące.

Zasady odstępów

Aby rozmieścić węzły w drzewie, obowiązują następujące zasady:

• Węzły na danej głębokości od katalogu głównego powinny znajdować się w tym samym wierszu tekstu na wyjściu.

  / \ NIE / \  
 / \ / 3
2 3 2

• W przypadku lewych węzłów gałąź przychodząca powinna znajdować się w prawym górnym rogu, jeśli węzeł jest liczbą jednocyfrową, w przeciwnym razie tuż powyżej ostatniej cyfry. Przykład:

 / I /
3 720

• W przypadku węzłów prawych gałąź przychodząca powinna znajdować się w lewym górnym rogu, jeśli węzeł jest liczbą jednocyfrową, w przeciwnym razie tuż powyżej pierwszej cyfry. Przykład:

\ I \
 7 243

• W przypadku wychodzących lewych gałęzi gałąź powinna zaczynać się o jedną spację po lewej stronie liczby. Przykład:

  275
 /
11

• W przypadku wychodzących prawych gałęzi gałąź powinna rozpoczynać się o jedną spację po prawej stronie liczby. Przykład:

275
   \
   25

• Każde dwa węzły na tym samym poziomie drzewa powinny mieć między sobą co najmniej dwa odstępy. W tym samym czasie dowolne dwa poddrzewa na tym samym poziomie drzewa powinny mieć możliwie jak najmniej odstępów.

To drzewo nie działa, ponieważ ** poddrzewa ** są zbyt blisko.

        504           
       / \          
      / \         
     / \        
    / \       
   21 24     
  / \. / \    
 / \. / \   
3 7. 4 6  
        . / \ / \
        .2 2 2 3

Podczas gdy drzewo ma wystarczająco dużo miejsca między gałęziami.

         504           
        / \          
       / \         
      / \        
     / \       
    / \      
   21 ... 24     
  / \ ... / \    
 / \ ... / \   
3 7 ... 4 6  
        ... / \ / \ 
        ... 2 2 2 3

• Jeśli jakieś dwa poddrzewa znajdują się zbyt blisko siebie na drzewie, można je rozdzielić, dodając kolejny rząd gałęzi /\do drzewa nad rodzicami.

   441                              
  / \ Ostatni wiersz nie jest jeszcze wypełniony i zabrakło nam już miejsca.
 21 21
/ \ / \

Dodaj kolejny rząd gałęzi

     441                              
    / \ Prawie, ale 7 i 3 są zbyt blisko siebie.
   / \ Powinien to zrobić jeszcze jeden wiersz.
  21 21
 / \ / \
3 7 3 7

Dodaj kolejny rząd gałęzi

      441
     / \ I gotowe.
    / \
   / \
  21 21
 / \ / \
3 7 3 7

Przykłady

Jako pełny przykład drzewo dzielnika 24 będzie wyglądało następująco:

     24
    /  \
   /    \
  4      6
 / \    / \
2   2  2   3

4 i 6 to para dzielników najbliższych pierwiastkowi kwadratowemu z 24. 4 znajduje się po lewej stronie, ponieważ jest mniejsza. W następnym wierszu liczba 2 po lewej stronie 3, ponieważ jest mniejsza.

Drzewo dzielnika dla 63 powinno wyglądać następująco:

  63        and NOT like this        63
 /  \                               /  \
7    9                             3   21
    / \                               /  \
   3   3                             7    3

W niewłaściwym drzewie 3 i 21 nie są parą dzielników najbliższych pierwiastkowi kwadratowemu 63, a 3 i 7 nie są odpowiednio posortowane. Jednak umieszczenie gałęzi na 21 jest prawidłowe.

Dla 42 powinieneś mieć:

    42      and NOT        42
   /  \                   /  \
  6    7                 21   2
 / \                    /  \
2   3                  3    7

Spójrzmy na 720. Zauważ, że potrzebujemy pięciu poziomów gałęzi, 720aby poddrzewa 24i 30poddrzewa były prawidłowo rozmieszczone. Należy również pamiętać, że 24i 30mieć dwa poziomy oddziałów bo 4i 6mieć dzieci węzły, które wymagają prawidłowego odstępu i dzieci węzły 30muszą być na tym samym poziomie jak dzieci węzłów 24.

           720
          /   \
         /     \
        /       \
       /         \
      /           \ 
     24           30
    /  \         /  \
   /    \       /    \
  4      6     5      6
 / \    / \          / \
2   2  2   3        2   3

Wyzwanie

• Twoim zadaniem jest zbudowanie odpowiednio rozmieszczonego, estetycznego drzewa dzielnika dla danych wejściowych n, gdzie ndodatnia liczba całkowita jest większa niż 1.
• Twój wynik może zawierać początkowe i końcowe spacje oraz wiodące i końcowe znaki nowej linii, ale w przeciwnym razie musi być zgodny z powyższymi regułami odstępów.
• Twoje dane wyjściowe mogą być: tekstem, obrazem (w razie potrzeby można dodać inne formaty).
• W przypadku obrazów upewnij się, że węzły drzewa są dobrze rozmieszczone, a węzły na tej samej wysokości w drzewie znajdują się na tej samej wysokości na obrazie.
• To jest kod golfowy. Najmniej wygranych bajtów (lub ich odpowiedników).

Podziękowania dla Stewiego Griffina za przemyślenie tego pomysłu i wielkie podziękowania dla Petera Taylora, Martina Endera, Mego i Eᴀsᴛᴇʀʟʏ Iʀᴋ za ich pomoc w przepisaniu specyfikacji. Jak zwykle wszelkie sugestie lub poprawki są mile widziane. Powodzenia i dobrej gry w golfa!

Więcej przypadków testowych:

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

Python 2 , 711 651 575 559 554 547 539 540 530 522 bajtów

Po czterech miesiącach próby napisania tej odpowiedzi, wbiegnięcia na ścianę, pozostawienia jej na kilka tygodni, spłukania, powtórzenia, w końcu skończyłem poprawną odpowiedź ASCII na to wyzwanie. Wszystko, co zostało, to gra w golfa, więc sugestie dotyczące gry w golfa są bardzo mile widziane. Wypróbuj online!

Golf: -60 bajtów od zmiany nazwy często używanych funkcji i zmiany sposobu zwracania wyniku. -73 bajty od zmiany sposobu sprawdzania wysokości poddrzewa, sposobu obliczania zmiennych odstępów i sposobu zwracania wyniku. -3 bajty z isdigit()wymiany FlipTacka . -16 bajtów gra w tę isdigit()grę jeszcze dalej i zamienia „” na E. -5 bajtów od drobnych usprawnień i zmiany z Pythona 3 na Python 2. -7 bajtów od modyfikacji sposobu zwracania wyniku. -8 bajtów od małej zmiany sposobu Adefiniowania, zmiany sposobu Tdefiniowania i dodawania W, używając hipotezy, że każde poddrzewo z co najmniej jedną dłuższą gałęzią niż jego odpowiednik, jest koniecznie dłuższe niż jego odpowiednik , usuwającQłącznie i edycja sposobu zwracania wyniku. -10 bajtów z użycia A<10zamiast L(S(A))<2dla Ai B. -8 bajtów od zmiany wartości domyślnej Hna, [0]ponieważ kod pozwala uniknąć problemu zmiennych argumentów domyślnych, nigdy nie mutując H, zmieniając sposób qdefiniowania poprzez użycie (B>9)zamiast 1-(B<10), pcałkowite usunięcie i tworzenie Fjako zamiennik p+q-M.

Poprawki błędów: Hipoteza była błędna, w kontrprzykładzie 11**9 = 2357947691. +1 bajt

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)))]

Wyjaśnienie

Całą funkcję można sprowadzić do około czterech kroków:

1. Określ największą parę dzielników n, Ai B.
2. Wykonaj poddrzewa Ai Bprzerysowuj w razie potrzeby.
3. Określ liczbę spacji, które powinny przechodzić między poddrzewami.
4. Narysuj i zwróć nowe drzewo dzielników.

Przejdę kolejno przez każdy krok.

Krok 1. Jest to najłatwiejszy krok, szczerze mówiąc. Sprawdź każdą liczbę zod 1 do pierwiastka kwadratowego pod kątem podzielności na ni złap największą zi n//zpasującą. Zwróć tylko str(n)jeśli njest liczbą pierwszą (albo A==1albo B==n)

Krok 2. Narysuj poddrzew Ai Bi uzyskać liczbę /\oddziałów między węzłami w poddrzew. Aby to zrobić, otrzymujemy wskaźniki każdego kroku zawierającego cyfry, otrzymujemy pierwsze różnice wskaźników i odejmujemy 1 ponownie. Kiedy mamy już wysokości, porównujemy je, aby uzyskać największą, i przerysowujemy poddrzewa z nowymi wysokościami.

Podejrzewam podejrzenie, że poddrzewo, które jest ogólnie wyższe, zawsze ma gałęzie tak długie lub równe gałęziom w krótszym poddrzewie i mogę tego użyć do gry w golfa, ale nie mam na to jeszcze dowodu. Kontrprzykład w 11**9 = 2357947691.

Krok 3. Napisanie tego zajęło miesiące. Krok 2 zajął kilka dni na napisanie i debugowanie, ale znalezienie odpowiednich formuł dla odstępów zajęło wieki. Zobaczę, czy uda mi się skondensować to, co doszedłem do kilku akapitów. Zwróć uwagę, że część kodu w tym objaśnieniu została oderwana od prawdziwego kodu.

Po pierwsze p, q, h, P, Q, si M. pto liczba znaków od końca lewej gałęzi /do prawego końca lewego poddrzewa. qto liczba znaków od lewego końca prawego poddrzewa do końca prawej gałęzi /. hto liczba rozgałęzień między korzeniem a poddrzewami. Pi Qto tylko odwrotności pa qi są przydatne do umieszczania przestrzenie wokół /\gałęzi aż do korzenia n. sto liczba spacji dodawanych między dwoma poddrzewami. Mjest najprostszy; to długość n. Ułóż graficznie:

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

Wzór na określenie pjest następujący: p = len(x[0]) - x[0].rindex(str(A)[-1]) - (A<10)długość pomniejszona o indeks zerowy ostatniego znaku w A pomniejszona o poprawkę na jednocyfrowe As.

Wzór na określenie qjest następujący: q = y[0].index(str(B)[0]) + (B>9)indeks pierwszego znaku w B, plus poprawka na indeksowanie zerowe, minus poprawka na jednocyfrowe Bs (połączone w jedną poprawkę na wielocyfrowe Bs).

Wzór do określania hjest następująca: h = H[0] or (p+q+M%2+2-M)//2 or 1. Albo pobieramy z predefiniowanego, Hco oznacza, że ​​przerysowujemy drzewo, używamy (from_the_left + from_the_right + parity_space + 2 - len(root)) // 2)lub używamy minimalnej liczby poziomów gałęzi, 1.

Wzór do określania sjest następująca: s = 2*h+M-p-q. Odejmujemy pi qod liczby spacji między gałęziami korzenia w najszerszym miejscu 2*h + M.

Krok 4. I w końcu zebraliśmy to wszystko. Najpierw musimy zrobić korzenia [" "*(P+h)+Z+" "*(Q+h)], a następnie kładziemy na gałęziach aż do poddrzew, [" "*(P+J)+"/"+" "*(2*h+M-2*J-2)+"\\"+" "*(Q+J)for J in G(h)][::-1]i wreszcie kładziemy w naszych prawidłowo rozstawionych poddrzew, [(" "*(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)))].

Gotowe! Mamy estetyczne drzewo dzielące!

Ungolfing:

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

Mathematica, 96 86 81 79 78 bajtów

Dzięki @MartinEnder za 2 bajty.

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

Dane wyjściowe wyglądają następująco:

Wyjaśnienie

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

Wygeneruj listę dzielników danych wejściowych. Znajdź element najbliższy pierwiastkowi kwadratowemu z danych wejściowych. ( Maxsłuży do spłaszczenia wyjścia)

#2[#,#2/#]&

Znajdź inny dzielnik, dzieląc dane wejściowe przez dzielnik znaleziony powyżej, zastosuj dane wejściowe jako wynik wyniku.

#0/@

Powtórz proces.

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

Jeśli dane wejściowe są najważniejsze, nie rób nic.

TreeForm

Sformatuj wyjście.

Edycja: Bardziej estetyczna wersja (258 bajtów)

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])&

Dane wyjściowe wyglądają następująco:

Węgiel drzewny , 302 bajty

≔⟦⟦Ｎ⁰θ⁰¦⁰⟧⟧θＦθ«≔§ι⁰ζ≔⌈Ｅ…·²Ｘζ·⁵∧¬﹪ζκκη¿η«Ｆ⟦η÷ζη⟧«≔⟦κ⊕§ι¹Ｉκ⁰¦⁰⟧κ⊞ικ⊞θκ»⊞υι»»≔…⁰⌈Ｅθ§ι¹ηＦ⮌竧≔ηι⊕⌈⟦⁰⌈Ｅυ∧⁼§κ¹ι÷Σ⟦¹§§κ⁵¦⁴‹⁹§§κ⁵¦⁰§§κ⁶¦³‹⁹§§κ⁶¦⁰±Ｌ§κ²⟧²⟧ＦυＦ²§≔κ⁺³λ⁺⁺§ηι∨⊖Ｌ§§κ⁺⁵벦¹§§κ⁺⁵λ⁺³λ»Ｆυ«§≔§ι⁵¦³⁻⁻§ι³§η§ι¹∨⊖Ｌ§§ι⁵¦²¦¹§≔§ι⁶¦³⁻⁺⁺§ι³Ｌ§ι²§η§ι¹‹⁹§§ι⁶¦⁰»Ｆ⊕Ｌη«Ｆθ«Ｆ⁼§κ¹ι«←⸿Ｍ§κ³→Ｆ‹⁵Ｌκ«↙Ｐ↙§ηι↗»§κ²↓Ｆ‹⁵ＬκＰ↘§ηι»»Ｍ⊕§ηι↓

Wypróbuj online! Link jest do pełnej wersji kodu. Ponieważ pełna wersja jest bardzo szczegółowa, jest on transliteracją JavaScript głównego algorytmu:

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)