Escribe el programa más corto que imprima la letra completa de "Never Gonna Give You Up" de Rick Astley.
Reglas:
- Debe emitir las letras exactamente como aparecen en el pastebin * anterior. Aquí está el volcado en bruto: http://pastebin.com/raw/wwvdjvEj
- No se puede confiar en ningún recurso externo: todas las letras deben ser generadas por / incrustadas en el código.
- Ningún uso de algoritmos de compresión existentes (por ejemplo, gzip / bzip2) a menos que incluya el algoritmo completo en su código.
- Use cualquier idioma, el código más corto gana.
Actualización, 1 de junio de 2012:
para las soluciones que contienen texto no ASCII, el tamaño de su solución se contará en bytes, según la codificación UTF-8. Si utiliza puntos de código que no se pueden codificar en UTF-8, su solución no se considerará válida.
Actualización, 7 de junio de 2012: ¡
Gracias a todos por sus increíbles soluciones! Aceptaré la respuesta más corta mañana por la tarde. En este momento, la respuesta GolfScript de Peter Taylor está ganando, ¡así que aprende algunas mejoras si quieres vencerlo! :)
* Hay un error tipográfico en el Pastebin (línea 46, "saber" debería ser "conocido"). Puede replicarlo o no a su discreción.
fuente
Respuestas:
Ruby
576 557556 (552) caracteres && PHP 543 caracteresOtra solución de búsqueda y reemplazo. Tenga en cuenta que esta forma de solución es esencialmente un Código de compresión basado en la gramática http://en.wikipedia.org/wiki/Grammar-based_code Consulte http://www.cs.washington.edu/education/courses/csep590a/07au /lectures/lecture05small.pdf para un ejemplo de compresión simple de entender.
He escrito las reglas de sustitución para que se calcule el carácter inicial de cada sustitución (están en orden ASCII secuencial); no necesita estar presente en los datos de transición.
notas de implementación
implementación anterior
Esta implementación anterior tiene 576 caracteres y comenzó con reglas de sustitución de la implementación bash / sed de ugoren. Ignorando el cambio de nombre de la variable de sustitución, mis primeras 28 sustituciones son exactamente las mismas que las realizadas en el programa de ugoren. Agregué algunos más para reducir el recuento general de bytes. Esto es posible porque mis reglas están representadas de manera más eficiente que las de la implementación de ugoren.
No intenté optimizar las reglas de sustitución en este caso.
notas del concurso
El esquema de descompresión de buscar y reemplazar funciona bien para este concurso porque la mayoría de los idiomas tienen rutinas preconstruidas que pueden hacer esto. Con una cantidad tan pequeña de texto para generar, los esquemas de descompresión complejos no parecen ser posibles ganadores.
Solo usé texto ASCII y también evité usar caracteres ASCII no imprimibles. Con estas restricciones, cada carácter en su código solo puede representar hasta un máximo de 6.6 bits de información; Esto es muy diferente a las técnicas de compresión reales en las que utiliza los 8 bits. En cierto sentido, no es "justo" comparar el tamaño del código gzip / bzip2 porque esos algoritmos usarán los 8 bits. Un algoritmo de descompresión más sofisticado puede ser posible si puede incluir ASCII tradicionalmente no imprimible en sus cadenas Y cada carácter no imprimible todavía está escrito en su código como un solo byte.
Solución PHP
La solución anterior toma el PHP de "un tipo triste" y lo combina con mis reglas de sustitución. La respuesta PHP resulta tener el código de descompresión más corto. Ver http://ideone.com/XoW5t
fuente
sedsolución seguramente no puede superarlo. Estoy trabajando en algo que, con suerte, tiene una posibilidad: tiene 75 bytes de sobrecarga, tal vez lo reduciré (no en Ruby).Bash / Sed,
705650588582 caracteresLógica :
la idea básica es el reemplazo simple. En lugar de escribir, por ejemplo,
Never gonna give you up\nNever gonna let you downescriboXgive you up\nXlet you downy reemplazo todoXconNever gonna.Esto se logra al ejecutar
sedcon un conjunto de reglas, en el formularios/X/Never gonna /g.Los reemplazos pueden estar anidados. Por ejemplo,
Never gonnaes común, pero también lo esgonnaen otros contextos. Entonces puedo usar dos reglas:s/Y/ gonna/gys/X/NeverY/g.Al agregar reglas, partes de los textos de las canciones se reemplazan por caracteres individuales, por lo que se acorta. Las reglas se vuelven más largas, pero si la cadena reemplazada es larga y frecuente, vale la pena.
El siguiente paso es eliminar la repetición de los
sedcomandos mismos. La secuencias/X/something/ges bastante repetitiva.Para hacerlo más corto, cambio los comandos sed para que se vean
Xsomething. Luego usosedpara convertir esto en unsedcomando normal . El código losed 's#.#s/&/#;s#$#/g;#hace.El resultado final es un
sedcomando, cuyos argumentos son generados por otrosedcomando, entre comillas.Puede encontrar una explicación más detallada en este enlace .
Código:
Notas:
El motor de descompresión tiene solo 40 caracteres de longitud. Los otros 543 son la tabla de traducción y el texto comprimido.
bzip2comprime la canción a 500 bytes (sin el motor, por supuesto), por lo que debe haber margen de mejora (aunque no veo cómo agregaría la codificación de Huffman o algo como esto lo suficientemente barato).<<Q(o<<_) se usa para leer hasta un carácter dado. Pero el final del guión (o expresión de comillas) es lo suficientemente bueno. Esto a veces causa una advertencia.Solución más antigua y simple, 666 caracteres:
fuente
\0con&.&hace 5.Espacio en blanco - 33115 caracteres
StackExchange mordió mi respuesta, aquí está la fuente: https://gist.github.com/lucaspiller/2852385
No es genial ... Creo que podría reducirlo un poco.
(Si no sabe qué es Whitespace: http://en.wikipedia.org/wiki/Whitespace_(programming_language) )
fuente
JavaScript
590588 bytesDependiendo ligeramente de la forma en que se "imprime" la cadena.
https://gist.github.com/2864108
fuente
if(g.indexOf(g[i])!=-1)antese=para arreglarlo.with(f.split(g[i]))f=join(pop())en elfor..inbucle guarda un byteC #
879816789 caracteresEl primer intento en CodeGolf definitivamente no es un ganador, estoy seguro de que es válido a pesar de su maldad.
fuente
var s1="a";var s2="b";intentar usarstring s1="a",s2="b"; si tienes más de 2 declaraciones es más corto.!y sacándolo de cualquier otro lado.Python,
597589 bytesEs posible exprimir otro par de bytes:
fuente
BrainFuck - 9905
Estoy bastante seguro de que puedo mejorar un poco ajustándolo, pero esto es bastante bueno por ahora. Suponiendo que no tiene ningún problema con que sea mucho más grande que el texto original.
fuente
Scala, 613 bytes
Este es un algoritmo de descompresión de texto, que aplica de forma recursiva la regla a la que se
~stuff~ blah ~ ~debe convertirstuff blah stuff stuff(es decir, la primera vez que ve un par de símbolos desconocido, delimita qué copiar; luego, completa el valor cuando lo ve).Nota: puede haber un retorno de carro adicional al final, dependiendo de cómo cuente. Si esto no está permitido, puede colocar el último en la cotización (guardar un carácter) y cambiar la división a
split(" ",-1)(gasto de 3 caracteres), para 615 bytes.fuente
Nrepeticiones de longitudL, usaL+N+1caracteres, mientras que yo usoL+N+2. Pero su código de descompresión es de 102 caracteres, mientras que el mío es de 40.589, C (solo la función de biblioteca es putchar)
Tabla de reglas de sustitución donde los caracteres en el rango -.._ (45..90) especifican qué regla aplicar, por lo tanto, se deben imprimir algunas 48 reglas (45, c-45> U48 en el código), otros caracteres
las reglas están delimitadas por el carácter '&' (38 en el código, n se disminuye hasta el cero y, por lo tanto, s apunta a la regla correcta)
la regla 0 indica que el siguiente carácter debe estar en mayúscula (al establecer k = 32 en el código), esto libera más espacio para agregar un rango continuo de caracteres más grande para las reglas
Se llama a main (..) con 1 (según la convención de programa C de argumento cero), y por lo tanto la regla 1 es la regla raíz
Evolución del código
recorté otros 9 bytes gracias a la sugerencia de ugoren
recortó otros 36 bytes creando una tabla algorítmicamente en lugar de a mano, y a través de la sugerencia "'"
afeitó otros 15 bytes cambiando la tabla de char * [] a una sola cadena donde '&' delimita las porciones
afeitado otros 19 bytes gracias a más consejos de ugoren
redujo 31 bytes al agregar más reglas, hizo una regla especial para capitalizar, permitiendo así más espacio para los índices de reglas.
recortó 10 bytes gracias a más consejos de urgoren y a ajustar ligeramente las reglas
fuente
*p>>4^3?putchar(*p):e(r[*p-48])"\'"traducción no es necesaria."We're"Es una cadena válida.ingEs un mejor candidato.d(int n)->d(n). Cambiar*s=='~'a*s-'~' and reverse the?:, also saving parenthesis around! N? ..: 0. Using 126 instead of'~' 'es inútil, pero ¿por qué~?mainrecursivo. La llamada inicial esmain(1)en lugar ded(0), pero puede ser tratada (tal vez un líder~ens). Además, la mejor alternativa~es una pestaña (ascii 9 - un solo dígito).Perl,
724714883 bytesEntonces, el cambio a las reglas que penalizan el uso de Latin-1 mató mi solución. Sin embargo, es un enfoque lo suficientemente diferente que odio eliminarlo, así que aquí hay una versión restringida que solo usa ASCII de 7 bits, según las nuevas reglas, con un gran aumento de tamaño.
Por supuesto, los caracteres de control todavía están destrozados aquí, por lo que aún querrá usar la codificación base64:
Porque creo que aún debería ser visible a pesar de ser DQ'd, aquí está la solución original:
La codificación base64 del script:
fuente
Python
781731605579 CaracteresHay muchas más y mejores respuestas de cuando vi esto por primera vez, pero perdí mucho tiempo en mi script de Python, así que lo publicaré de cualquier manera, sería increíble ver sugerencias para acortarlo aún más,
Editar: gracias a las sugerencias de Ed H 2 caracteres cortados, para ir más lejos, podría tener que reestructurar muchas cosas aquí, lo que tomará algún tiempo
Después de la primera vez que produje manualmente la cadena (muy tediosa), escribí una función para encontrar recursivamente el reemplazo de patrón que era más rentable (en ese paso), lo que me dio una solución pero resultó aumentar el tamaño en 10 caracteres
Entonces, hice mi algoritmo un poco menos codicioso al hacer la clasificación final solo en 'caracteres reducidos', clasificación en función de 'caracteres reducidos', 'longitud de patrón' y 'conteos de patrón'
longitud del patrón = recuento de longitud = recuento
Entonces le pregunté a mi pobre ordenador portátil para ejecutar infinitamente, la asignación de valores aleatorios para
lengthWeightycountWeighty obtener diferentes tamaños de compresión final, y almacenar los datos para los tamaños mínimos de compresión en un archivoEn media hora más o menos apareció con la cadena anterior (intenté seguir jugando para ver si podía acortar el código), y no irá más abajo, supongo que me estoy perdiendo algo aquí.
aquí está mi código, también
max_patternes muy lento (Nota: el código escupe una cadena similar a la del formulario en mi versión anterior de la solución, trabajé manualmente para obtener el formulario actual, quiero decir manualmente, manualmente en el shell de Python)fuente
\ncostaría 5 caracteres y ahorraría 9. 2. Espacio adicional enin (g,l..). 3.join(..)funciona tan bien comojoin([..])(al menos en 2.7).Malbolge, 12735 bytes
Pruébalo en línea.
Generado usando las herramientas aquí.
fuente
JavaScript 666 bytes
Inspirado en la solución de tkazec .
Echa un vistazo a la publicación de blog que escribí al respecto, contiene todas las fuentes y explica cómo construí ese código.
Puede copiar y pegar el código en la consola de su navegador. O pruébelo en http://jsfiddle.net/eikes/Sws4g/1/
fuente
Perl,
584578577576575571564554553540Esta solución sigue el mismo enfoque básico que la mayoría de los demás: dada una cadena inicial, realiza sustituciones repetidas de porciones repetidas del texto.
Las reglas de sustitución se especifican por un solo carácter, preferiblemente uno que no aparece en el texto de salida, por lo que una regla de longitud L y N veces ahorrará aproximadamente N * LNL-1 (N * L es la longitud original de todas las ocurrencias, pero el carácter de sustitución aparece N veces, y el texto literal en sí tiene una longitud L, y las reglas se dividen por un carácter de separación.) Si los caracteres de sustitución se especifican explícitamente, el ahorro se reduce a N * LNL-2. Dado que la mayoría de los lenguajes pueden calcular un carácter con chr () o un código similar, el primer enfoque tiende a ser superior.
Existen algunos inconvenientes para calcular el carácter de sustitución, siendo el más importante la necesidad de un rango continuo de caracteres ASCII. La salida usa principalmente letras minúsculas, pero hay suficientes letras mayúsculas y signos de puntuación para requerir reemplazar un carácter consigo mismo, reasignar algunos caracteres en una etapa de reparación posterior u ordenar las reglas para que los reemplazos con caracteres problemáticos ocurran antes. El uso de un lenguaje que reemplaza el uso de expresiones regulares también significa que hay trampas para los caracteres que tienen un significado especial dentro de una expresión regular:
.+*\?Mi enfoque original tenía 63 bytes en el decodificador y 521 en las reglas. Pasé mucho tiempo optimizando las reglas, lo que puede ser complicado, especialmente con las reglas cortas, ya que pueden superponerse. Obtuve la decodificación a 55 bytes y las reglas a 485 al engañar un poco la fórmula. Normalmente, una regla de 2 caracteres que ocurre 3 veces o una regla de 3 caracteres que ocurre dos veces en realidad no ahorraría ninguna longitud, pero hay una laguna, que también permite inventar palabras que no son parte de la salida; )
Hago uso de caracteres de control en esta solución, por lo que la solución se proporciona aquí codificada en base64.
Y aquí está como una versión ligeramente más legible (pero menos ejecutable).
Sin embargo, sospecho que esto todavía no es el mínimo, ya que Ed H. señala que la decodificación php es la más corta con 44 bytes y he visto margen para mejorar las reglas que está utilizando. Tengo un decodificador de 52 bytes en Perl, pero no pude usarlo para esta solución, ya que necesitaba ejecutar el rango en reversa.
fuente
PHP
730707 caracteresfuente
$s="Never gonna give...se puede acortar con$n.Perl -
589 588 583 579576 BytesCada regla consta de una cabeza de 1 carácter, un cuerpo y un guión bajo. Siempre que las reglas se puedan cortar desde el principio, el encabezado de la regla se reemplaza con su cuerpo en el resto del Texto. Se da el encabezado de la primera regla, los encabezados de todas las reglas siguientes se generan a partir de la variable $ i.
Como la regla anterior coloca la cabeza de la siguiente regla en el comienzo del texto, la última regla creará un carácter que ya no se eliminará. Tuve que elegir un rango de nombres donde el último sería "W", para poder eliminar la "W" original desde el comienzo de la letra, y reemplazarla por la sustitución de la regla.
La codificación se realizó mediante un script de Python utilizando un algoritmo simple de escalada.
Aquí está el código Perl:
(Me parece notable que el texto comprimido contenga "hearBach": D)
Y aquí el código de Python que lo genera:
fuente
whilepara el bucle; Esto le permite renunciar a los corchetes, así como a los paréntesis. Otra idea: averiguar cómo usar ensaylugar deprinthacer la salida.Python 2.7,
975803 bytesNo es lo mejor: (ahora) desearía que Python formateara expansiones así. Por desgracia no lo hace.
Editar: expansión simulada con sintaxis de formato alternativo (más o menos ..)
fuente
Clojure
720 bytes / caracteres:
(Reproducido aquí con espacios en blanco adicionales para que pueda ver el formato)
fuente
C # - 605 caracteres | T-SQL - 795 caracteres | C # - 732 caracteres | C # - 659 caracteres
La inspiración para esto vino del ejemplo sed. El único cambio importante que hice de eso fue hacer búsquedas en caracteres ASCII consecutivos para que no tuvieran que ser declarados. Desafortunadamente, es C #, así que no sé cómo hacerlo más pequeño. Tomé el mismo texto de reemplazo e hice el código en T-SQL usando una tabla temporal.
T-SQL
C # - Segundo intento Esto fue probar con un enfoque diferente. La compresión fue realizada completamente por la computadora buscando los mejores reemplazos. Las búsquedas son secuenciales y están ordenadas por tamaño, por lo que no hay necesidad de búsquedas delimitadas, sin embargo, el código para hacer las búsquedas fue menos eficiente de lo que pensaba, ¡así que terminó costando 127 caracteres más en general! Vive y aprende.
3er intento en C #. Esta vez expirementé con \ b, \ r, \ t caracteres. Puede usar \ rN \ n para reemplazar el primer carácter de la línea con una N mayúscula, pero en realidad no guardó caracteres. Creé \ b alias para mover el cursor hacia atrás y luego escribir sobre el texto existente. Pero nada de esto ahorró espacio y al final todavía estaba peor que una simple estrategia de búsqueda y reemplazo.
fuente
REPLACEenfoque inteligente , especialmente con el SQL dinámico, pero hay muchas maneras de jugar al golf más: utilícelo@como variable en lugar de@shacerlo una tabla permanente entlugar de#t(no tiene que limpiar después de usted mismo), deshacerse de la declaración COLLATE de 29 caracteres y simplemente requerir que se ejecute en un servidor / base de datos con la clasificación, usovarchar(999)ovarchar(max)toneladas de espacio en blanco innecesario alrededor de signos iguales y comas, etc.PHP,
591585568564 bytesfuente
Rubí, 1014 bytes
Solo estoy aprendiendo programación, así que no voy a romper ningún récord aquí. Pero, esta fue una tarea divertida.
fuente
GolfScript (511 bytes)
Esto utiliza un cambio de base para empaquetar los bits, por lo que incluye caracteres que no están en ASCII. Sin embargo, no es apropiado calificar esos caracteres por su codificación UTF-8 porque el intérprete trata el programa como ISO-8859-1. Por esta razón, he especificado la longitud en bytes en lugar de caracteres.
Base 64 codificada:
Volcado hexadecimal (salida de
xxd):Como la mayoría de las mejores soluciones, esto utiliza un enfoque basado en la gramática con divisiones y uniones de cadenas para expandir la gramática. La gramática tiene 30 reglas y fue encontrada por una búsqueda codiciosa.
fuente
JavaScript, 854 caracteres (nuevas líneas agregadas para "legibilidad")
fuente
Ingenuo sh / echo - 810 bytes
fuente
JavaScript 789 caracteres
Mi javascript (se imprime con "document.write ()"):
Cambio algunas palabras y frases comunes con letras cirílicas y luego las vuelvo a cambiar con la función replace ().
Después de acortar la letra, acorté mi programa con el mismo método y ejecuté el código con eval ().
fuente
Rubí,
741678657627619 bytesEsta es una expansión iterativa de símbolos. Para cada uno de los 28 caracteres de la cadena en el primer argumento de
gsub!, todas las apariciones de ese carácter_se reemplazan por la sección apropiada de la segunda cadena (separada por+caracteres).fuente
Python, 573 caracteres
Mi
sedsolución no irá más allá, y fue golpeada por varias personas, así que decidí un nuevo enfoque.Desafortunadamente, solo es lo suficientemente bueno para el
segundo ytercer lugar (a partir de ahora): Ed H. todavía está mucho por delante de mí .Notas :
La idea principal fue tomada de Ed H., usando caracteres consecutivos para el reemplazo, en lugar de especificarlos en cada regla de reemplazo.
Mi manera de tratar con los personajes que existen en la canción
es diferente a la de Ed: simplemente me aseguro de traducir cada uno a sí mismo (y si siempre va seguido de algo, agréguelo también, lo que solo funcionóW).El código es generado por un script que busca buenas traducciones. Al principio, utilicé un algoritmo codicioso, que simplemente toma el que da la mejor reducción. Luego descubrí que ajustarlo para que prefiera cadenas más largas lo mejora un poco. Supongo que todavía no es óptimo.
fuente
Golfscript,
708702699691 bytesfuente
" I'm feeling":i;?j, asigné tres cadenas concatenadas (eliminadas{y}, pero agregadas++para la concatenación). Esto me permitió declarar enilínea, al componer los contenidos dej.gy para el coro usando una sola cadena con nuevas líneas y luegon/g*gya que también se usa hacia el final (realmente posible, pero al final habría costado 1 personaje más). Sin embargo, el enfoque de división / plegado para insertar g al comienzo de cada línea es un gran protector de caracteres.Java, 858 bytes
Guau. Realmente no pensé que pudiera comprimir esto tan duro.
UngolfedEn una forma legible por humanos:fuente
String foo; String bar;cuando no golfistas.JavaScript,
14281451883 * caracteresDefinitivamente no es la solución más corta, pero aquí va.
La lógica de la solución es bastante simple:
* Por supuesto, la solución se vuelve mucho más corta cuando se toman líneas únicas en lugar de palabras únicas.
fuente