Faktorbäume dekodieren

11

Falls Sie Encode Factor Trees verpasst haben , finden Sie hier die Definition eines Factor Tree:

  • Die leere Zeichenfolge ist 1.
  • Verkettung steht für Multiplikation.
  • Eine in Klammern eingeschlossene Zahl n (oder ein beliebiges gepaartes Zeichen) stellt die n- te Primzahl dar, wobei 2 die erste Primzahl ist.
    • Beachten Sie, dass dies rekursiv erfolgt: Die n- te Primzahl ist der Faktorbaum für n in Klammern.
  • Die Faktoren einer Zahl sollten vom kleinsten zum größten geordnet werden.

Hier sind zum Beispiel die Faktorbäume für 2 bis 10:

()
(())
()()
((()))
()(())
(()())
()()()
(())(())
()((()))

Diese Herausforderung verwendet ein ähnliches Format. Diese Herausforderung besteht jedoch darin , diese Strukturen zu dekodieren .

Testfälle

Schamlos gestohlen von der letzten Herausforderung umfunktioniert .

Zusätzlich zu den 9 oben…

()()((()))((())) => 100
(()(()(()))) => 101
(()())(((())))(()(())) => 1001
(((((((()))))))) => 5381
(()())((((()))))(()()(())(())) => 32767
()()()()()()()()()()()()()()() => 32768

Regeln

  • Bei den gepaarten Zeichen in der Eingabe können Sie zwischen Klammern, Klammern, Klammern oder spitzen Klammern wählen. Ich kann andere Formate (z. B. XML-Tags) zulassen, wenn ich dazu aufgefordert werde.
  • Sie sollten in der Lage sein, Faktorbäume für eine beliebige Anzahl von 2 bis 2 15 oder 32768 zu verarbeiten.
  • Da dies , gewinnt die kürzeste Antwort in Bytes.
Nissa
quelle

Antworten:

9

Wolfram Language (Mathematica) , 52 45 Bytes

ToExpression@*StringReplace[{"["->"Prime[1"}]

Probieren Sie es online aus!

Die Eingabe verwendet Klammern.

Wandelt die Eingabe in einen Mathematica-Ausdruck um, der das Ergebnis berechnet. Wir tun dies einfach durch Ersetzen [durch Prime[1. Dies funktioniert , weil Verkettung ist Multiplikation in Mathematica.

Martin Ender
quelle
8

Prolog (SWI) , 134 128 127 124 Bytes

Diese Antwort ist Teil einer Zusammenarbeit zwischen mir und 0 '. Wir haben beide zusammen daran gearbeitet. Der einzige Grund, warum ich es poste, ist, dass ich Rock, Paper, Scissors gewonnen habe.

\Q-->{Q=1};"(",\N,")",\B,{findnsols(N,I,(between(2,inf,I),\+ (between(3,I,U),0=:=I mod(U-1))),L)->append(_,[Y],L),Q is Y*B}.

Probieren Sie es online aus!

Erläuterung

Diese Antwort ist ein perfektes Beispiel dafür, was Golfen im Prolog Spaß macht.


Diese Antwort verwendet das leistungsstarke System von Prolog für bestimmte Klauselgrammatiken. Hier ist unsere Grammatik etwas ungepflegt.

head(1)-->[].
head(Q)-->"(",head(N),")",head(B),{prime(N,Y),Q is Y*B}.
isprime(I):- \+ (between(3,I,U),0 =:= I mod(U-1)).
prime(N,Y):-
  findnsols(N,I,(
    between(2,inf,I),
    isprime(I)
  ),L),
  append(_,[Y],L),!.

Die erste Konstruktionsregel lautet:

head(1)-->[].

Dies teilt Prolog mit, dass die leere Zeichenfolge 1 entspricht.

Unsere zweite Konstruktionsregel ist etwas komplexer.

head(Q)-->"(",head(N),")",head(B),{prime(N,Y),Q is Y*B}.

Dies sagt uns, dass jede nicht leere Zeichenfolge Klammern um eine Klausel mit denselben Regeln rechts von einer Klausel mit denselben Regeln enthält.

Es sagt uns auch, dass der Wert dieser Klausel ( Q) der Regel folgt:

{prime(N,Y),Q is Y*B}

Dies aufzuschlüsseln, Qist das Produkt von 2 Zahlen Yund B. Bist nur der Wert der Klausel links und Ydie Nth Primzahl, wobei Nder Wert der Klausel in den Klammern steht.

Diese Regel deckt beide Formationsregeln des Faktorbaums ab

  • Verkettung multipliziert
  • Das Gehäuse erhält die n-te Primzahl

Nun zu den Prädikatdefinitionen. In der ungolfed-Version spielen zwei Prädikate eine Rolle (in meinem eigentlichen Code habe ich die Prädikate vorwärts verkettet). Die zwei relevanten Prädikate hier sind isprime/1, die mit einer Primzahl übereinstimmen, und prime/2die gegeben Nund Ymit iff übereinstimmt, wenn Ydie Nth Primzahl ist. Zuerst haben wir

isprime(I):- \+ (between(3,I,U),0 =:= I mod(U-1)).

Dies funktioniert mit einer ziemlich standardmäßigen Definition von Primalität. Wir bestehen darauf, dass es keine Zahl zwischen 2 und I, einschließlich 2, gibt, aber nicht I, die teilt I.

Das nächste Prädikat ist auch ziemlich einfach

prime(N,Y):-
  findnsols(N,I,(
    between(2,inf,I),
    isprime(I)
  ),L),
  append(_,[Y],L),!.

Wir verwenden findnsols, um die ersten NZahlen zu finden , die Primzahlen sind, und geben dann die letzte zurück. Der Trick dabei ist, dass zwar findnsolsnicht garantiert wird, dass die kleinsten N Primzahlen gefunden werden, aufgrund der Art und Weise, wie SWI damit umgeht between, kleinere Primzahlen jedoch immer früher gefunden werden. Dies bedeutet jedoch, dass wir schneiden müssen, um zu verhindern, dass mehr Primzahlen gefunden werden.


Die Golfplätze

Wir können die Vernunft in unserem Code zweimal weiterleiten. Da isprimewird nur verwendet, wenn seine Definition innerhalb von verschoben werden kann prime. Die nächste besteht darin, sich primedirekt innerhalb des DCG zu bewegen. Da wir jedoch einen Cut-In verwenden prime, um zu verhindern findnsols, dass zu viele Primzahlen erzeugt werden, haben wir ein kleines Problem. Der Schnitt schneidet das gesamte DCG anstatt nur das Bit, das wir wollen. Nach einigem Durchgraben der Dokumentation haben wir festgestellt, dass once/1nur dieser Teil, aber nicht das gesamte DCG geschnitten werden kann. Weitere Dokumentationsarbeiten ergaben jedoch, dass der ->Bediener auch zur Ausführung einer ähnlichen Aufgabe verwendet werden kann. Der ->Operator entspricht in etwa dem, ,!,also haben wir unseren Schnitt auf die andere Seite verschoben append/3und durch ersetzt ->.

In SWI-Prolog können Prädikate (und Regeln) Operatoren als Namen angegeben werden, wodurch wir die normalerweise erforderlichen Klammern löschen können. Dadurch können wir durch Aufrufen der Regel 6 Bytes sparen \.

Post Rock Garf Hunter
quelle
1

JavaScript (ES6), 98 Byte

Inspiriert von Notjagans Python-Antwort . Verwandelt den Eingabeausdruck in eine riesige und hässliche ausführbare Zeichenfolge.

s=>eval(s.split`)(`.join`)*(`.split`(`.join`(g=(n,k)=>(C=d=>n%--d?C(d):k-=d<2)(++n)?g(n,k):n)(1,`)

Das Zusammenführen der Cund g-Funktionen zu einer einzigen kann einige Bytes einsparen, würde jedoch noch mehr Rekursion erfordern.

Testfälle

Arnauld
quelle