Einführung

Du bist ein Verbrecher, der einige geheime Pläne des neuen Tech-Startups Dejavu stehlen muss. Sie schleichen sich über die Rückwand hinein, finden aber eine Tür, für deren Öffnen ein Stift erforderlich ist. Sie erkennen die Marke des Schlosses und wissen, dass es eine 5-stellige PIN mit allen Ziffern von 0 bis 4 benötigt. Nach jeder eingegebenen Ziffer überprüft das Schloss die letzten 5 eingegebenen Ziffern und öffnet sich, wenn der Code korrekt ist. Du musst an dieser Schleuse vorbeikommen und zwar schnell.

Superpermutationen auf den Punkt gebracht

Eine Permutation sind alle möglichen Kombinationen eines bestimmten Ziffernsatzes. Beispielsweise lauten alle Permutationen der Ziffern 0, 1, 2 wie folgt:

012, 021, 102, 120, 201 und 210.

Wenn wir alle diese Permutationen miteinander verketten, erhalten wir eine Superpermutation:

012021102120201210

Diese Superpermutation enthält alle Permutationen von 0, 1, 2, aber es ist möglich, eine kürzere zu machen. Ich werde hier etwas überspringen, aber die kürzeste Superpermutation dieser Ziffern ist:

012010210

Für unsere Absichten und Zwecke ist dies im Wesentlichen die kürzeste Ziffernfolge, die alle möglichen Permutationen dieser Ziffern enthält, dh eine Superpermutation.

Aufgabe

Ihre Aufgabe ist etwas schwieriger als das oben gezeigte Beispiel für Superpermutation, da Sie sich um zwei weitere Stellen Sorgen machen müssen. - Wenn Sie nicht über Superpermutationen gelesen haben oder mein Beispiel oben etwas unklar war, empfehle ich Ihnen dringend, diesen großartigen Artikel von Patrick Honner zu diesem Thema zu lesen (diese Herausforderung war sehr stark von seinem Artikel inspiriert, also ein großes Lob an ihn): https://www.quantamagazine.org/unscrambling-the-hidden-secrets-of-superpermutations-20190116/ . Ihr Ziel ist es, das kürzestmögliche Programm zu schreiben, das eine Superpermutation der Ziffern 0 bis 4 erzeugt.

Wertung

Ihr Programm nimmt keinerlei Eingaben entgegen und erzeugt eine Superpermutation der Ziffern von 0 bis 4. Diese resultierende Superpermutation muss auf der Konsole ausgedruckt oder dem Benutzer sichtbar angezeigt werden, soweit dies von der Sprache Ihrer Wahl vorgegeben wird. Dies muss nicht die kürzestmögliche Permutation sein, es muss nur eine gültige Superpermutation sein. Aus diesem Grund besteht das Ziel darin, das kürzeste Programm mit der kürzesten Superpermutation zu schreiben. Berechnen Sie Ihre Punktzahl also wie folgt:

Dateigröße (Bytes) * generierte Superpermutationslänge (Ziffern)

Wenn ich zum Beispiel ein 40-Byte-Programm hatte und meine Superpermutation 153 Stellen lang ist, lautet meine Punktzahl:

40 * 153 = 6120

Ziel ist es wie immer, diese Punktzahl so niedrig wie möglich zu halten.

Vorlage

So kannst du deine Antwort posten:

Sprache | Ergebnis

Link zum Code in der Arbeitsumgebung (falls möglich)

code snippet

Code Erklärung usw.

Finalitäten

Dies ist eine meiner ersten Fragen auf dieser Site. Sagen Sie mir bitte, wenn ich etwas vermisse oder ein Teil meiner Herausforderung unklar ist. Vielen Dank und viel Spaß beim Golfen!

05AB1E , Score = 1673 (7 Bytes · 239)

žBœ∊{3ý

Probieren Sie es online!

Wie es funktioniert

žB          push 1024
  œ         permutations: ["1024", "1042", …, "4201"]
   ∊        vertically mirror: ["1024", "1042", …, "4201", "4201", …, "1042", "1024"]
    {       sort: ["0124", "0124", "0142", "0142", …, "4210", "4210"]
     3      push 3
      ý     join: "01243012430142301423…3421034210"

Pyth , score = 1944 (9 Bytes · 216)

s+R+4d.p4

Probieren Sie es online!

Wie es funktioniert

 +R   .p4   append to each permutation d of [0, 1, 2, 3]:
   +4d        [4] + d
s           concatenate

Brachylog , Score = 2907 (19 Bytes × 153)

4⟦pᶠP∧~l.g;Pz{sᵈ}ᵐ∧

Zu langsam , etwas zu sehen, aber wenn Sie ändern , 4indem 2Sie es testen können: Online ausprobieren!

Dies findet die kürzeste Superpermutation als solche:

4⟦                   The range [0,1,2,3,4]
  pᶠP                P is the list of all permutations of this range
     ∧
      ~l.            Try increasing lengths for the output
         g;Pz        Zip the output with P
             {sᵈ}ᵐ   For each permutation, it must be a substring of the output
                  ∧

JavaScript (ES6), 26975 (325 * 83 Byte)

Bei diesem Scoring-System gibt es wenig Raum für etwas zwischen "Hardcode für die optimale Supermutation" und "Verwenden einer kurzen integrierten Funktion zum Verketten aller Permutationen". , zumindest in Nicht-Esolangs.

Hier ist sowieso ein Versuch.

f=(a=[0,1,2,3,4],p=r='')=>a.map((v,i)=>f(a.filter(_=>i--),p+v))|~r.search(p)?r:r+=p

Probieren Sie es online!

Es generiert eine Zeichenfolge von 325 Bytes:

012340124301324013420142301432021340214302314023410241302431031240314203214032410341203421
041230413204213042310431204321102341024310324103421042310432201342014320314203412041320431
210342104330124301423021430241304123042131024310423201432041321044012340132402134023140312
4032141023410324201342031421034301243021431024320143210

Python 2 , Score: 24327 15147 12852 12628 (154 * 82 Byte)

S=str(int('OH97GKT83A0GJRVO309F4SGSRWD0S2T292S1JBPVKJ6CRUY8O',36))
print S+S[::-1]

Probieren Sie es online!

Ebenfalls:

Python 2 , 12628 (154 * 82 Byte)

S=oct(int('FS02C3XQJX14OTVMGM70CGCPWU41MNJZ0CO37ZMU0A0Y',36))[:-1]
print S+S[::-1]

Probieren Sie es online!

05AB1E , Score: 5355 2160 (216 * 10 Byte )

3ÝœJε4yJ}J

Port von @AndersKaseorgs Pyth-Antwort , also stelle sicher, dass du ihn positiv bewertest!

Probieren Sie es online aus.

Erläuterung:

3Ý           # Push a list in the range [0,3]: [0,1,2,3]
  œ          # Get all possible permutations of this list
   J         # Join each inner list together to a single string
    ε        # Map each string `y` to:
             #  (Push string `y` implicitly)
     4       #  Push 4
      y      #  Push string `y` again
       J     #  Join all three together
        }J   # After the map: Join all strings together to a single string
             # (and output it implicitly as result)

Oktave 27 x 442 = 11934

'01234'(perms(1:5)'(4:445))

Probieren Sie es online!

Es stellt sich also heraus, dass es kürzer ist , naiv alle Permutationen zu generieren und dann auf die kürzeste Teilzeichenfolge zu kürzen, die noch eine gültige Superpermutation ist, als die kürzeste Superpermutation zu generieren. Leider ist die Partitur diesmal kein Palindrom.

Oktave 97 x 153 = 14841

a=sym(9);while i<120
i=0;a+=1;q='01234';for t=q(perms(1:5))'
i+=any(regexp(char(a),t'));end
end
a

Probieren Sie es online!

Eintrag für ein paar Dinge aktualisiert

• a++ ist nicht für symbolische Zahlen implementiert.
• contains()ist in Octave nicht implementiert. Ersetzt durch any(regexp()).
• In den Online-Link habe ich manuell eine asehr nahe an der 153-Länge liegende Superpermutation eingegeben . Dadurch kann die Lösung überprüft werden.

CJam (6 * 240 = 1440)

5e!72>

Online-Demo , Validierung (gibt den Index aus, bei dem jede Permutation von gefunden werden 0..4kann; er muss die Ausgabe reduzieren, da das Originalprogramm eine geeignete Ausgabe für stdout liefert, aber was es auf dem Stapel ablegt, ist nicht direkt verwendbar).

Nähern Sie sich von Sanchises gestohlen , obwohl die Permutation der Reihenfolge der CJam unterschiedlich ist, eine andere Teilkette geben.

CJam (22 * 207 = 4554)

0a4{)W@+W+1$)ew\a*W-}/

Online-Demo , Validierung .

Präparation

Dies verwendet eine einfache rekursive Konstruktion.

0a       e# Start with a superpermutation of one element, [0]
4{       e# for x = 0 to 3:
  )      e#   increment it: n = x+1
  W@+W+  e#   wrap the smaller superpermutation in [-1 ... -1]
  1$)ew  e#   split into chunks of length n+1
  \a*    e#   insert an n between each chunk
  W-     e#   remove the -1s from the ends
}/

Gelee , 3000 (600 * 5 Bytes)

5ḶŒ!F

Probieren Sie es online!

Kohle , 29 Bytes, Ausgabelänge 153, Punktzahl 4437

”)⊞⧴�r3⁼Ｈ⁴↓¦σ✳ＬïpＷＳ [Ｔ↑ZωÞ”‖Ｏ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung: Wie bei @TFeld drucke ich nur die Hälfte einer Superpermutation und spiegele sie. Ich habe die Superpermutation mit folgendem Code berechnet:

Push(u, w);
for (u) {
    Assign(Plus(Plus(i, Length(i)), i), h);
    Assign(Ternary(i, Join(Split(w, i), h), h), w);
    Assign(Incremented(Length(i)), z);
    if (Less(z, 5)) for (z) Push(u, Slice(h, k, Plus(k, z));
}
Print(w);

Dies entspricht einem 45-Byte-Programm in Charcoal und hätte somit 6885 Punkte erzielt.

MATL , 16 × 442 = 7072

4Y25:Y@!)K442&:)

Probieren Sie es online!

MATL Port meiner Octave Antwort. -442 dank Luis Mendo

Japt-P, 2376 (11 x 216)

4o ¬á Ë+4+D

Versuch es!

-1 Byte danke an @ Shaggy!

Port of Anders Kaseorgs Pyth-Antwort .

Perl 6 , 7191 (153 * 47 Byte)

say first *.comb(permutations(5).all.join),0..*

Probieren Sie es online!

Findet die erste Zahl, die alle Permutationen der Ziffern 0 bis 4 enthält. Die Ausführung nimmt viel Zeit in Anspruch, aber Sie können sie mit den ersten beiden Permutationen 0und testen0,1

Wolfram Language (Mathematica) , 153 × 95 Bytes, 14535

Nest[Flatten[Join[#,{Max@#+1},#]&/@Partition[#,Max@#+1,1]]//.{b__,a__,a__,c__}:>{b,a,c}&,{0},4]

Probieren Sie es online!