La complejidad de Kolmogorov de una cadena s se define como la longitud del programa P más corto que emite s. Si la longitud de P es más corta que la longitud de s, entonces se dice que s es compresible , de lo contrario s es incompresible . La mayoría de las cadenas son incompresibles ...
Escriba el programa más corto que genera esta cadena (sin espacios y sin líneas nuevas):
d9 a6 b6 33 56 a7 95 4b 29 b0 ac 7f 2a aa 6d 19 b8 4b 4c f8 b6 2a ac 95
a1 4b 4e a5 9d b3 e7 c9 4c 49 59 ec 94 b3 aa 6c 93 8f 11 5a 4d 39 75 82
ec ea 24 cc d3 2d c3 93 38 4e b7 a6 0d d2 b5 37 23 54 ad 1b 79 aa 6e 49
55 52 94 5a a7 3a 6a e9 e4 52 cd 2d 79 ad c6 12 b5 99 5b b4 76 51 17 4e
94 f3 9a a2 e7 15 6a 55 14 4d 4e 4a a3 5c 2f ab 63 cc b5 a6 a4 92 96 8a
2e c3 d8 88 9b 8c a9 16 f5 33 22 5b a2 e2 cc 1b 27 d4 e8 db 17 a4 39 85
ca aa 5b 4f 36 24 d3 c6 f6 94 ad d7 0f 71 24 e1 b1 c5 ef 65 35 6c 8d d7
1a 87 1e 25 df 5d c0 13 b2 6f 5a 57 28 98 bd 41 66 04 ed a2 52 c9 ac 83
b3 6c 56 7e d1 c6 cc 53 4a 62 c5 59 a9 b2 d4 af 22 a5 a9 f4 b2 99 23 32
f8 fb ae 48 6a 8a 9a b5 46 7a 36 59 9f 92 d3 25 b5 19 bd 8a 4a 49 62 a5
e4 59 fb e5 ba a2 35 dd a9 36 1d a9 c9 69 89 77 6a b2 34 2d 1d 22 61 c5
c2 66 1c e2 76 74 52 a5 d9 84 b9 8a a6 b5 14 ec 29 58 b2 bc 96 16 16 48
f5 c5 bd 2f 32 1b 3d 4f 4b 2e b2 6b 9a d9 32 a4 4b 5c bc 92 b7 b3 26 39
fa 42 2d 64 ed 1a 79 49 4c a3 b7 85 b2 a6 e2 8c d9 55 90 e1 a8 87 4b 60
a6 e1 ba c4 bb ec 32 39 76 90 a6 b4 c6 65 79 61 91 aa 3d 54 b7 18 3d 15
4b 06 db 30 8a 4d 4a a1 35 75 5d 3b d9 98 ac 55 5b 10 dd b3 e2 cc f1 5e
b3 2b 53 90 b6 ee 2b ac 8f 88 8d 95 5a 75 df 59 2d 1c 5a 4c e8 f4 ea 48
b9 56 de a0 92 91 a9 15 4c 55 d5 e9 3a 76 8e 04 ba e7 b2 aa e9 ab 2a d6
23 33 45 3d c4 e9 52 e3 6a 47 50 ba af e4 e5 91 a3 14 63 95 26 b3 8b 4c
bc aa 5a 92 7a ab ad a6 db 53 2e 97 06 6d ba 3a 66 49 4d 95 d7 65 c2 aa
c3 1a 92 93 3f ca c2 6c 2b 37 55 13 c9 88 4a 5c 62 6b a6 ae cc de 72 94
La salida debería verse así:
d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4e...7294
Nota: no se permite la entrada del usuario, ni el acceso web, ni las bibliotecas (excepto la requerida para imprimir la salida).
Edición I: la secuencia parece aleatoria ... pero resulta ser altamente compresible manejando un poco de números primos ...
Edición II: ¡ Bien hecho! Revisaré las respuestas en las próximas horas, luego asignaré la recompensa. Esta es mi idea sobre cómo podría resolverse:
- Si intentas comprimir los datos, no te alejas ...
- En internet puede encontrar la (¿conocida?) Enciclopedia en línea de secuencias enteras (OEIS);
- probar los primeros dígitos hexadecimales
d9, a6, b6, 33, ...(o su representación decimal) no da ningún resultado; - pero si convierte los números a binario (
1,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0) y los busca en OEIS, obtendrá este resultado . - Como señaló Claudiu, también di una pequeña pista en la pregunta (Editar I arriba) ... :-)
El ganador es : Peter Taylor (GolfScript, 50), con una mención especial para Claudiu (Python, 92), el primero que lo "resolvió".
fuente
Respuestas:
GolfScript (50 bytes)
Dado que todos los demás ahora están revelando su código, también me adelantaré a la solicitud de OP para no ofuscar:
Disección general
38200,{:x,{)x\%!},,2=},4/pap&2 != 0, y haga una conversión de base-2 a base-16:{3\{2&!!1$++}/.57>39*+}%(aquí es donde están los trucos interesantes)+Disección más detallada de la conversión de base
Dada una pila que contiene una cadena vacía y una lista de números primos, necesitamos hacer dos conversiones:
Hay muchas maneras igualmente largas de hacer 1; p.ej
o incluso
Para 2, el enfoque obvio es
Pero base es una palabra larga, y como 16 = 2 4 podemos guardar fácilmente algunos caracteres con
Ahora el desperdicio más obvio son los 18 caracteres dedicados a esa cadena. Solo queremos una función de dígito a código ASCII. Queremos mapear
0a'0' = 48, ...,9a'9' = 57,10a'a' = 97, ...15a'f' = 102.Pero ahora arroja a la mezcla una prohibición
base. Necesitamos implementarlo nosotros mismos. La implementación obvia (en esta dirección, la fácil) es quek basees un pliegue{\k*+}*. La alternativa un poco más largo es una iteración directa, que necesita un caso base:0\{\k*+}/. Base 2 es ligeramente especial:1$++es equivalente a\2*+la misma longitud, y he adoptado ese enfoque.Ambos son más largos que el 5-char
2base, pero dado que ahora estamos iterando sobre los valores, podemos extraer en la parte 1 para tener un solo bucle. Reemplazamoscon
para un buen ahorro de 1 char, o
por una pérdida de 1 char.
Pero aunque esa pérdida de 1 carácter parece un paso atrás, considere lo que le sucede a ese 0. Se multiplica por 16 y se agrega a la salida de conversión de base. Y lo último que hacemos es agregar un múltiplo de 16 a la salida. Entonces podemos combinar los dos como
La articulación más corta y la inteligencia adicional lo hacen más interesante.
fuente
base? Todas las otras soluciones usan un equivalente (la mina usahex, la C usaprintf("%x"), la Haskell usashowHex)basees más largo que este, porque hice la mayor parte de la optimización después de aclarar que no podía usarla.baseme da un valor de 0 a 15, por lo que todavía necesita algo de trabajo para convertir0-9a-f. Podría volver a usarlobaseen algún momento, pero no esta noche.Python, 92 caracteres
¡Aquí están damas y caballeros, el código en sí!
Marzio dejó una pista inteligente al decir que "resulta ser muy compresible manejar un poco de números primos". Estaba seguro de que el "bit" no estaba en cursiva por accidente, así que convertí la cadena hexadecimal en bits e intenté encontrar patrones. Al principio pensé que él representaba todos los números primos como bits y los concatenaba, pero eso no funcionó. Entonces, tal vez solo tome unos pocos dígitos o elimine todos los ceros en la cadena de bits, aún no. ¿Quizás es una cadena de bits del bit menos significativo de los primeros números primos? No exactamente. Pero finalmente encontré el que funcionó: es una cadena de bits del segundo bit menos significativo de los primeros sin embargo, muchos primos.
Entonces, mi código hace exactamente eso: generar suficientes primos, tomar el segundo bit de cada (
i/2%2), concatenarlos como una cadena binaria, luego convertirlo a base-10 (int(..., 2)) y luego a base-16 (hex(...)).fuente
Haskell, 105
SHA1 hash:
a24bb0f4f8538c911eee59dfc2d459194ccb969cSalida:
Editar: Código:
Me perdí la regla sobre no usar ninguna función de biblioteca excepto la impresión (putStr). Supongo que los operadores matemáticos, aunque técnicamente son funciones, están permitidos.
fuente
C,
136116109103 caracteresBien, entonces, aquí está mi esfuerzo:
fuente
printfdevuelve el número de caracteres escritos, que aquí siempre es distinto de cero, puede usar en!printf(...)lugar deprintf(...)*0guardar un carácter.JS, 764
Si consideramos esta cadena como base64, podemos tener una versión más pequeña usando la versión un-base-64-ed:
Pero creo que el autor quiere que encontremos la lógica detrás de esta cadena no aleatoria.
fuente
Mathetmatica - 56
El misterio ya está resuelto, así que solo implementando la idea
fuente
J - 46 char
No te preocupes por mí, simplemente registrando el golf J aquí para la posteridad. No fue lo suficientemente inteligente como para descubrir el truco.
Explicado:
p:i.1007 4- Cree una matriz de 1007 filas y 4 columnas de enteros a partir de 0, luego tome los números primos correspondientes a esos enteros. Sí,p:es un J incorporado. Sí, somos cuatro primos cortos.2|<.-:- Reduzca a la mitad cada número (-:), suéltelo (<.) y tome ese módulo 2 (2|). Esto es lo mismo que tomar el bit significativo siguiente al arrendamiento.#.- Convierta cada fila del resultado de la base 2 en un entero. Esto nos da 1007 números del 0 al 15 inclusive.'0123456789abcdef'{~#.- Tome cada fila de esta matriz de bits como el binario para un número, y use ese número para seleccionar de la lista de dígitos hexadecimales. Esto convierte cada cuatro bits en el hex.1!:2&4- El intérprete J tiene un problema al generar cadenas de más de 256 caracteres, por lo que debemos enviar estos datos directamente a stdout. A veces se gana, se pierde algo.4[- Finalmente, descarte el resultado1!:2y, en su lugar, envíe los 4 que faltan de la salida. Hacemos esto porque es más corto que incluir esos últimos cuatro números primos y devolver un resultado vacío aquí.fuente
JS, 503
Siguiendo la idea de @xem:
fuente
Mathematica, 55
Probado en Mathematica 8. Esto hace uso de dos observaciones:
FromDigitsrealidad , Mathematica no verifica el rango de los dígitos dados, por lo tanto, si lo aplica a una lista del formulario{2,0,2,2,0,...}, obtendrá el doble de resultados que si aplicara{1,0,1,1,0,...}. Pero esa es exactamente la forma generada porBitAndlos primos con 2.fuente