Ein ästhetisch ansprechender Teilerbaum ist ein Baum von Eingabeteilern n
, der für jede zusammengesetzte Zahl m
zwei untergeordnete Knoten hat, die das Teilerpaar darstellen , das der Quadratwurzel von am nächsten liegt m
. Der linke Knoten sollte der kleinere Teiler sein m
und der rechte Knoten sollte der größere Teiler sein m
. Eine Primzahl im Baum sollte keine untergeordneten Knoten haben. Ihr Baum kann in Form von Textkunst oder einem Bild vorliegen. Die Regeln für die Ausgabe von Textkunst lauten wie folgt.
Abstandsregeln
Um die Knoten in der Baumstruktur auszuräumen, gelten die folgenden Regeln:
- Die Knoten in einer bestimmten Tiefe von der Wurzel sollten sich in der Ausgabe alle in derselben Textzeile befinden.
/ \ NOT / \ / \ / 3 2 3 2
- Bei linken Knoten sollte sich der eingehende Zweig oben rechts befinden, wenn der Knoten eine einstellige Zahl ist, ansonsten direkt über der letzten Ziffer. Beispiel:
/ UND / 3 720
- Bei rechten Knoten sollte sich der eingehende Zweig oben links befinden, wenn der Knoten eine einstellige Zahl ist, ansonsten direkt über der ersten Ziffer. Beispiel:
\ UND \ 7 243
- Bei ausgehenden linken Zweigen sollte der Zweig ein Leerzeichen links von der Nummer beginnen. Beispiel:
275 / 11
- Für ausgehende rechte Zweige sollte der Zweig ein Leerzeichen rechts von der Nummer beginnen. Beispiel:
275 \ 25
- Zwei beliebige Knoten auf derselben Ebene des Baums müssen mindestens zwei Leerzeichen voneinander entfernt sein. Gleichzeitig sollten zwei Teilbäume auf derselben Ebene des Baums so wenig Leerzeichen wie möglich voneinander entfernt sein.
Dieser Baum funktioniert nicht, weil die ** Teilbäume ** zu eng sind. 504 / \ / \ / \ / \ 21. 24 / \. / \ / \. / \ 3 7. 4 6 . / \ / \ .2 2 2 3 Während dieser Baum genug Platz zwischen seinen Zweigen hat. 504 / \ / \ / \ / \ / \ 21 ... 24 / \ ... / \ / \ ... / \ 3 7 ... 4 6 ... / \ / \ ... 2 2 2 3
- Wenn zwei Teilbäume in einem Baum zu nahe beieinander liegen, können Sie sie trennen, indem Sie
/\
dem Baum über den Eltern eine weitere Reihe von Zweigen hinzufügen .
441 / \ Letzte Zeile ist noch nicht ausgefüllt und wir haben bereits keinen Platz mehr. 21 21 / \ / \ Fügen Sie eine weitere Reihe von Zweigen hinzu 441 / \ Fast, aber die 7 und die 3 liegen zu nahe beieinander. / \ Eine weitere Zeile sollte es tun. 21 21 / \ / \ 3 7 3 7 Fügen Sie eine weitere Reihe von Zweigen hinzu 441 / \ Und wir sind fertig. / \ / \ 21 21 / \ / \ 3 7 3 7
Beispiele
Als vollständiges Beispiel sieht der Teilerbaum von 24 folgendermaßen aus:
24
/ \
/ \
4 6
/ \ / \
2 2 2 3
4 und 6 sind das Teilerpaar, das der Quadratwurzel von 24 am nächsten liegt. 4 befindet sich links, da es kleiner ist. In der nächsten Zeile die Zahl 2 links von 3, weil sie kleiner ist.
Der Teilerbaum für 63 sollte wie folgt aussehen:
63 and NOT like this 63
/ \ / \
7 9 3 21
/ \ / \
3 3 7 3
In der falschen Baumstruktur sind 3 und 21 nicht das der Quadratwurzel von 63 am nächsten liegende Teilerpaar, und 3 und 7 sind nicht richtig sortiert. Die Abzweigplatzierung auf der 21 ist jedoch korrekt.
Für 42 sollten Sie haben:
42 and NOT 42
/ \ / \
6 7 21 2
/ \ / \
2 3 3 7
Werfen wir einen Blick auf 720. Beachten Sie, dass wir fünf Verzweigungsebenen benötigen 720
, damit die Teilbäume 24
und den 30
richtigen Abstand zueinander haben. Beachten Sie auch, dass 24
und 30
zwei Ebenen von Zweigen haben , weil 4
und 6
Kinder - Knoten haben , die richtigen Abstand und die Kinder - Knoten müssen 30
Notwendigkeit , sich auf der gleichen Ebene wie die Kinder - Knoten zu sein 24
.
720
/ \
/ \
/ \
/ \
/ \
24 30
/ \ / \
/ \ / \
4 6 5 6
/ \ / \ / \
2 2 2 3 2 3
Die Herausforderung
- Ihre Aufgabe ist es, einen korrekt beabstandeten, ästhetisch ansprechenden Teilerbaum für die Eingabe zu erstellen
n
, wobein
eine positive ganze Zahl größer als 1 ist. - Ihre Ausgabe kann führende und nachfolgende Leerzeichen sowie führende und nachfolgende Zeilenumbrüche enthalten, muss jedoch ansonsten den oben angegebenen Abstandsregeln entsprechen.
- Ihre Ausgabe darf sein: Textkunst, ein Bild (andere Formate müssen hinzugefügt werden, falls erforderlich).
- Stellen Sie bei Bildern sicher, dass die Knoten Ihres Baums einen ausreichenden Abstand haben und dass sich die Knoten auf derselben Höhe im Baum auf derselben Höhe im Bild befinden.
- Das ist Code Golf. Die geringste Anzahl von Bytes (oder eine entsprechende Anzahl) gewinnt.
Wir danken Stewie Griffin für das Nachdenken über diese Idee und Peter Taylor, Martin Ender, Mego und Eᴀsᴀ Iᴛᴇʀʟʏ für ihre Hilfe bei der Neufassung der Spezifikation. Wie immer sind Vorschläge oder Korrekturen sehr willkommen. Viel Glück und gutes Golfen!
Weitere Testfälle:
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
quelle
Antworten:
Python 2 ,
711651575559554547539540530522 BytesNachdem ich vier Monate lang versucht habe, diese Antwort zu schreiben, gegen eine Wand gelaufen bin und sie für Wochen stehen gelassen habe, spüle und wiederhole, habe ich endlich eine richtige ASCII-Kunstantwort für diese Herausforderung erstellt. Alles, was übrig bleibt, ist das Golfen. Daher sind Vorschläge zum Golfen sehr willkommen. Probieren Sie es online!
Golfs: -60 Bytes durch Umbenennen häufig verwendeter Funktionen und Ändern der Ergebnisausgabe. -73 Bytes, wenn geändert wird, wie die Höhen der Teilbäume überprüft werden, wie die Abstandsvariablen berechnet werden und wie das Ergebnis zurückgegeben wird. -3 Bytes von FlipTacks
isdigit()
Ersatz. -16 Bytes, die diesenisdigit()
Ersatz noch weiter ausbauen und "" durch "ersetzenE
. -5 Bytes nach geringfügigen Verbesserungen und nach dem Wechsel von Python 3 zu Python 2. -7 Bytes nach dem Ändern der Rückgabe des Ergebnisses. -8 Bytes aus einer kleinen Änderung, wieA
definiert ist, zuverändern , wie, zu entfernenT
definiert ist, und das HinzufügenW
, die Hypothese unter Verwendung dass jede Teilstruktur mit mindestens einem Zweig länger als sein Gegenstück, insgesamt notwendigerweise länger als sein Gegenstück istQ
insgesamt und Bearbeiten, wie das Ergebnis zurückgegeben wird. -10 Bytes von usingA<10
anstelle vonL(S(A))<2
forA
undB
. -8 Bytes vom Ändern der StandardeinstellungH
auf,[0]
da der Code das Problem von veränderlichen Standardargumenten vermeidet, indem er niemalsH
verändert, dieq
Definition ändert , indem er(B>9)
stattdessen verwendet1-(B<10)
, alles entferntp
undF
als Ersatz für erstelltp+q-M
.Fehlerbehebungen: Hypothese war falsch, Gegenbeispiel in
11**9 = 2357947691
. +1 ByteErläuterung
Die gesamte Funktion lässt sich in vier Schritten zusammenfassen:
n
,A
undB
.A
undB
und zeichnen Sie sie nach Bedarf neu.Ich werde jeden Schritt der Reihe nach durchgehen.
Schritt 1. Dies ist, ganz offen gesagt, der einfachste Schritt. Überprüfen Sie jede Zahl
z
zwischen 1 und der Quadratwurzel auf Teilbarkeit inn
und greifen Sie zu der größtenz
undn//z
der übereinstimmenden Zahl . Rückgabe nurstr(n)
wennn
ist prime (entwederA==1
oderB==n
)Schritt 2. Zeichnen Sie die Teilbäume von
A
undB
und ermitteln Sie die Anzahl der/\
Zweige zwischen den Knoten in den Teilbäumen. Dazu erhalten wir die Indizes jedes Schritts, der Ziffern enthält, die ersten Differenzen der Indizes und subtrahieren erneut 1. Sobald wir die Höhen haben, vergleichen wir sie, um die größten zu erhalten, und zeichnen die Teilbäume mit den neuen Höhen neu.Ich habe den schleichenden Verdacht, dass der Teilbaum, der insgesamt höher ist, immer Zweige hat, die mindestens so lang sind wie die Zweige des kürzeren Teilbaums, und ich kann das zum Golfen des Codes verwenden, aber ich habe noch keinen Beweis dafür.Gegenbeispiel in11**9 = 2357947691
.Schritt 3. Das Schreiben dieses Schritts dauerte Monate. Das Schreiben und Debuggen von Schritt 2 dauerte einige Tage, aber das Finden der richtigen Formeln für den Abstand dauerte ewig. Ich werde sehen, ob ich das, was ich herausgefunden habe, in ein paar Absätzen zusammenfassen kann. Beachten Sie, dass ein Teil des Codes in dieser Erklärung seitdem nicht mehr mit dem tatsächlichen Code übereinstimmt.
Erstens
p
,q
,h
,P
,Q
,s
undM
.p
ist die Anzahl der Zeichen vom Ende des linken Zweigs/
bis zum rechten Ende des linken Teilbaums.q
ist die Anzahl der Zeichen vom linken Ende des rechten Teilbaums bis zum Ende des rechten Zweigs/
.h
ist die Anzahl der Zweige zwischen der Wurzel und den Teilbäumen.P
undQ
sind nur die Umkehrungen vonp
undq
und sind nützlich, um die Abstände um/\
Zweige bis zur Wurzel zu platzierenn
.s
ist die Anzahl der Leerzeichen, die zwischen den beiden Teilbäumen eingefügt werden.M
ist am einfachsten; es ist die Länge vonn
. Grafisch setzen:Die Formel zur Bestimmung
p
lautet:p = len(x[0]) - x[0].rindex(str(A)[-1]) - (A<10)
Die Länge abzüglich des Nullindex des letzten Zeichens in A abzüglich einer Korrektur für einstelligeA
s.Die Formel zur Bestimmung
q
lautet wie folgt:q = y[0].index(str(B)[0]) + (B>9)
Der Index des ersten Zeichens in B plus eine Korrektur für die Indexierung auf Null minus eine Korrektur für einstelligeB
s (kombiniert zu einer Korrektur für mehrstelligeB
s).Die Formel zur Bestimmung
h
ist dies:h = H[0] or (p+q+M%2+2-M)//2 or 1
. Entweder greifen wir auf ein vordefiniertes Objekt zurück,H
was bedeutet, dass wir den Baum neu zeichnen(from_the_left + from_the_right + parity_space + 2 - len(root)) // 2)
, oder wir verwenden die Mindestanzahl von Zweigebenen, 1.Die Formel zur Bestimmung
s
ist dies:s = 2*h+M-p-q
. Wir subtrahierenp
undq
von der Anzahl der Abstände zwischen den Zweigen der Wurzel am breitesten2*h + M
.Schritt 4. Und zum Schluss setzen wir alles zusammen. Zuerst machen wir die Wurzel,
[" "*(P+h)+Z+" "*(Q+h)]
dann setzen wir die Zweige bis zu den Teilbäumen ein[" "*(P+J)+"/"+" "*(2*h+M-2*J-2)+"\\"+" "*(Q+J)for J in G(h)][::-1]
, und schließlich setzen wir unsere Teilbäume mit den richtigen Abständen ein[(" "*(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à! Wir haben uns einen ästhetisch ansprechenden Teilerbaum!
Ungolfing:
quelle
isdigit
Scheck sein'/'<x[i].strip()[0]<':'
?Mathematica,
9686817978 BytesDanke @MartinEnder für 2 Bytes.
Die Ausgabe sieht folgendermaßen aus:
Erläuterung
Generieren Sie die Liste der Teiler der Eingabe. Suchen Sie das Element, das der Quadratwurzel der Eingabe am nächsten liegt. (
Max
dient zur Verflachung der Ausgabe)Suchen Sie den anderen Divisor, indem Sie die Eingabe durch den oben angegebenen Divisor dividieren. Wenden Sie die Eingabe als Kopf des Ergebnisses an.
Wiederholen Sie den Vorgang.
Wenn der Eingang prim ist, machen Sie nichts.
Formatieren Sie die Ausgabe.
Edit: Eine ästhetisch ansprechendere Version (258 Bytes)
Die Ausgabe sieht folgendermaßen aus:
quelle
Sqrt@#
->#^.5
(dann können Sie natürlich keine Infixnotation verwenden,Nearest
aber dann können Sie verwendenMax@
).Kohle , 302 Bytes
Probieren Sie es online! Link ist eine ausführliche Version des Codes. Da die ausführliche Version sehr ausführlich ist, ist er eine JavaScript-Transliteration des Hauptalgorithmus:
quelle