Bei positiver Ganzzahl n > 2
. Wir konvertieren es wie folgt in ein Array:
- Wenn es gleich ist, wird
2
ein leeres Array zurückgegeben - Andernfalls erstellen Sie ein Array mit allen
n
Primfaktoren, die aufsteigend sortiert sind. Anschließend wird jedes Element durch seinen Index in der Reihenfolge der Primzahlen ersetzt und schließlich jedes Element in ein Array konvertiert
Lassen Sie uns beispielsweise eine Zahl 46
in ein Array konvertieren . Konvertieren Sie es zunächst in eine Reihe seiner Primfaktoren:
[2, 23]
Die Zahl 23
ist die 9
Primzahl. Ersetzen Sie sie 2
durch ein leeres Array und 23
durch [9]
. Array wird jetzt:
[[], [9]]
Primfaktoren von 9
sind 3
und 3
, also:
[[], [3, 3]]
Machen Sie dasselbe für beide 3
:
[[], [[2], [2]]]
Und schlussendlich:
[[], [[[]], [[]]]]
Um es zu kodieren, ersetzen wir einfach jede offene Klammer mit 1
und jede schließende Klammer mit 0
, entfernen dann alle endenden Nullen und lassen eine 1
vom Ende fallen. Dies ist unsere Binärzahl. Mit dem obigen Beispiel:
[ ] [ [ [ ] ] [ [ ] ] ]
| | | | | | | | | | | |
| | | | | | | | | | | |
V V V V V V V V V V V V
1 0 1 1 1 0 0 1 1 0 0 0
Nun einfach die letzten drei Nullen und die letzten fallen lassen 1
. Die Zahl wird 10111001
das ist 185
in Dezimal. Das ist die erwartete Ausgabe. Beachten Sie, dass in der Konvertierung von Array zu Binär keine Klammern des Hauptarrays enthalten sind.
Eingang
Positive ganze Zahl n
größer als 2
.
Ausgabe
Codierte Ganzzahl n
.
Regeln und IO-Format
- Es gelten Standardregeln.
- Die Eingabe kann eine Zeichenfolge oder eine Zahl sein (im Falle einer Zeichenfolge muss sie sich jedoch in der Basis 10 befinden).
- Die Ausgabe kann eine Zeichenfolge oder eine Zahl sein (im Falle einer Zeichenfolge muss sie sich jedoch in der Basis 10 befinden).
- Das ist Code-Golf , die kürzeste Antwort in Bytes gewinnt!
Testfälle
Weitere Testfälle auf Anfrage.
3 ---> 1
4 ---> 2
5 ---> 3
6 ---> 5
7 ---> 6
8 ---> 10
9 ---> 25
10 ---> 11
10000 ---> 179189987
10001 ---> 944359
10002 ---> 183722
10003 ---> 216499
10004 ---> 2863321
10005 ---> 27030299
10006 ---> 93754
10007 ---> 223005
10008 ---> 1402478
2
da die Einreichungen nicht zur Bearbeitung erforderlich sind.Antworten:
Schale ,
3531302926252422201915 Bytes-7 Bytes dank @Zgarb!
Indirekt wurden dank Zgarb weitere 4 Bytes gespeichert
Probieren Sie es online!
Erklärung
quelle
φ
den Fixpoint Lambda!`:0:1
kann sein`Jḋ2
.Jelly ,
22 2019 Bytes-1 danke an Erik den Outgolfer (Schwanz Nullen von beiden Seiten
t
, anstatt von rechtsœr
)Eine monadische Verknüpfung, die eine Ganzzahl größer als 2 und eine Ganzzahl größer als 0 zurückgibt (2 würde auch 0 gemäß der ursprünglichen Spezifikation zurückgeben).
Probieren Sie es online!
Wie?
Dies entspricht fast genau der angegebenen Beschreibung, nur mit einigen ordinalen Manipulationen für die Erstellung des binären Arrays ...
quelle
Python 2 ,
212177 BytesProbieren Sie es online!
Das Fehlen von eingebauten Primzahlen schadet der Byteanzahl wirklich und es tritt bei TIO mit größeren Primzahlen eine Zeitüberschreitung auf. Verwendet die Primalitätsprüfung von xnor .
Python 2 + gmpy2 , 175 Bytes
Probieren Sie es online!
Diese Version läuft bei größeren Testfällen (z. B. 10000 - 10008) nicht ab.
quelle
Mathematica,
125119 BytesVerwendet einen etwas anderen Ansatz; konvertiert Prime-Indizes in
{1, index, 0}
und 2 in{1, 0}
.Probieren Sie es auf Wolfram Sandbox
Verwendung:
quelle
Gelee , 35 Bytes
Probieren Sie es online!
quelle
J,
747366 BytesProbieren Sie es online!
Dies ist ein echtes Durcheinander, das sicherlich weiteren Golfsport erfordert (z. B. das Entfernen der expliziten Funktionsdefinition). Ich denke, dass das Boxen, das ich gemacht habe, besonders das ist, was das bytecount aufwirft, da ich wirklich nicht weiß, was ich dort mache (es war eine Menge Versuch und Irrtum). Außerdem bin ich mir ziemlich sicher, dass es einige integrierte Funktionen gibt, die ich vergesse (z. B. habe ich
_2,~_1,
wahrscheinlich eine integrierte Funktion).Erklärung (ungolfed)
Präambel
Lehnen Sie sich fest zurück, denn dies wird keine kurze Erklärung sein. Ironischerweise wurde eine knappe Sprache mit einer wortreichen Person gepaart.
Ich werde dies in einige Funktionen aufteilen
encode
codiert die Ganzzahl mit _1 und _2 anstelle von [und]convert
wandelt eine Liste von _1 und _2 in eine Liste von 1 und 0 umdrop
Lässt die letzte 1 und nachfolgende Nullen fallendecode
wandelt von einer binären Liste in eine Zahl umIch werde einen Beispielanruf für 46 durchgehen, der im ungolfed-Format fertig ist
Kodieren
Hier gibt es viel zu erklären.
Beachten Sie, dass die explizite Funktionsdefinition
3 : '[function]'
die Funktion so auswertet, als befände sie sich auf der REPL, wobei das richtige Argument jede Instanz von ersetzty
(dies bedeutet, dass die Verwendung von caps ([:
), atops (@
) und ats (@:
) auf Kosten von vermieden werden kann ein paar Bytes).So sieht es bei jeder Iteration der Eingabe von 46 aus
Diese Funktion verwendet advers (
::
), um die Werte in "Klammern" zu verschachteln (die hier verwendeten Klammern sind -1 und -2). Grundsätzlich wird bei jeder Faktorisierung und Umwandlung in Primzahlindizes _1 vorangestellt und _2 angehängt, die als Klammern fungieren. Wenn die Funktion für diese Elemente aufgerufen wird, werden sie nur so zurückgegeben, wie sie sind, daq:
beim Versuch, eine negative Zahl zu faktorisieren, ein Fehler auftritt. Es ist auch das Glück , dasq:
sich nicht auf einem Fehler beim 1 faktorisieren und stattdessen gibt das leere Feld (wie gewünscht).Konvertieren
Konvertieren ist viel einfacher. Es entfernt nur alle Boxing-Elemente sowie das erste Element und konvertiert dann alles in 1s und 0s (einfach durch Hinzufügen von 2).
Fallen
Dies kehrt die Liste um, findet die erste und löscht dann alle Werte bis zu dieser und kehrt die Liste erneut um.
Dekodieren
Decode ist die eingebaute Funktion,
#.
die eine Liste von Einsen und Nullen aufnimmt und in eine Binärzahl umwandelt.quelle
Retina ,
244227225 BytesProbieren Sie es online!
Dies ist ein direkter Ansatz, der dem in der Frage gezeigten Algorithmus folgt. Die Erzeugung des Primärindex ist exponentiell komplex, sodass bei größeren Eingaben eine Zeitüberschreitung auftritt
Erläuterung:
quelle
Haskell ,
162160155 BytesProbieren Sie es online!
Erläuterung:
r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]]
definiert eine unendliche Liste von Tupeln von Primzahlen und deren Indizes:[(1,2),(2,3),(3,5),(4,7),(5,11),(6,13), ...]
.Die Funktion
(%)
nimmt diese Lister
und eine Zahln
und konvertiert die Zahl in die umgekehrte Faktor-Array-Darstellung. Dies geschieht, indemr
wir durchlaufen, bis wir eine Primzahl finden, die sich teiltn
. Wir bestimmen dann rekursiv die Darstellung des Index dieses Prims und schließen ihn in0
und ein1
und stellen die Darstellungn
geteilt durch diesen Prim vor.Für
n=46
ergibt dies die Liste ,[0,0,0,1,1,0,0,1,1,1,0,1]
aus der dann die führenden Nullen (snd.span(<1)
) und die nächste1
(tail
) werden gelöscht. Danach wird die Liste in eine Dezimalzahl durch elementweise Multiplikation mit einer Liste von Zweierpotenzen umgewandelt und die resultierende Liste zusammenfassend:sum.zipWith((*).(2^))[0..]
.quelle
JavaScript, 289 Bytes
Die Bytes sind die Summe des JavaScript-Codes ohne Zeilenumbrüche nach den Kommas (die nur zur besseren Formatierung und Lesbarkeit eingefügt werden) (256 Bytes) und der zusätzlichen Zeichen für den Befehlszeilenschalter, der bei Verwendung von Chrome erforderlich ist (33 Bytes).
Und eine längere, besser lesbare Version:
Einige kurze Erklärungen:
f
ist ein rein funktionaler Algorithmus zur rekursiven Faktorisierung des Schwanzes.c
zählt an welcher Steller
die Primzahlp
in der Folge der Primzahlen vorkommt und entweder[]
(wennp=2
undr=1
) zurückgibt oderr
durch Rekursion zerlegt und weiterverarbeitet .h
ist eine kleine Hilfsfunktion, die leider notwendig ist, da siemap
die angegebene FunktionnumberOfCurrentElement
als zweites undwholeArray
als drittes Argument aufruft und somit die angegebenen Standardwerte überschreibt,c
wenn wir diese Funktion direkt übergeben würden. Ersetzenh
durch seine Definition wäre einige Bytes länger.s
transformiert das generierte Array in einen String. Wir verwendenblank
statt ,0
so dass wir verwenden können ,trim()
ino
.o
ist die Funktion, die mit dem Eingabewert aufgerufen werden soll, deri
die Ausgabe zurückgibt. Es generiert die für die Spezifikation erforderliche binäre Zeichenfolgendarstellung und konvertiert sie in eine (Dezimal-) Zahl.Bearbeiten: Chrome muss gestartet werden
chrome --js-flags="--harmony-tailcalls"
, damit die Schwanzrekursion optimiert werden kann (siehe https://v8project.blogspot.de/2016/04/es6-es7-and-beyond.html ). Dies erfordert auch die Verwendung des Strict-Modus.Der folgende Test zeigt, dass die Berechnung für einige Werte etwas langsam ist (der längste dauert
10007
auf meinem Computer mehr als sechs Sekunden ). Interessanterweise ist die Berechnung ohne Optimierung der Schwanzrekursion viel schneller (ungefähr Faktor 5), wenn kein Stapelüberlauf vorliegt.quelle
tinylisp , 209 bytes
Die letzte Zeile ist eine unbenannte Funktion, die die angegebene Codierung berechnet. Probieren Sie es online!
Pre-Golf-Version
Dies ist der Code, den ich hatte, bevor ich anfing, Golf zu spielen:
quelle
05AB1E , 18 Bytes
Probieren Sie es online!
Erläuterung:
quelle