Cree el programa o función más corto que encuentre el factorial de un entero no negativo.

El factorial, representado con !se define como tal

En inglés simple, el factorial de 0 es 1 y el factorial de n, donde n es mayor que 0 es n veces el factorial de uno menor que n.

Su código debe realizar entradas y salidas utilizando métodos estándar.

Requisitos:

• No utiliza ninguna biblioteca incorporada que pueda calcular el factorial (esto incluye cualquier forma de eval)
• Puede calcular factoriales para números hasta 125
• Puede calcular el factorial para el número 0 (igual a 1)
• Completa en menos de un minuto para números hasta 125

La presentación más corta gana, en caso de empate gana la respuesta con más votos en el momento.

Golfscript - 12 caracteres

{,1\{)*}/}:f

Comenzando con Golfscript - Factorial paso a paso

Aquí hay algo para las personas que están tratando de aprender golfscript. El requisito previo es una comprensión básica de golfscript y la capacidad de leer la documentación de golfscript.

Por eso queremos probar nuestra nueva herramienta golfscript . Siempre es bueno comenzar con algo simple, así que comenzamos con factorial. Aquí hay un intento inicial, basado en un pseudocódigo imperativo simple:

# pseudocode: f(n){c=1;while(n>1){c*=n;n--};return c}
{:n;1:c;{n 1>}{n c*:c;n 1-:n;}while c}:f

El espacio en blanco se usa muy raramente en golfscript. El truco más fácil para deshacerse del espacio en blanco es usar diferentes nombres de variables. Cada token se puede usar como una variable (ver la página de sintaxis ). Fichas útiles para utilizar como variables son caracteres especiales como |, &, ?- por lo general no cualquier cosa usada en otras partes del código. Estos siempre se analizan como tokens de un solo personaje. En contraste, las variables como nrequerirán un espacio para insertar un número en la pila después. Los números son esencialmente variables preinicializadas.

Como siempre, habrá declaraciones que podemos cambiar, sin afectar el resultado final. En golfscript, todo lo que se evalúa como verdadera, excepto 0, [], "", y {}(ver esta ). Aquí, podemos cambiar la condición de salida de bucle a simplemente {n}(bucleamos un tiempo adicional y terminamos cuando n = 0).

Al igual que con el golf en cualquier idioma, es útil conocer las funciones disponibles. Afortunadamente, la lista es muy corta para golfscript. Podemos cambiar 1-a (para salvar a otro personaje. En la actualidad, el código se ve así: (podríamos usarlo en 1lugar de |aquí si quisiéramos, lo que dejaría la inicialización).

{:n;1:|;{n}{n|*:|;n(:n;}while|}:f

Es importante usar bien la pila para obtener las soluciones más cortas (práctica práctica). En general, si los valores solo se usan en un pequeño segmento de código, puede que no sea necesario almacenarlos en variables. Al eliminar la variable de producto en ejecución y simplemente usar la pila, podemos guardar una gran cantidad de caracteres.

{:n;1{n}{n*n(:n;}while}:f

Aquí hay algo más en lo que pensar. Estamos eliminando la variable nde la pila al final del cuerpo del bucle, pero luego la empujamos inmediatamente después. De hecho, antes de que comience el ciclo, también lo eliminamos de la pila. En su lugar, deberíamos dejarlo en la pila, y podemos mantener en blanco la condición del bucle.

{1\:n{}{n*n(:n}while}:f

Quizás incluso podamos eliminar la variable por completo. Para hacer esto, necesitaremos mantener la variable en la pila en todo momento. Esto significa que necesitamos dos copias de la variable en la pila al final de la verificación de condición para que no la perdamos después de la verificación. Lo que significa que tendremos un redundante 0en la pila después de que finalice el ciclo, pero eso es fácil de solucionar.

¡Esto nos lleva a nuestra whilesolución de bucle óptima !

{1\{.}{.@*\(}while;}:f

Ahora todavía queremos hacer esto más corto. El objetivo obvio debería ser la palabra while. Mirando la documentación, hay dos alternativas viables: desplegar y hacer . Cuando tenga la opción de elegir diferentes rutas, intente sopesar los beneficios de ambas. Desplegar es 'casi un bucle while', por lo que, como estimación, reduciremos el carácter whilede 5 en 4 /. En cuanto a do, cortamos whileen 3 caracteres y fusionamos los dos bloques, lo que podría salvar a otro personaje o dos.

En realidad, hay un gran inconveniente al usar un dobucle. Dado que la verificación de la condición se realiza después de que el cuerpo se ejecuta una vez, el valor de 0será incorrecto, por lo que es posible que necesitemos una instrucción if. Te diré ahora que el despliegue es más corto ( doal final se proporcionan algunas soluciones ). Siga adelante y pruébelo, el código que ya tenemos requiere cambios mínimos.

{1\{}{.@*\(}/;}:f

¡Excelente! Nuestra solución ahora es súper corta y hemos terminado aquí, ¿verdad? No. Esto tiene 17 caracteres y J tiene 12 caracteres. ¡Nunca admitas la derrota!

Ahora estás pensando con ... recursividad

Usar recursividad significa que debemos usar una estructura de ramificación. Desafortunadamente, pero como el factorial se puede expresar de manera tan breve y recursiva, parece una alternativa viable a la iteración.

# pseudocode: f(n){return n==0?n*f(n-1):1}
{:n{n.(f*}1if}:f # taking advantage of the tokeniser

Bueno, eso fue fácil: si hubiéramos intentado la recursividad antes, ¡tal vez ni siquiera hubiéramos visto usar un whilebucle! Aún así, solo tenemos 16 caracteres.

Matrices

Las matrices generalmente se crean de dos maneras: usando los caracteres [y ], o con la ,función. Si se ejecuta con un número entero en la parte superior de la pila, ,devuelve una matriz de esa longitud con arr [i] = i.

Para iterar sobre matrices, tenemos tres opciones:

1. {block}/: empujar, bloquear, empujar, bloquear, ...
2. {block}%: [push, block, push, block, ...] (esto tiene algunos matices, por ejemplo, los valores intermedios se eliminan de la pila antes de cada inserción)
3. {block}*: empujar, empujar, bloquear, empujar, bloquear, ...

La documentación de golfscript tiene un ejemplo de uso {+}*para sumar el contenido de una matriz. Esto sugiere que podemos usar {*}*para obtener el producto de una matriz.

{,{*}*}:f

Desafortunadamente, no es tan simple. Todos los elementos están separados por uno (en [0 1 2]lugar de [1 2 3]). Podemos usar {)}%para rectificar este problema.

{,{)}%{*}*}:f

Pues no del todo. Esto no maneja cero correctamente. Podemos calcular (n + 1)! / (N + 1) para rectificar esto, aunque esto cuesta demasiado.

{).,{)}%{*}*\/}:f

También podemos tratar de manejar n = 0 en el mismo depósito que n = 1. Esto es realmente extremadamente corto de hacer, prueba y trabaja lo más corto que puedas.

No tan buena es la clasificación, a los 7 caracteres: [1\]$1=. Tenga en cuenta que esta técnica de clasificación tiene propósitos útiles, como imponer límites a un número (por ejemplo, `[[\ \ 100] $ 1 =)
Aquí está el ganador, con solo 3 caracteres:.! +

Si queremos tener el incremento y la multiplicación en el mismo bloque, debemos iterar sobre cada elemento de la matriz. Como no estamos construyendo una matriz, esto significa que deberíamos estar usando {)*}/, lo que nos lleva a la implementación de factorial más corta de golfscript. Con 12 caracteres de largo, esto está relacionado con J!

{,1\{)*}/}:f

Soluciones de bonificación

Comenzando con una ifsolución sencilla para un dobucle:

{.{1\{.@*\(.}do;}{)}if}:f

Podemos exprimir un par extra de esto. Un poco complicado, por lo que tendrás que convencerte de que estos funcionan. Asegúrate de entender todo esto.

{1\.!!{{.@*\(.}do}*+}:f
{.!{1\{.@*\(.}do}or+}:f
{.{1\{.@*\(.}do}1if+}:f

Una mejor alternativa es calcular (n + 1)! / (N + 1), lo que elimina la necesidad de una ifestructura.

{).1\{.@*\(.}do;\/}:f

Pero la dosolución más corta aquí toma algunos caracteres para asignar 0 a 1, y todo lo demás para sí mismo, por lo que no necesitamos ninguna ramificación. Este tipo de optimización es extremadamente fácil de perder.

{.!+1\{.@*\(.}do;}:f

Para cualquier persona interesada, aquí se proporcionan algunas soluciones recursivas alternativas con la misma longitud que la anterior:

{.!{.)f*0}or+}:f
{.{.)f*0}1if+}:f
{.{.(f*}{)}if}:f

* nota: en realidad no he probado muchas de las piezas de código en esta publicación, así que siéntase libre de informar si hay errores.

Haskell, 17

f n=product[1..n]

Python - 27

Así de simple:

f=lambda x:0**x or x*f(x-1)

APL (4)

×/∘⍳

Funciona como una función anónima:

    ×/∘⍳ 5
120

Si quieres darle un nombre, 6 caracteres:

f←×/∘⍳

J (12)

Una definición estándar en J:

f=:*/@:>:@i.

¡Menos de 1 segundo por 125!

P.ej:

 f 0
 1
 f 5
 120
  f 125x
 1882677176888926099743767702491600857595403
 6487149242588759823150835315633161359886688
 2932889495923133646405445930057740630161919
 3413805978188834575585470555243263755650071
 31770880000000000000000000000000000000

Golfscript - 13 caracteres (SYM)

define la función !

{),()\{*}/}:!             # happy robot version \{*}/ 

versión alternativa de 13 caracteres

{),()+{*}*}:! 

la versión completa del programa es de 10 caracteres

~),()+{*}*

Las cajas de prueba toman menos de 1/10 de segundo:

entrada:

0!

salida

1

entrada

125!

salida

188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000

Perl 6: 13 caracteres

$f={[*]1..$_}

[*]es igual que Haskell product, y 1..$_es un conteo desde 1 hasta $_, el argumento.

Matlab, 15

f=@(x)prod(1:x)

Casos de prueba

>> f(0)
ans =
     1
>> f(4)
ans =
    24
>> tic,f(125),toc
ans =
  1.8827e+209
Elapsed time is 0.000380 seconds.

Python, 28 bytes

f=lambda x:x/~x+1or x*f(x-1)

(basado en la solución de Alexandru)

MATL , 2 bytes

:p

Explicado:

:    % generate list 1,2,3,...,i, where i is an implicit input
p    % calculate the product of of all the list entries (works on an empty list too)

Pruébalo en línea!

Ruby - 21 caracteres

f=->n{n>1?n*f[n-1]:1}

Prueba

irb(main):009:0> f=->n{n>1?n*f[n-1]:1}
=> #<Proc:0x25a6d48@(irb):9 (lambda)>
irb(main):010:0> f[125]
=> 18826771768889260997437677024916008575954036487149242588759823150835315633161
35988668829328894959231336464054459300577406301619193413805978188834575585470555
24326375565007131770880000000000000000000000000000000

Java, 85 caracteres

BigInteger f(int n){return n<2?BigInteger.ONE:new BigInteger(""+n).multiply(f(n-1));}

PostScript, 26 caracteres

/f{1 exch -1 1{mul}for}def

Ejemplo:

GS> 0 f =
1
GS> 1 f =
1
GS> 8 f =
40320

La función en sí solo toma 21 caracteres; el resto es vincularlo a una variable. Para guardar un byte, también se puede vincular a un dígito, así:

GS> 0{1 exch -1 1{mul}for}def
GS> 8 0 load exec =
40320

JavaScript, 25

function f(n)!n||n*f(n-1)

CoffeeScript, 19

f=(n)->!n||n*f(n-1)

Devuelve trueen el caso de n = 0, pero JavaScript lo obligará a escribir de todos modos.

Ruby - 30 29 caracteres

def f(n)(1..n).inject 1,:*end

Prueba

f(0) -> 1
f(5) -> 120

F #: 26 caracteres

No hay una función de producto incorporada en F #, pero puede hacer una con un pliegue

let f n=Seq.fold(*)1{1..n}

C #, 20 o 39 caracteres según su punto de vista

Como método de instancia tradicional (39 caracteres; probado aquí ):

double f(int x){return 2>x?1:x*f(x-1);}

Como una expresión lambda (20 caracteres, pero ver descargo de responsabilidad; probado aquí ):

f=x=>2>x?1:x*f(x-1);

Tenemos que usar doubleporque 125! == 1.88 * 10 ²⁰⁹ , que es mucho más alto que ulong.MaxValue.

Descargo de responsabilidad sobre el recuento de caracteres de la versión lambda:

Si recurres en un C # lambda, obviamente tienes que almacenar el lambda en una variable con nombre para que pueda llamarse a sí mismo. Pero a diferencia de (p. Ej.) JavaScript, una lambda autorreferenciada debe haberse declarado e inicializado en una línea anterior. No puede llamar a la función en la misma declaración en la que declara y / o inicializa la variable.

En otras palabras, esto no funciona :

Func<int,double> f=x=>2>x?1:x*f(x-1); //Error: Use of unassigned local variable 'f'

Pero esto hace :

Func<int,double> f=null;            
f=x=>2>x?1:x*f(x-1);  

No hay una buena razón para esta restricción, ya fque nunca se puede desasignar en el momento en que se ejecuta. La necesidad de la Func<int,double> f=null;línea es una peculiaridad de C #. Si eso hace justo ignorarlo en el recuento de caracteres depende del lector.

CoffeeScript, 21 19 caracteres de verdad

f=(x)->+!x||x*f x-1

Probado aquí: http://jsfiddle.net/0xjdm971/

Brachylog , 7 6 bytes

Al hacer un rango y multiplicarlo

-1 tanques de bytes a ovs que tienen la idea de usar la función max ()

;1⌉⟦₁×

Explicación

;1          --  If n<1, use n=1 instead (zero case)
  ⟦₁        --      Construct the range [1,n]
    ×       --      return the product of said range

Pruébalo en línea!

Brachylog , 10 9 bytes

recursividad

≤1|-₁↰;?×

Explicación

            --f(n):
≤1          --  if n ≤ 1: return 1
|           --  else:
 -₁↰        --      f(n-1)
    ;?×     --            *n

Pruébalo en línea!

C (39 caracteres)

double f(int n){return n<2?1:n*f(n-1);}

D: 45 caracteres

T f(T)(T n){return n < 2 ? 1 : n * f(n - 1);}

Más legible:

T f(T)(T n)
{
    return n < 2 ? 1 : n * f(n - 1);
}

Una versión más fresca (aunque más larga) es la plantilla que lo hace todo en tiempo de compilación ( 64 caracteres ):

template F(int n){static if(n<2)enum F=1;else enum F=n*F!(n-1);}

Más legible:

template F(int n)
{
    static if(n < 2)
        enum F = 1;
    else
        enum F = n * F!(n - 1);
}

Sin embargo, las plantillas homónimas son bastante detalladas, por lo que realmente no puede usarlas muy bien en el código de golf. D ya es lo suficientemente detallado en términos de recuento de caracteres para ser bastante pobre para el golf de código (aunque en realidad funciona muy bien para reducir el tamaño general del programa para programas más grandes). Sin embargo, es mi lenguaje favorito, así que me imagino que también podría intentar ver qué tan bien puedo lograrlo en el golf de código, incluso si los gustos de GolfScript están obligados a crearlo.

PowerShell - 36

Ingenuo:

filter f{if($_){$_*(--$_|f}else{1}}

Prueba:

> 0,5,125|f
1
120
1,88267717688893E+209

Scala, 39 caracteres

def f(x:BigInt)=(BigInt(1)to x).product

La mayoría de los caracteres se aseguran de que BigIntse usen s para cumplir con el requisito de valores de hasta 125.

Javascript, ES6 17

f=n=>n?n*f(n-1):1

ES6:

• Función de flecha

PowerShell, 42 bytes

(guardado 2 caracteres usando filtro en lugar de función )

filter f($x){if(!$x){1}else{$x*(f($x-1))}}

Salida:

PS C:\> f 0
1
PS C:\> f 5
120
PS C:\> f 1
1
PS C:\> f 125
1.88267717688893E+209

Raqueta (esquema) 40 35 29 bytes

Calcula 0! ser 1, y calcula 125! en 0 segundos según el temporizador. Enfoque recursivo regular

(define(f n)(if(= n 0)1(* n(f(- n 1)))))

Nueva versión para vencer el lisp común: multiplica todos los elementos de una lista (igual que esa solución de Haskell)

(λ(n)(apply *(build-list n add1)))

Versión más nueva para vencer a la otra solución de esquema y matemática a la otra solución de raqueta usando foldl en lugar de aplicar y usando rango en lugar de buildlist

(λ(n)(foldl * n(range 1 n)))

Mornington Crescent , 1827 1698 caracteres

Hoy tuve ganas de aprender un nuevo idioma, y ​​esto es en lo que llegué ... (¿Por qué me hago esto a mí mismo?) Esta entrada no ganará ningún premio, pero supera las 0 respuestas hasta ahora usando el ¡mismo lenguaje!

Take Northern Line to Bank
Take Central Line to Holborn
Take Piccadilly Line to Heathrow Terminals 1, 2, 3
Take Piccadilly Line to Acton Town
Take District Line to Acton Town
Take District Line to Parsons Green
Take District Line to Bank
Take District Line to Parsons Green
Take District Line to Acton Town
Take District Line to Hammersmith
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Acton Town
Take Piccadilly Line to Bounds Green
Take Piccadilly Line to Acton Town
Take Piccadilly Line to Bounds Green
Take Piccadilly Line to Acton Town
Take District Line to Acton Town
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Parsons Green
Take District Line to Notting Hill Gate
Take Circle Line to Notting Hill Gate
Take Circle Line to Bank
Take Circle Line to Temple
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Bank
Take District Line to Upney
Take District Line to Upminster
Take District Line to Hammersmith
Take District Line to Upminster
Take District Line to Upney
Take District Line to Bank
Take Circle Line to Embankment
Take Circle Line to Embankment
Take Northern Line to Angel
Take Northern Line to Moorgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Moorgate
Take Circle Line to Moorgate
Take Northern Line to Mornington Crescent

Pruébalo en línea!

Cualquiera que haya viajado por Londres lo entenderá al instante, por supuesto, así que estoy seguro de que no necesito dar una explicación completa.

La mayor parte del trabajo al principio está en manejar el caso 0. Después de inicializar el producto en 1, puedo usarlo para calcular max (input, 1) para obtener la nueva entrada, ¡aprovechando el hecho de que 0! = 1! Entonces el ciclo principal puede comenzar.

(EDITAR: Se han guardado un montón de viajes quitando el 1 de "Heathrow Terminals 1, 2, 3" en lugar de generarlo dividiendo 7 (Sisters) por sí mismo. También utilizo un método más barato para generar el -1 en el siguiente paso.)

Disminuir es costoso en Mornington Crescent (aunque menos costoso que el Tubo en sí). Para hacer las cosas más eficientes, genero un -1 tomando el NOT de un 0 analizado y lo guardo en Hammersmith durante gran parte del ciclo.

Befunge - 2x20 = 40 caracteres

0\:#v_# 1#<\$v *\<
    >:1-:#^_$>\:#^_$

Esta es una función porque es un bloque de código independiente que no utiliza el entorno envolvente. Debe colocar el argumento en la parte superior de la pila y luego ingresar desde la parte superior izquierda hacia la derecha, la función saldrá desde la parte inferior derecha hacia la derecha con el resultado en la parte superior de la pila.

Por ejemplo, para calcular el factorial de 125

555**   0\:#v_# 1#<\$v *\<
            >:1-:#^_$>\:#^_$    .@

Prueba 0

0   0\:#v_# 1#<\$v *\<
        >:1-:#^_$>\:#^_$    .@

J - 6 caracteres

*/>:i.

¿Esto cuenta? Sé que es muy similar al ejemplo J anterior, pero es un poco más corto :)

Soy un principiante con J, pero hasta ahora es muy divertido.

En C (23 caracteres)

Esto abusa de la "característica" GCC que hace que la última asignación cuente como una devolución si no se especifica ninguna devolución.

f(a){a=a>0?f(a-1)*a:1;}

En C propia, 28 caracteres

f(a){return a>0?f(a-1)*a:1;}

Kona ( 11 6)

*/1.+!

K funciona de derecha a izquierda (en su mayor parte), por lo que enumeramos x(hacemos una lista / matriz de números de 0a x-1), le agregamos 1(los rangos de lista 0a x), luego multiplicamos todos los números. Si no fuera un requisito para calcular 125!, podría ahorrar 1 byte más eliminando al .lado del 1. En cualquier caso, 125! se calcula en meros milisegundos:

  */1.+!125.
1.882677e+209