Superpermutaciones

26

Introducción

Eres un criminal encargado de robar algunos planes secretos de la nueva startup tecnológica Dejavu. Te escabulles por la pared del fondo, pero encuentras una puerta que requiere un alfiler para abrirla. Reconoce la marca de la cerradura y sabe que se necesita un pin de 5 dígitos con todos los números del 0 al 4. Después de ingresar cada dígito, la cerradura verifica los últimos 5 dígitos ingresados ​​y se abre si el código es correcto. Tienes que pasar esta cerradura, y rápido.

Superpermutaciones en pocas palabras

Una permutación es todas las combinaciones posibles de un determinado conjunto de dígitos. por ejemplo, todas las permutaciones de los dígitos 0, 1, 2 son:

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

Si concatenamos todas estas permutaciones juntas, obtenemos una superpermutación:

012021102120201210

Esta superpermutación contiene todas las permutaciones de 0, 1, 2, pero es posible hacer una más corta que esta. Voy a saltar un poco aquí, pero la superpermutación más corta de estos dígitos es:

012010210

Para nuestros propósitos y propósitos, esta es esencialmente la cadena de dígitos más corta que contiene todas las permutaciones posibles de esos dígitos, es decir, una superpermutación.

Tarea

Su tarea es un poco más difícil que el ejemplo de superpermutación como se muestra arriba, porque tiene dos dígitos más de los que preocuparse. - Si no ha leído sobre las superpermutaciones, o mi ejemplo anterior no está claro, le sugiero que lea este excelente artículo de Patrick Honner sobre el tema (este desafío fue muy inspirado por su artículo, así que felicitaciones a él): https://www.quantamagazine.org/unscrambling-the-hidden-secrets-of-superpermutations-20190116/ . Su objetivo es escribir el programa más corto posible que genere una superpermutación de los dígitos 0 a 4.

Tanteo

Su programa no recibe ningún tipo de entrada y produce una superpermutación de los dígitos de 0 a 4. Esta superpermutación resultante debe imprimirse en la consola o mostrarse visiblemente al usuario en la medida que lo indique su idioma de elección. Esto no tiene que ser la permutación más corta posible, solo tiene que ser una superpermutación válida. Debido a esto, el objetivo es escribir el programa más corto con la superpermutación más corta, por lo que debe calcular su puntaje de la siguiente manera:

tamaño de archivo (bytes) * longitud de superpermutación generada (dígitos)

por ejemplo, si tuviera un programa de 40 bytes y mi superpermutación tiene 153 dígitos, mi puntaje será:

40 * 153 = 6120

como siempre, el objetivo es obtener este puntaje lo más bajo posible.

Modelo

Así es como debe publicar su respuesta:

Idioma | Puntuación

enlace al código en el entorno de trabajo (si es posible)

code snippet

explicación del código, etc.

Finalidades

Esta es una de mis primeras preguntas en este sitio. Entonces, dígame si me falta algo o una sección de mi desafío no está clara. ¡Gracias y diviértete jugando al golf!

Isaac C
fuente
¿Podemos saber la duración de la superpermutación más corta para tener una idea de la puntuación más baja?
Fatalize
1
@Fatalize 153 es el más corto
TFeld
1
@Fatalize Ver A180632 .
Arnauld
1
A primera vista, parece que solo pide una secuencia de Bruijn; sin embargo, el criterio de puntuación hace que este desafío sea interesante. ¡Bien hecho!
Erik el Outgolfer
3
@EriktheOutgolfer No es solo una diferencia de puntuación: una superpermutación incluye todas las permutaciones de cierta longitud, mientras que una secuencia de Bruijn incluye todas las cadenas de cierta longitud.
Anders Kaseorg

Respuestas:

6

05AB1E , puntuación = 1673 (7 bytes · 239)

žBœ∊{3ý

Pruébalo en línea!

Cómo funciona

ž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 , puntuación = 1944 (9 bytes · 216)

s+R+4d.p4

Pruébalo en línea!

Cómo funciona

 +R   .p4   append to each permutation d of [0, 1, 2, 3]:
   +4d        [4] + d
s           concatenate
Anders Kaseorg
fuente
1
vy3yJguarda un byte
Emigna
1
En el código Pyth, m+d-> +Rguarda un byte.
Isaac
8
¿No sería mejor publicar esto como dos respuestas separadas, ya que los enfoques y los lenguajes de programación son diferentes?
Kevin Cruijssen
@KevinCruijssen Meh, ambas son variaciones sobre el tema de unir permutaciones de 4 elementos con el elemento restante; mi respuesta 05AB1E en realidad tiene casi tanto en común con mi respuesta Pyth como con diferentes versiones de sí misma. Así que no quería pedir el doble de votos a favor solo para cambiar de idioma.
Anders Kaseorg
3

Brachylog , puntaje = 2907 (19 bytes × 153)

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

Demasiado lento para ver nada, pero si cambia 4por 2usted puede probar que: Pruébelo en línea!

Esto encuentra la superpermutación más corta como tal:

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
                  ∧
Fatalizar
fuente
2

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

Con este sistema de puntuación, hay poco espacio para algo entre 'codificar la supermutación óptima' y 'solo usar un breve incorporado para concatenar todas las permutaciones' , al menos en no-esolangs.

Aquí hay un intento de todos modos.

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

Pruébalo en línea!

Genera una cadena de 325 bytes:

012340124301324013420142301432021340214302314023410241302431031240314203214032410341203421
041230413204213042310431204321102341024310324103421042310432201342014320314203412041320431
210342104330124301423021430241304123042131024310423201432041321044012340132402134023140312
4032141023410324201342031421034301243021431024320143210
Arnauld
fuente
Tienes un punto válido, diré que estaba un poco preocupado por el sistema de puntuación. En el futuro, intentaré ser más considerado y calificar de una manera que permita una amplia variedad de métodos. : D
Isaac C
Si puede devolver una cadena de texto de menos de 23 bytes, la codificación dura mejor que esta solución ( 26975/153-153>23)
Sanchises
@Sanchises Necesitamos 5 repeticiones para una cadena, o 4 para un BigInt .
Arnauld
@Sanchises Podemos comprimir la cuerda ligeramente: ¡ Pruébelo en línea! (o menos si no cuenta el nsufijo predeterminado que console.logsale)
Neil
2

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

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

Pruébalo en línea!


También:

Python 2 , 12628 (154 * 82 bytes)

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

Pruébalo en línea!

TFeld
fuente
2

05AB1E , puntuación: 5355 2160 (216 * 10 bytes )

3ÝœJε4yJ}J

Puerto de @AndersKaseorg 's respuesta Pyth , así que asegúrese de que le Upvote!

Pruébalo en línea.

Explicación:

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)
Kevin Cruijssen
fuente
2

Octava , 27 x 442 = 11934

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

Pruébalo en línea!

Entonces, resulta que generar ingenuamente todas las permutaciones y luego truncar a la subcadena más corta que todavía es una superpermutación válida es más corta que generar la superpermutación más corta. Lamentablemente, esta vez el puntaje no es un palíndromo.

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

Pruébalo en línea!

Entrada actualizada por algunas cosas

  • a++ no está implementado para números simbólicos.
  • contains()no está implementado en Octave. Sustituido por any(regexp()).
  • En el enlace en línea, ingresé manualmente una asuperpermutación muy cercana a la 153. Esto permite verificar la solución.
Sanchises
fuente
2

CJam (6 * 240 = 1440)

5e!72>

Demostración en línea , validación (genera el índice en el que 0..4se puede encontrar cada permutación de ; necesita aplanar la salida porque el programa original proporciona una salida adecuada para stdout pero lo que coloca en la pila no se puede usar directamente).

Enfoque robado de Sanchises , aunque el orden de permutación de CJam es diferente, dando una subcadena diferente.


CJam (22 * 207 = 4554)

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

Demostración en línea , validación .

Disección

Esto utiliza una construcción recursiva 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
}/
Peter Taylor
fuente
1

Carbón , 29 bytes, longitud de salida 153, puntaje 4437

”)⊞⧴�r3⁼H⁴↓¦σ✳LïpWS [T↑ZωÞ”‖O

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación: Al igual que @TFeld, solo imprimo la mitad de una superpermutación y la reflejo. Calculé la superpermutación usando el siguiente código:

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

Esto se traduce en un programa de 45 bytes en carbón, por lo que habría obtenido un puntaje de 6885.

Neil
fuente
1

Japt -P, 2376 (11 x 216)

4o ¬á Ë+4+D

¡Intentalo!

-1 byte gracias a @ Shaggy!

La respuesta Pyth del puerto de Anders Kaseorg .

dana
fuente
1
Hay un atajo para q<space>;)
Shaggy
0

Perl 6 , 7191 (153 * 47 bytes)

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

Pruébalo en línea!

Encuentra el primer número que contiene todas las permutaciones de los dígitos 0 a 4. Esto llevará mucho tiempo ejecutarlo, pero puede probarlo con las dos primeras permutaciones 0y0,1

Jo King
fuente
0

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]

Pruébalo en línea!

J42161217
fuente
9936
ASCII
9504?
Solo ASCII
8424?
Solo ASCII
¡Agradable! Solo quería publicar una solución 153. Puede publicar una nueva respuesta si lo desea
J42161217
Ah, también ... explicación por favor: P
solo ASCII