Deadfish es uno de los más conocidos lenguajes de programación no completos de Turing. Tiene solo un acumulador (que comienza en 0) para almacenar datos, y solo cuatro comandos:
i - Increment the accumulator
s - Square the accumulator
d - Decrement the accumulator
o - Output the accumulator
Un programa de Deadfish puede verse así:
iiisdo
Y eso imprimiría:
8
El reto
Crear un programa que de entrada voluntad un código de número y Deadfish de salida para mostrar el número. (O hacer una función que toma el número como parámetro y devuelve el código.) Se debe trabajar para cualquier número entero de 0al255
Gol
Intente hacer que su código haga el código más corto posible para generar el número dado. Por ejemplo:
iiiiiiiiio
y
iiiso
cada impresión 9, pero la segunda es más corta.
Tanteo
Tu puntaje es:
The number of characters in your source code +
The sum of the lengths of your output for all numbers from 1-255
-100 if the language you chose is Deadfish :)
¡La puntuación más baja gana!
En el desafío original solo tenía la suma de 6 números (9,17,99,100 y 123). Esto fue de mí que quería no hacer que todos probaran cada número, y quería que el código más corto fuera relevante. Luego me di cuenta de que los programadores son buenos para hacer scripts para probar cosas como esa, y preferiría que este fuera un concurso para el mejor algoritmo con el golf como un desempate.
Por lo tanto, cambié esto, como lo sugirió Martin Büttner.
fuente
16^2 = 0o16^2 = 256o16^2 = error?-1OR256, se restablece a0. Pero si aciertas un número más grande que256al cuadrado, entonces no cambia, por ejemplo17^2 = 289. (vea la página de esolang)Respuestas:
Perl,
132131 bytes + 2.036 bytes = 2167Incluye +2 para
-lpEjecutar con el número de destino en STDIN, p. Ej.
deadfish.pl:
El grep es un filtro para restringir un poco la explosión exponencial (aunque este programa todavía necesita 2 GB para los casos difíciles). También funciona sin, pero no puedo ejecutarlo en mi hardware así, excepto por los casos fáciles. Pero, en principio, este
110=108+2programa de bytes también funciona:Lista de salida:
fuente
ES6 JavaScript 2126 + 311 = 2437 puntaje
Semi comentado:
Esto aprovecha el hecho de que en deadfish, puede imprimir más de un personaje.
Ejemplo:
10compila a loiodoque es "imprimir uno, disminuir, imprimir cero".Uso:
Aquí hay datos json de salida:
Eso fue generado por este código:
que imprime
result = (the result)yc =lo de arriba.Esto obtiene una puntuación notablemente alta a pesar de ser bastante simple. Busca el cuadrado perfecto más cercano, calcula la raíz cuadrada de ese cuadrado perfecto, agrega 's' e incrementa / disminuye apropiadamente.
Versión anterior que no utilizaba el hecho de que "10" = "imprime uno, imprime cero"
fuente
doperación fue incorrecto: si disminuye a-1, se restablece a0, no255.ohace; saca el acumulador y una nueva línea.iodosalidas1\n0\n, no10.o. Tampoco muchos compiladores (en diferentes idiomas) imprimen una nueva línea conoMathematica,
254165caracteres + 3455 = 3620Menos golf:
Creo que los números resultantes son óptimos. Esto está haciendo una búsqueda amplia de los 256 números, haciendo un seguimiento de la forma más corta que ha encontrado para representar cada número. La búsqueda está construyendo una especie de tabla de búsqueda en la función
gque luego se aplica a la entrada.Como referencia, aquí están todos los 255 resultados:
fuente
n > 256non ≥ 256. Y eso también está en línea con la página de esolang: "Aunque el comentario en los estados de implementación de C/* Make sure x is not greater then [sic] 256 */, la implementación establece el valor en cero si y solo sivalue == -1 || value == 256".d, por lo que debe imprimir 0.C, código 433 + salida 3455 = 3888
C ++, código 430 + salida 3455 = 3885
Y ahora para algo completamente diferente.
Utilicé el resultado de la respuesta de Mathematica de Martin (actualizado el 23 de octubre porque era incorrecto para más de 240 antes) Mi salida es los mismos 3455 caracteres. Analicé patrones en la salida y descubrí que [0,255] puede ser representado por esta secuencia:
isssisodsssio 0-16dsoEl siguiente paso fue construir cuidadosamente estas cinco columnas (a
ctravésgdel código a continuación). Usé números negativos para indicar endlugar deien columnaseyg. Luego, resulta que los resultados funcionan principalmente como un contador en lagcolumna, ya que cada filaugeneralmente elimina unodo agrega unoirelativo a la fila anteriorv). Hay 15 excepciones, que se almacenan enx(los índices) yb(las cinco columnas, empaquetadas en un número entero que solo requiere 14 bits para almacenar el máximo10832).Por ejemplo, la primera "excepción" es la primera fila, donde queremos cero caracteres aparte de la terminación
o. Asíx[0]es0, yb[0]es544, que cuando se desempaqueta es (estilo "little endian", ya queges la columna de conteo){ 32, 0, 4, 0, 0 }. Siempre restamos 32 degy 4 deepara hacer que funcionen los campos de bits sin signo (es decir, esas dos columnas representan números negativos conceptualmente cuandodse requiere en lugar dei, pero en la implementación los valores se compensan para evitar números negativos reales).Aquí hay una tabla que muestra cómo funcionan los primeros diez números (los espacios en blanco son ceros):
Puedes ver eso
gsu mayoría, solo se incrementa en uno para cada nueva fila, pero algunas filas (0, 4, 8, ..., que esperaba encontrar brevemente en OEIS) "restablecen" la secuencia, lo que significa quegadquiere un nuevo valor y al menos otra columna también se modifica.El recuento de caracteres de código excluye los espacios en blanco, excepto la nueva línea obligatoria antes de cada uno
#y el espacio después deunsignedyint. Puede guardar 3 caracteres compilando como C ++ en lugar de C, reemplazando<stdio.h>con<cstdio>y*(int*)&ucon(int&)u.Un dato curioso sobre este código: una versión anterior utilizaba una matriz de 256 uniones en lugar de solo
uyv. ¡Esa versión hizo que GCC 4.7.2 generara un error interno del compilador! Sin embargo, GCC 4.9 lo solucionó y el código anterior funciona con cualquier versión.fuente
for(...)conscanf- esto disminuiría el recuento de caracteres).#include, y tal vez podría hacer que elstructinteriorunionno tenga nombre.forbucle todavía es necesario debido a la forma en que calculo el resultado. Esto además de eliminar la estructura ahorró 5 caracteres; otro 2 fueron salvados cambiando==a>y eliminar el salto de línea final. :) El programa solo es completamente válido en C99, porquemainno devuelve un valor explícitamente; eliminando los#includeresultados en un error debido ascanf()ahora.256.Haskell,
220021772171 = 2036 + 135esto funciona al tener una lista infinita de todos los programas de deadfish, ordenados por su longitud, acompañados por el estado interno y la salida. la función
fbusca en la lista y devuelve la primera entrada que coincide.Este enfoque permite múltiples
oen cada código resultante, pero no lo limita a imprimir todos los dígitos por separado o imprimir el número entero de una vez. por ejemplo, aquí 216 tiene el código deiiosso.Editar:
según la especificación, cuando el estado es 256 (pero no 257) se convierte en un 0. Ahora mi código tiene esto en cuenta. por ejemplo, 160 es
iissoso.esto tiene algunos problemas de eficiencia; porque
les una lista de nivel superior, todos los elementos delque se han evaluado permanecen en la memoria, por lo que el tiempo de ejecución probablemente se quedará sin memoria en algún momento.Para calcular el puntaje, hice una versión equivalente pero con menos memoria.
mi código más eficiente funciona volviendo a calcular la lista en cada aplicación de
f, para que el recolector de basura pueda tirar la parte ya buscada de la lista. en cierto sentido, esta es una búsqueda de amplitud utilizando la pereza.el código más eficiente también agrega algunas restricciones más a los elementos de la lista: filtra todos los códigos que contienen
idodi, o contiene unscuando el estado es menor que 2.Editar:
moví la
gfunción del nivel superior a una función auxiliarf', por lo que ahoragfiltra los códigos que imprimen algo que no es un prefijo de nuestro número deseado. ahora el código es mucho más rápido.El código más eficiente:
tenga en cuenta que el código más eficiente no tendrá los mismos resultados porque los programas atraviesan todos los códigos posibles en un orden diferente. sin embargo, generarán códigos de la misma longitud. también, cambiando
c:xconx++[c]hace que los programas sean equivalentes.Con este código pude calcular todos los programas en
520.81 segundos.Editar:
aparentemente esta es la mejor respuesta! Lo noté justo ahora, tan lejos de cuando se le preguntó ...
Los resultados:
fuente
Picat 516 + 2060 = 2576
Es una versión algo modificada del programa Sergey Dymchenko . Esta versión genera programas de peces muertos más compactos.
Por lo que entendí la oración "longitudes de salidas", significa que debería sumar la salida sin caracteres de nueva línea.
Utilizar:
1-255 códigos:
Actuación:
Versión del programa para medir el tiempo:
Resultado:
Salida completa:
fuente
ioiolo que imprimiría"12"y no"11"JavaScript (E6) 141 + 3455 = 3596
La función recursiva que busca la raíz cuadrada más cercana, pero evitando 16 como 16 * 16 = 256 se cambiará a 0. Muchas otras respuestas no obtienen este punto.
Prueba en la consola FireFox / FireBug
Salida
fuente
Picat, código 242 + salida 3455 = 3697
Ver http://picat-lang.org/ para obtener información sobre Picat.
Menos golf:
fuente
Python 3 - 4286 + 168 = 4454
No es demasiado serio, pero extremadamente simple. Solo encuentra el mejor de sumar a 0, un cuadrado, un 4 4º potencia
y un 8 º potencia.EDITAR: Golfed 75 bytes, el 8 th potencia no hizo nada
EDIT 2: se eliminaron algunos bytes para implementar correctamente
d. Sin embargo, la puntuación aumentó.Python 3 - 2594 + 201 = 2795
Este utiliza un tipo de búsqueda profunda primero para encontrar el programa más corto. Le agregué algunas optimizaciones (¿innecesarias?) Para poder obtener el resultado; de esta manera no tiene que correr tantos caminos. Podría intentar eliminar algunos de ellos. No supera al JS, ya que utiliza trucos inteligentes como múltiples
o.EDITAR: Golfed 93 bytes, aparentemente tuve un crapton de código inútil dejado por el desarrollo. También eliminé todo lo que encontré innecesario hasta ahora. Aquí vengo, JS.
EDIT 2: Golfed otros 8 bytes. Eso
returnfue innecesario.EDITAR 3: Golfed 5 bytes adicionales. Ahora que nos hemos librado de eso, solo podríamos poner un en
eliflugar del otroreturn.EDIT 4: se corrigió la funcionalidad de
d. Tamaño aumentado en 1 byte, puntuación en algunos bytes.fuente
APL: 80 + 3456 = 3536
Explicación: (corregido después de la nota de edc65, gracias)
⍵ <4: ⍵⍴'i 'Si el argumento es menor que 3, repita "i" tantas veces
(⌈, ⌊) ⍵ * .5 ⍵ es el argumento, toma la raíz cuadrada y toma el techo y el piso
| ⍵-2 * ⍨ elevar el techo y el piso a la potencia 2, eliminar argumentos y hacer positivo
b ← ⊃ (>, <, =) / obtener un vector booleano con a> b, a
(⍵> 240) ⌽ Para evitar ir a 256, haga "i" para los números superiores a 240, en lugar de ^ 2
b / 'ids' usa ese booleano para tomar i, do s y agregarlo a la solución con,
, ∇ (-⊃b) + b [2] + ⍵ * ÷ 1 + 3⊃b Llama recursivamente a la función con el argumento -b 1 + b [2] elevado a la potencia (inverso de b [3] +1)
Puede contar la salida con:
¨ aplica la función a cada número 0-255
+ / ⊃, / ⍴¨ cuenta el número total de elementos
De nuevo, puedes probar todo lo anterior en TryApl.org
Por cierto: es 3456 y no 3455 porque también estoy considerando 0, ya que creo que el problema era preguntar. Si es 1-255, entonces el puntaje es 80 + 3455 = 3535
fuente
Python 2712 = 2608 + 104
Código:
Utilizar:
Código 0-255:
fuente
CJam,
2436 2392 22962173 ( 74 caracteres + 2099)Lo que se traduce en:
Intenta optimizar la longitud del código Deadfish eligiendo la ruta más corta para llegar a cada dígito del número.
Gracias Martin por la traducción Unicode
Aquí está la lista completa de código
Pruébelo en línea aquí:
fuente
oimprima nueva línea. Todos los compiladores también imprimían simplemente sin una nueva línea.C printf("%d\n",x);C# Console.WriteLine(x)GO fmt.Println(x)pascal WRITELN(val);python print accumulator (no comma)bash echo $no;; (no -n)