Evaluar la enésima hiperoperación

12

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 STDINo 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.

Soham Chowdhury
fuente
¿Qué es n=1? Si es x+yo x+1, 1 1 1debería devolver2
John Dvorak
Sabía que había cometido un error en alguna parte :) arreglado, gracias.
Soham Chowdhury
1
Me escribí un pseudocódigo, luego me di cuenta de que en realidad es un código Ruby válido (casi :-()
John Dvorak
1
No, n> = 1 solamente.
Soham Chowdhury

Respuestas:

4

Ruby, lento 86 84 83 caracteres

def f x,y,n
n>1?(c=x;2.upto(y){c=f(x,c,n-1)};c):x+y
end
p f *gets.split.map(&:to_i)

Ruby, rápido 96 94 93 caracteres

def f x,y,n
n>1?(n>2?(c=x;2.upto(y){c=f(x,c,n-1)};c):x*y):x+y
end
p f *gets.split.map(&:to_i)

La 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 returnse considera poco convincente, incluso cuando no se juega al golf.

Los números son objetos en rubí (incluso nulles un objeto). En ruby, los enteros tienen el método times, que ejecuta el bloque pasado varias veces. Este es solo uno de los muchos métodos iteradores de Ruby. Aquí, el uptométodo nos permite guardar dos caracteres más sobre lo que timesnos permite.

Unary *es el operador splat aquí. Convierte una matriz en una lista de argumentos. Al igual que Javascript Function#apply, pero es más corto y mejor.

Unary &convierte un procedimiento en un bloque. Si bien :to_ies un símbolo, se convierte en un procedimiento bastante bien. Es decir, se convierte en un procedimiento que recurre to_ia 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=3como 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

John Dvorak
fuente
Bien, pero todavía estoy esperando una salida de 3 3 4:) es muy lento.
Soham Chowdhury
@SohamChowdhury el caso base es la suma. Con un caso base de multiplicación, también sería muy lento (y más largo). Recomiendo probar con exponenciación en su lugar ;-)
John Dvorak
Se puede ahorrar tiempo al uso memoization, pero que costaría algunos bytes (unos cuantos)
John Dvorak
Agregue otra versión entonces :)
Soham Chowdhury
1
El operador ** ya existía en FORTRAN en los años 50 y ALGOL tendría 1 carácter menos con la flecha hacia arriba
conocido como el
6

APL, 62

{1=3⌷⍵:2⌷+\⍵⋄0=2⌷⍵:(⍵[3]⌊3)⌷⍵[1],0,1⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1}⎕

{...}⎕: 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 índice min(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 3salidas 15.

Pero no puedo hacer que vuelva a aparecer. Quizás alguien más pueda hacerlo.

TwiNight
fuente
Ah, APL. Beats Python por simplicidad cualquier día. </sarcasm> ¿Cómo ejecuto esto?
Soham Chowdhury
2

Python, 83

(Basado en la respuesta de flornquake )

def h(x,y,n):r=n>2;exec"r=h(x,r,n-1);"*y*(n>1);return(x+y,r)[n>1]
print h(*input())

Muy lento para grandes resultados.

Para 2, 4, 4la salida es 65536.

Reinstalar a Mónica
fuente
"muy lento" es la razón por la cual mi solución de 86 caracteres se consideró mala.
John Dvorak
1
@ JanDvorak: ¿Por qué crees que se consideró malo? Soham Chowdhury acaba de decir que es lento y que debe agregar otra versión, no que reemplace su solución. (Pero tal vez no entendí eso.)
Restablece a Mónica el
Tienes razón; restaurado la versión corta. Ahora solo soy un char más largo que tú.
John Dvorak
@WolframH exactamente. Siempre es bueno tener versiones.
Soham Chowdhury
2

Python, 96 92

def h(x,y,n):r=1;exec(n>2)*y*"r=h(x,r,n-1);";return(r,(x+y,x*y)[n>1])[n<3]
print h(*input())

Entrada: 3, 3, 4
Salida:7625597484987

Acortado usando un par de ideas de @ WolframH .

flornquake
fuente
2

Golfscript, lento, 39 caracteres

 ~{\(.{3${[4$\2$4$.~}4$(*}{;;+}if])\;}.~

(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:

~{            #read the input and do (x y n f)
 \(.{         #(x y f n-1); if(n-1)
  3${         #(x y f n-1 c)
   4$\2$4$.~  #(x y f n-1 x c n-1 f); call
  }3$(*       #y-1 times
  {\;}4*
 }{           #else
  ;;+         #return (x+y)
 }if
}.~           #once

~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.

John Dvorak
fuente
"llama a la función consigo misma como primer argumento" - idea interesante para la recursión
aditsu se retiró porque SE es MAL
1

Smalltalk Squeak 4.x sabor muchos bytes!

Podría implementar una de las formas recursivas en Integer en 71 char

f:y n:n n=1or:[^(2to:y)inject:self into:[:x :i|self f:x n:n-1]].^self+y

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)

s self skipSeparators

Implemente este método de 20 caracteres en Comportamiento (para leer una instancia de un Stream)

<s^self readFrom:s s

Luego 28 caracteres en String (para crear un identificador de archivo)

f^FileDirectory default/self

Luego 59 caracteres en FileDirectory (para crear un readStream)

r^FileStream concreteStream readOnlyFileNamed:self fullName

Luego 33 caracteres en BlockClosure (para evaluarlo n veces)

*n^(1to:n)collect:[:i|self value]

Luego 63 caracteres en la matriz (evalúe el argumento con el receptor y los argumentos tomados de la matriz)

`s^self first perform:s asSymbol withArguments:self allButFirst

luego resuelva el problema evaluando este fragmento de 31 caracteres en cualquier lugar para leer desde el archivo llamado x

|s|s:='x'f r.[0class<s]*3`#f:n:

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:

doesNotUnderstand:m
    (m selector allSatisfy:[:c|c=$+])or:[^super doesNotUnderstand:m].
    self class compile:
        m selector,'y y=0or:[^(2to:y)inject:self into:[:x :i|self'
        ,m selector allButLast,'x]].^'
        ,(Character digitValue:()asBit)
        ,(m selector size-2min:1)hex last.
    thisContext sender restart

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 lastes 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

^m sendTo:self

Ahora implemente la utilidad de 28 caracteres en el Carácter (para repetirlo n veces en una Cadena)

*n^String new:n withAll:self

Luego evalúa esta expresión de 43 caracteres:

|i s|i:=0class.s:='x'f r.[i<s]*2`($+*(i<s))

Podemos acelerar con 10 caracteres más implementando en Integer:

++y^self*y

y en este caso también tenemos un código más corto porque podemos reemplazarlo ^',(m selector size-2min:1)hex lastcon^1'

Por un precio tan alto, el código funciona con el segundo entero = 0 :)

aka.nice
fuente
0

Groovy - 77

h={x,y,n->n<2?x+y:y<2?x:h(x,h(x,y-1,n),n-1)}
print h(args.collect{it as int})

Nota: requiere cantidades obscenas de pila (y tiempo) para argumentos no pequeños.

aditsu renunció porque SE es MALO
fuente
0

AXIOM Computer Algebra System, bytes 69

p(x,y,n)==(n<=1=>y+x^n;n=2=>y*x;n=3=>x^y;y<=0=>1;p(x,p(x,y-1,n),n-1))

prueba:

(2) -> p(1,1,1)
   (2)  2
                                                 Type: Expression Integer
                                   Time: 0.05 (IN) + 0.03 (OT) = 0.08 sec
(3) -> p(2,4,4)
   (3)  65536
                                                 Type: Expression Integer
                                                              Time: 0 sec
(4) -> p(3,3,4)
   (4)  7625597484987
                                                 Type: Expression Integer
                                                              Time: 0 sec

Esto eliminaría algo de recursión ... Posible cambio en x e y en algún retorno ... ¿hay otros valores de prueba?

RosLuP
fuente
0

APL (NARS), caracteres 61, bytes 122

{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}

prueba:

  h←{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}
  h 1 1 1
2
  h 2 4 4
65536
  h 3 4 4
∞
  h 3 3 4
7625597484987
RosLuP
fuente