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, m
a 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, 720
aby poddrzewa 24
i 30
poddrzewa były prawidłowo rozmieszczone. Należy również pamiętać, że 24
i 30
mieć dwa poziomy oddziałów bo 4
i 6
mieć dzieci węzły, które wymagają prawidłowego odstępu i dzieci węzły 30
muszą 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
, gdzien
dodatnia 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
źródło
Odpowiedzi:
Python 2 ,
711651575559554547539540530522 bajtówPo 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 „” naE
. -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 sposobuA
definiowania,zmiany sposobu, usuwającT
definiowania i dodawaniaW
, 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 odpowiednikQ
łącznie i edycja sposobu zwracania wyniku. -10 bajtów z użyciaA<10
zamiastL(S(A))<2
dlaA
iB
. -8 bajtów od zmiany wartości domyślnejH
na,[0]
ponieważ kod pozwala uniknąć problemu zmiennych argumentów domyślnych, nigdy nie mutującH
, zmieniając sposóbq
definiowania poprzez użycie(B>9)
zamiast1-(B<10)
,p
całkowite usunięcie i tworzenieF
jako zamiennikp+q-M
.Poprawki błędów: Hipoteza była błędna, w kontrprzykładzie
11**9 = 2357947691
. +1 bajtWyjaśnienie
Całą funkcję można sprowadzić do około czterech kroków:
n
,A
iB
.A
iB
przerysowuj w razie potrzeby.Przejdę kolejno przez każdy krok.
Krok 1. Jest to najłatwiejszy krok, szczerze mówiąc. Sprawdź każdą liczbę
z
od 1 do pierwiastka kwadratowego pod kątem podzielności nan
i złap największąz
in//z
pasującą. Zwróć tylkostr(n)
jeślin
jest liczbą pierwszą (alboA==1
alboB==n
)Krok 2. Narysuj poddrzew
A
iB
i 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 w11**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
,s
iM
.p
to liczba znaków od końca lewej gałęzi/
do prawego końca lewego poddrzewa.q
to liczba znaków od lewego końca prawego poddrzewa do końca prawej gałęzi/
.h
to liczba rozgałęzień między korzeniem a poddrzewami.P
iQ
to tylko odwrotnościp
aq
i są przydatne do umieszczania przestrzenie wokół/\
gałęzi aż do korzenian
.s
to liczba spacji dodawanych między dwoma poddrzewami.M
jest najprostszy; to długośćn
. Ułóż graficznie:Wzór na określenie
p
jest 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 jednocyfroweA
s.Wzór na określenie
q
jest 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 jednocyfroweB
s (połączone w jedną poprawkę na wielocyfroweB
s).Wzór do określania
h
jest następująca:h = H[0] or (p+q+M%2+2-M)//2 or 1
. Albo pobieramy z predefiniowanego,H
co 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
s
jest następująca:s = 2*h+M-p-q
. Odejmujemyp
iq
od liczby spacji między gałęziami korzenia w najszerszym miejscu2*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:
źródło
isdigit
być twój czek'/'<x[i].strip()[0]<':'
?Mathematica,
9686817978 bajtówDzięki @MartinEnder za 2 bajty.
Dane wyjściowe wyglądają następująco:
Wyjaśnienie
Wygeneruj listę dzielników danych wejściowych. Znajdź element najbliższy pierwiastkowi kwadratowemu z danych wejściowych. (
Max
służy do spłaszczenia wyjścia)Znajdź inny dzielnik, dzieląc dane wejściowe przez dzielnik znaleziony powyżej, zastosuj dane wejściowe jako wynik wyniku.
Powtórz proces.
Jeśli dane wejściowe są najważniejsze, nie rób nic.
Sformatuj wyjście.
Edycja: Bardziej estetyczna wersja (258 bajtów)
Dane wyjściowe wyglądają następująco:
źródło
Sqrt@#
->#^.5
(oczywiście wtedy nie można używać notacji infix,Nearest
ale można użyćMax@
).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:
źródło