introduction

Vous êtes un criminel chargé de voler des plans secrets à la nouvelle startup technologique Dejavu. Vous vous faufilez par-dessus le mur du fond, mais trouvez une porte qui nécessite une épingle pour l'ouvrir. Vous reconnaissez la marque de la serrure et savez qu'il faut une broche à 5 chiffres en utilisant tous les chiffres de 0 à 4. Après chaque chiffre entré, la serrure vérifie les 5 derniers chiffres entrés et s'ouvre si le code est correct. Vous devez passer cette écluse et vite.

Superpermutations en bref

Une permutation est toutes les combinaisons possibles d'un certain ensemble de chiffres. par exemple, toutes les permutations des chiffres 0, 1, 2 sont:

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

Si nous concaténons toutes ces permutations ensemble, nous obtenons une superpermutation:

012021102120201210

cette superpermutation contient toutes les permutations de 0, 1, 2, mais il est possible d'en faire une plus courte. Je vais sauter un peu ici, mais la superpermutation la plus courte de ces chiffres est:

012010210

À nos fins, il s'agit essentiellement de la plus courte chaîne de chiffres qui contient toutes les permutations possibles de ces chiffres, c'est-à-dire une superpermutation.

Tâche

Votre tâche est un peu plus difficile que l'exemple de superpermutation comme indiqué ci-dessus, car vous avez deux chiffres de plus à vous soucier. - Si vous n'avez pas lu sur les superpermutations, ou mon exemple ci-dessus était un peu flou, je vous suggère fortement de lire cet excellent article de Patrick Honner sur le sujet (ce défi a été très fortement inspiré par son article, donc bravo à lui): https://www.quantamagazine.org/unscrambling-the-hidden-secrets-of-superpermutations-20190116/ . Votre objectif est d'écrire le programme le plus court possible qui génère une superpermutation des chiffres 0 à 4.

Notation

Votre programme ne prend aucune entrée d'aucune sorte et produit une superpermutation des chiffres de 0 à 4. Cette superpermutation résultante doit être imprimée sur la console ou affichée visiblement à l'utilisateur dans la mesure fournie par la langue de votre choix. Cela ne doit pas être la permutation la plus courte possible, il doit simplement s'agir d'une superpermutation valide. Pour cette raison, l'objectif est d'écrire le programme le plus court avec la superpermutation la plus courte, vous devez donc calculer votre score comme suit:

taille du fichier (octets) * longueur de super-permutation générée (chiffres)

par exemple, si j'avais un programme de 40 octets et que ma superpermutation comporte 153 chiffres, mon score sera:

40 * 153 = 6120

comme toujours, l'objectif est d'obtenir ce score le plus bas possible.

Modèle

Voici comment publier votre réponse:

Langue | But

lien vers le code dans l'environnement de travail (si possible)

code snippet

explication du code, etc.

Finalités

C'est l'une de mes premières questions sur ce site. Alors s'il vous plaît dites-moi si je manque quelque chose ou si une section de mon défi n'est pas claire. Merci et amusez-vous au golf!

05AB1E , score = 1673 (7 octets · 239)

žBœ∊{3ý

Essayez-le en ligne!

Comment ça marche

ž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 octets · 216)

s+R+4d.p4

Essayez-le en ligne!

Comment ça marche

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

Brachylog , score = 2907 (19 octets × 153)

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

Trop lent pour voir quoi que ce soit, mais si vous changez 4par, 2vous pouvez le tester: Essayez-le en ligne!

Cela trouve la superpermutation la plus courte en tant que telle:

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 octets)

Avec ce système de notation, il y a peu de place pour quelque chose entre «coder en dur la supermutation optimale» et «utiliser simplement un court intégré pour concaténer toutes les permutations» , au moins dans les non-esolangs.

Voici une tentative de toute façon.

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

Essayez-le en ligne!

Il génère une chaîne de 325 octets:

012340124301324013420142301432021340214302314023410241302431031240314203214032410341203421
041230413204213042310431204321102341024310324103421042310432201342014320314203412041320431
210342104330124301423021430241304123042131024310423201432041321044012340132402134023140312
4032141023410324201342031421034301243021431024320143210

Python 2 , score: 24327 15147 12852 12628 (154 * 82 octets)

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

Essayez-le en ligne!

Également:

Python 2 , 12628 (154 * 82 octets)

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

Essayez-le en ligne!

05AB1E , score: 5355 2160 (216 * 10 octets )

3ÝœJε4yJ}J

Port de @AndersKaseorg « s réponse Pyth , alors assurez - vous de le Upvote!

Essayez-le en ligne.

Explication:

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)

Octave , 27 x 442 = 11934

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

Essayez-le en ligne!

Ainsi, il s'avère que générer naïvement toutes les permutations puis tronquer à la sous-chaîne la plus courte qui est toujours une superpermutation valide est plus court que de générer la superpermutation la plus courte. Malheureusement, cette fois, le score n'est pas un palindrome.

Octave , 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

Essayez-le en ligne!

Entrée mise à jour pour quelques éléments

• a++ n'est pas implémenté pour les nombres symboliques.
• contains()n'est pas implémenté dans Octave. Remplacé parany(regexp()) .
• Dans le lien en ligne, j'ai entré manuellement une atrès proche de la superpermutation de 153 longueurs. Cela permet de vérifier la solution.

CJam (6 * 240 = 1440)

5e!72>

Démo en ligne , validation (affiche l'indice auquel chaque permutation de 0..4peut être trouvée; il doit aplatir la sortie car le programme d'origine donne une sortie appropriée à stdout mais ce qu'il place sur la pile n'est pas directement utilisable).

Approche volée à Sanchises , bien que l'ordre de permutation de CJam soit différent, donnant une sous-chaîne différente.

CJam (22 * 207 = 4554)

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

Démo en ligne , validation .

Dissection

Cela utilise une construction récursive simple.

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
}/

Gelée , 3000 (600 * 5 octets)

5ḶŒ!F

Essayez-le en ligne!

Fusain , 29 octets, longueur de sortie 153, score 4437

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication: Comme @TFeld, je viens d'imprimer la moitié d'une superpermutation et de la refléter. J'ai calculé la superpermutation en utilisant le code suivant:

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);

Cela se traduit par un programme de 45 octets en charbon de bois et aurait donc marqué 6885.

MATL , 16 x 442 = 7072

4Y25:Y@!)K442&:)

Essayez-le en ligne!

Port MATL de ma réponse Octave. -442 grâce à Luis Mendo

Japt -P, 2376 (11 x 216)

4o ¬á Ë+4+D

Essayez!

-1 octet grâce à @ Shaggy!

Port d'Anders Kaseorg est réponse Pyth .

Perl 6 , 7191 (153 * 47 octets)

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

Essayez-le en ligne!

Recherche le premier nombre qui contient toutes les permutations des chiffres de 0 à 4. Cela prendra beaucoup de temps à exécuter, mais vous pouvez le tester avec les deux premières permutations 0et0,1

Wolfram Language (Mathematica) , 153 * 95 octets, 14535

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

Essayez-le en ligne!