Me doy cuenta de que esto es un poco matemático, pero ... aquí va.
En matemáticas, la secuencia de hiperoperación es una secuencia infinita de operaciones aritméticas (llamadas hiperoperaciones) que comienza con la operación unaria del sucesor, luego continúa con las operaciones binarias de adición, multiplicación y exponenciación, después de lo cual la secuencia continúa con otras operaciones binarias que se extienden más allá exponenciación, utilizando la asociatividad correcta.
Su objetivo es escribir un programa que tome tres enteros x, y y n como entrada y produzca el resultado de la enésima hiperoperación en x e y.
P.ej
1 1 1
salidas 2
2 4 4
salidas 65536
3 3 4
salidas 7625597484987
- El programa debe escribirse en el código más corto.
- Puede tomar la entrada desde
STDIN
o desde un archivo. - Funciones de biblioteca no permitidas.
- Restricciones de entrada: n será ≥ 1.
http://en.wikipedia.org/wiki/Tetration tiene una buena explicación en caso de que no puedas entender esto.
fuente
n=1
? Si esx+y
ox+1
,1 1 1
debería devolver2
Respuestas:
Ruby, lento
86 8483 caracteresRuby, rápido
96 9493 caracteresLa primera versión es manera demasiado lenta con el último caso de prueba, por lo que añade una versión que utiliza la multiplicación como el caso base en lugar de adición. La primera versión tarda años en calcularse
3 3 4
; el segundo es instantáneo (en la consola IRB nativa; la versión web es un poco más lenta).Varias bellezas de Ruby aparecen aquí:
Casi cada declaración es una expresión en rubí. Por lo tanto, puede rellenar con punto y coma dentro del operador ternario, siempre que tenga suficientes paréntesis por ahí. Coffeescript tomó prestado ese. También tomó prestada la sintaxis de llamada "no se necesitan padres" de Ruby.
Retornos implícitos: esta es una característica interesante, y se desprende de la anterior. De hecho, comenzar la última línea de una función
return
se considera poco convincente, incluso cuando no se juega al golf.Los números son objetos en rubí (incluso
null
es un objeto). En ruby, los enteros tienen el métodotimes
, que ejecuta el bloque pasado varias veces. Este es solo uno de los muchos métodos iteradores de Ruby. Aquí, elupto
método nos permite guardar dos caracteres más sobre lo quetimes
nos permite.Unary
*
es el operador splat aquí. Convierte una matriz en una lista de argumentos. Al igual que JavascriptFunction#apply
, pero es más corto y mejor.Unary
&
convierte un procedimiento en un bloque. Si bien:to_i
es un símbolo, se convierte en un procedimiento bastante bien. Es decir, se convierte en un procedimiento que recurreto_i
a su argumento y devuelve el resultado. Más información sobre Stack Overflow.Sería posible obtenerlo aún más rápido si se usa
n=3
como el caso base, pero me temo que no es necesario. Sin embargo, solo costaría 11 caracteres, gracias a otra belleza del rubí: el operador de exponenciación**
. Python tiene este operador, pero no es el primero (como señaló @ aka.nice, gracias, Fortran ya tenía este operador).intérprete de rubí en línea disponible aquí: http://repl.it/Ikj/1
fuente
3 3 4
:) es muy lento.APL, 62
{...}⎕
: Toma la entrada evaluada (los números separados por espacios se evalúan en una matriz numérica) y le aplican la función.1=3⌷⍵:
: Si n es igual a 1 ...2⌷+\⍵
: Devuelve la suma de los 2 primeros elementos (x + y) ...⋄0=2⌷⍵:
: De lo contrario, si y es igual a 0 ...(⍵[3]⌊3)⌷⍵[1],0,1
: Crea una matriz numérica [x, 0,1] y devuelve el índicemin(n,3)
...⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1
: De lo contrario, ∇ (x, ∇ (x, y-1, n), n-1). (∇ es autorreferencia)Tengo un operador "hyper-raiser", que toma una función y devuelve la próxima hiperoperación
Por ejemplo,
+{⍺⍺/⊃⍴/⌽⍵}
sería la función de multiplicación y las+{⍺⍺/⊃⍴/⌽⍵}5 3
salidas 15.Pero no puedo hacer que vuelva a aparecer. Quizás alguien más pueda hacerlo.
fuente
Python, 83
(Basado en la respuesta de flornquake )
Muy lento para grandes resultados.
Para
2, 4, 4
la salida es65536
.fuente
Python,
9692Entrada:
3, 3, 4
Salida:
7625597484987
Acortado usando un par de ideas de @ WolframH .
fuente
Golfscript, lento, 39 caracteres
(enlace en vivo)
Este es el algoritmo recursivo estándar con un caso base de n = 1 (suma) (es decir, lento). Lo mismo que he usado en mi solución Ruby
Aquí hay una versión con mis anotaciones (principalmente mantenimiento de pila). No incluye una optimización que agregué más tarde:
~
es el operador eval. En el caso de las cadenas, trata la cadena como un programa GolfScript. Afortunadamente, una lista de enteros separados por espacios es un programa válido de GolfScript que empuja esos enteros en la pila. En comparación con esto, mi versión anterior de la rutina de entrada (" "/{~}/
dividida por espacio y evaluado cada una) es bastante pobre. En caso de funciones, llama a la función. Cuando está precedido por.
(clon), llama a la función consigo misma como primer argumento.Golfscript no parece ser exactamente adecuado para crear algoritmos recursivos. Si desea un algoritmo recursivo que no sea optimizable para las llamadas de cola, debe crear y destruir marcos de pila para preservar sus variables. En la mayoría de los idiomas, esto se hace automáticamente. En golfscript, debe clonar las variables (en realidad, apilar entradas) y destruir las entradas de apilamiento que ya no necesita. Golfscript no tiene ningún concepto de marcos de pila. ¿He dicho que GolfScript es un lenguaje basado en pila?
El primer requisito es comprensible. Tienes que especificar los argumentos de alguna manera. Solo es bueno si mantienen sus posiciones originales también. El segundo requisito es desafortunado, especialmente porque el valor de retorno está en la parte superior de la pila, y golfscript carece de la capacidad de eliminar cualquier elemento de la pila. Puede girar la pila y descartar el nuevo elemento superior, pero eso se acumula rápidamente.
\;
está bien.\;\;\;\;\;
no lo es Puede hacerlo\;
en bucle ({\;}9*
; costo: 6 caracteres para descartar hasta 9 elementos, o 7 caracteres para descartar hasta 99 elementos), pero podemos hacerlo mejor:Golfscript tiene matrices de primera clase. También tiene la sintaxis literal de la matriz
[1 2 3 4]
. Lo inesperado es eso[
y en]
realidad no son parte de la sintaxis. Son simplemente dos operadores:[
marca la posición actual en la pila y]
recopila cada elemento hasta que encuentra la marca de inicio de la matriz o se queda sin pila, y descarta la marca. Incluso puedes separar estos dos y ver qué pasa. Bueno, algo bastante interesante:¿Dije golfscript no tiene concepto de marcos de pila? Mentí. Se trata de un marco de pila:
[
. Se pueden descartar todo a la vez:];
. Pero, ¿qué pasa si queremos mantener el valor de retorno? Puede cerrar el marco de la pila en la entrada de la función (luego tenemos una versión ligeramente alterada de paso por matriz, no es un concepto interesante), o podemos cerrar el marco de la pila y tomar su último elemento en lugar de descartarlo por completo:]-1=
o pueden Subsi el último elemento en su lugar, y luego desechar el marco:])\;
. Tienen la misma longitud, pero este último es un poco más frío, así que lo estoy usando.Entonces, en lugar de 6 o 7 personajes para hacer una limpieza, podemos hacerlo con 5. Todavía siento que esto podría jugar más, pero bueno, hemos salvado a un personaje.
fuente
Smalltalk Squeak 4.x sabor muchos bytes!
Podría implementar una de las formas recursivas en Integer en 71 char
Luego, leer desde un archivo o FileStream stdin me costará un brazo ... Squeak obviamente no fue diseñado como un lenguaje de script. Así que gastaré muchos bytes para crear mis propias utilidades de propósito general no relacionadas con el problema:
Implemente este método de 21 caracteres en Stream (para omitir los seaparators)
Implemente este método de 20 caracteres en Comportamiento (para leer una instancia de un Stream)
Luego 28 caracteres en String (para crear un identificador de archivo)
Luego 59 caracteres en FileDirectory (para crear un readStream)
Luego 33 caracteres en BlockClosure (para evaluarlo n veces)
Luego 63 caracteres en la matriz (evalúe el argumento con el receptor y los argumentos tomados de la matriz)
luego resuelva el problema evaluando este fragmento de 31 caracteres en cualquier lugar para leer desde el archivo llamado x
Incluso sin contar las utilidades, ya son 71 + 31 = 102 caracteres ...
Ahora, como estoy seguro de perder el codeGolf, tengo una implementación más divertida en Integer:
Este método definirá (compilará) un mensaje binario hecho de n + si no existe (no lo entiende el receptor del mensaje m) y reiniciará la ejecución al comienzo del contexto del remitente. Inserté un retorno de carro adicional y espacios para facilitar la lectura.
Tenga en cuenta que
(m selector size-2min:1)hex last
es una forma abreviada de(m selector size>2)asBit printString
.Si no fuera para demostrar los superpoderes malvados de Smalltalk, la última declaración podría ser reemplazada por más corta y simple
Ahora implemente la utilidad de 28 caracteres en el Carácter (para repetirlo n veces en una Cadena)
Luego evalúa esta expresión de 43 caracteres:
Podemos acelerar con 10 caracteres más implementando en Integer:
y en este caso también tenemos un código más corto porque podemos reemplazarlo
^',(m selector size-2min:1)hex last
con^1'
Por un precio tan alto, el código funciona con el segundo entero = 0 :)
fuente
Groovy - 77
Nota: requiere cantidades obscenas de pila (y tiempo) para argumentos no pequeños.
fuente
AXIOM Computer Algebra System, bytes 69
prueba:
Esto eliminaría algo de recursión ... Posible cambio en x e y en algún retorno ... ¿hay otros valores de prueba?
fuente
APL (NARS), caracteres 61, bytes 122
prueba:
fuente