Utwórz najkrótszy program lub funkcję, która znajdzie silnię nieujemnej liczby całkowitej.

Silnia reprezentowana przez !jest zdefiniowana jako taka

W prostym języku angielskim silnia 0 wynosi 1, a silnia n, gdzie n jest większa od 0, jest n razy silnia o jeden mniejsza niż n.

Twój kod powinien wykonywać dane wejściowe i wyjściowe przy użyciu standardowych metod.

Wymagania:

• Nie używa żadnych wbudowanych bibliotek, które mogą obliczyć silnię (w tym dowolną formę eval)
• Potrafi obliczyć silni dla liczb do 125
• Potrafi obliczyć silnię dla liczby 0 (równej 1)
• Wypełnia w niecałą minutę dla numerów do 125

Najkrótsze zgłoszenie wygrywa, w przypadku remisu wygrywa odpowiedź z największą liczbą głosów w danym momencie.

Golfscript - 12 znaków

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

Pierwsze kroki z Golfscript - Factorial krok po kroku

Oto coś dla ludzi, którzy próbują nauczyć się gry w golfa. Warunkiem jest podstawowa znajomość gry w golfa i umiejętność czytania dokumentacji gry w golfa.

Dlatego chcemy wypróbować nasze nowe narzędzie do gry w golfa . Zawsze dobrze jest zacząć od czegoś prostego, więc zaczynamy od silni. Oto wstępna próba, oparta na prostym pseudokodzie imperatywnym:

# 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

Biała spacja jest bardzo rzadko używana w golfscript. Najłatwiejszym sposobem na pozbycie się białych znaków jest użycie różnych nazw zmiennych. Każdy token może być użyty jako zmienna (patrz strona składni ). Przydatne żetonów do wykorzystania jako zmienne są znaki specjalne, takie jak |, &, ?- generalnie nic nie wykorzystane gdzie indziej w kodzie. Są one zawsze analizowane jako tokeny jednoznakowe. Dla kontrastu, zmienne takie nbędą wymagały spacji do wypchnięcia liczby do stosu po. Liczby są zasadniczo zmiennymi wstępnie zainicjowanymi.

Jak zawsze pojawią się oświadczenia, które możemy zmienić bez wpływu na wynik końcowy. W golfscript, wszystko jest true chyba 0, [],"" , i {}(zobacz to ). Tutaj możemy zmienić warunek wyjścia pętli na prosty {n}(zapętlamy dodatkowy czas i kończymy, gdy n = 0).

Podobnie jak w golfie w dowolnym języku, pomaga poznać dostępne funkcje. Na szczęście lista jest bardzo krótka jak na golfa. Możemy zmienić 1-, aby (zapisać inny charakter. Obecnie kod wygląda następująco: ( gdybyśmy chcieli, moglibyśmy użyć 1zamiast |tutaj, co spowodowałoby usunięcie inicjalizacji).

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

Ważne jest, aby dobrze wykorzystać stos, aby uzyskać najkrótsze rozwiązania (ćwiczyć praktykę). Zasadniczo, jeśli wartości są używane tylko w małym segmencie kodu, może nie być konieczne przechowywanie ich w zmiennych. Usuwając działającą zmienną produktu i po prostu używając stosu, możemy zapisać sporo znaków.

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

Oto coś innego do przemyślenia. Usuwamy zmienną nze stosu na końcu korpusu pętli, ale następnie wypychamy ją natychmiast po. W rzeczywistości przed rozpoczęciem pętli usuwamy ją również ze stosu. Zamiast tego powinniśmy zostawić go na stosie i możemy pozostawić warunek pętli pusty.

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

Może możemy nawet całkowicie wyeliminować zmienną. Aby to zrobić, będziemy musieli cały czas przechowywać zmienną na stosie. Oznacza to, że potrzebujemy dwóch kopii zmiennej na stosie na końcu sprawdzania warunku, abyśmy nie stracili go po sprawdzeniu. Co oznacza, że ​​będziemy mieli zbędne0 po zakończeniu pętli stos, ale łatwo to naprawić.

To prowadzi nas do naszego optymalnego whilerozwiązania pętli!

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

Teraz nadal chcemy to skrócić. Oczywistym celem powinno być słowo while. Patrząc na dokumentację, istnieją dwie realne alternatywy - rozwinąć i zrobić . Gdy masz do wyboru różne trasy, spróbuj rozważyć zalety obu. Unfold to „prawie czasowa pętla”, więc w przybliżeniu zmniejszymy 5 znaków whileo 4 w /. Jeśli chodzi o to do, przecinamy whileo 3 znaki i łączymy dwa bloki, co może uratować kolejny znak lub dwa.

Korzystanie z dopętli ma dużą wadę . Ponieważ sprawdzanie warunku jest wykonywane po jednokrotnym wykonaniu treści, wartość parametru 0będzie niepoprawna, więc może być konieczne użycie instrukcji if. Powiem wam teraz, że rozwinięcie jest krótsze (niektóre rozwiązania dosą podane na końcu). Śmiało, spróbuj, kod, który już mamy, wymaga minimalnych zmian.

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

Wspaniały! Nasze rozwiązanie jest teraz super krótkie i skończyliśmy tutaj, prawda? Nie. To jest 17 znaków, a J ma 12 znaków. Nigdy nie przyznawaj się do porażki!

Teraz myślisz z ... rekurencją

Korzystanie z rekurencji oznacza, że musimy użyć rozgałęzionej struktury. Niestety, ale ponieważ czynnik można tak zwięźle wyrazić rekurencyjnie, wydaje się to realną alternatywą dla iteracji.

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

Cóż, to było łatwe - gdybyśmy wcześniej spróbowali rekurencji, moglibyśmy nawet nie spojrzeć na whilepętlę! Nadal mamy tylko 16 znaków.

Tablice

Tablice są zazwyczaj tworzone na dwa sposoby - za pomocą [i ]znaków, lub z ,funkcji. Jeśli zostanie wykonany z liczbą całkowitą na górze stosu, ,zwraca tablicę o tej długości z arr [i] = i.

Do iteracji po tablicach mamy trzy opcje:

1. {block}/: push, block, push, block, ...
2. {block}%: [push, block, push, block, ...] (ma to pewne niuanse, np. wartości pośrednie są usuwane ze stosu przed każdym push)
3. {block}*: push, push, block, push, block, ...

Dokumentacja golfscript zawiera przykład użycia {+}*do zsumowania zawartości tablicy. Sugeruje to, że możemy użyć, {*}*aby uzyskać iloczyn macierzy.

{,{*}*}:f

Niestety nie jest to takie proste. Wszystkie elementy są wyłączone o jeden ( [0 1 2]zamiast [1 2 3]). Możemy użyć {)}%do rozwiązania tego problemu.

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

Cóż, niezupełnie. To nie obsługuje poprawnie zera. Możemy obliczyć (n + 1)! / (N + 1), aby to naprawić, chociaż kosztuje to zdecydowanie za dużo.

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

Możemy również spróbować obsłużyć n = 0 w tym samym segmencie, co n = 1. Jest to naprawdę bardzo krótkie do zrobienia, spróbuj wypracować najkrótsze, jakie możesz.

Nie jest tak dobry sortowania, po 7 znaków: [1\]$1=. Pamiętaj, że ta technika sortowania ma użyteczne cele, takie jak narzucanie granic na liczbę (np. „[0 \ 100] $ 1 =)
Oto zwycięzca, posiadający tylko 3 znaki:.! +

Jeśli chcemy, aby przyrost i mnożenie występowały w tym samym bloku, powinniśmy iterować każdy element tablicy. Ponieważ nie budujemy tablicy, oznacza to, że powinniśmy używać {)*}/, co prowadzi nas do najkrótszej implementacji silnia golfowego! Przy długości 12 znaków jest to powiązane z literą J!

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

Rozwiązania premiowe

Zaczynając od prostego ifrozwiązania dla dopętli:

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

Możemy wycisnąć z tego kilka dodatkowych. Trochę skomplikowane, więc musisz się przekonać, że te działają. Upewnij się, że rozumiesz je wszystkie.

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

Lepszą alternatywą jest obliczenie (n + 1)! / (N + 1), co eliminuje potrzebę ifbudowy.

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

Ale najkrótsze dorozwiązanie wymaga kilku znaków, aby zamapować 0 na 1 i wszystko inne na siebie - więc nie potrzebujemy rozgałęzień. Tego rodzaju optymalizacji bardzo łatwo przeoczyć.

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

Dla wszystkich zainteresowanych podajemy tutaj kilka alternatywnych rozwiązań rekurencyjnych o takiej samej długości jak powyżej:

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

* Uwaga: W rzeczywistości nie testowałem wielu fragmentów kodu w tym poście, więc zachęcamy do informowania o ewentualnych błędach.

Haskell, 17

f n=product[1..n]

Python - 27

Po prostu:

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

APL (4)

×/∘⍳

Działa jako funkcja anonimowa:

    ×/∘⍳ 5
120

Jeśli chcesz nadać mu nazwę, 6 znaków:

f←×/∘⍳

J (12)

Standardowa definicja w J:

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

Mniej niż 1 sekunda na 125!

Na przykład:

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

Golfscript - 13 znaków (SYM)

definiuje funkcję !

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

alternatywna wersja 13 znaków

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

cała wersja programu to 10 znaków

~),()+{*}*

testy trwają krócej niż 1/10 sekundy:

Wejście:

0!

wynik

1

Wejście

125!

wynik

188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000

Perl 6: 13 znaków

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

[*]jest taki sam jak Haskell producti 1..$_jest liczeniem od 1 do $_argumentu.

Matlab, 15

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

Przypadki testowe

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

Python, 28 bajtów

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

(w oparciu o rozwiązanie Alexandru)

MATL , 2 bajty

:p

Wyjaśniono:

:    % 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)

Wypróbuj online!

Rubin - 21 znaków

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

Test

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 znaków

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

PostScript, 26 znaków

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

Przykład:

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

Sama funkcja zajmuje tylko 21 znaków; reszta polega na powiązaniu go ze zmienną. Aby zapisać bajt, można również powiązać go z cyfrą, w następujący sposób:

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)

Zwraca truew przypadku n = 0, ale JavaScript i tak wymusi to na 1.

Rubin - 30 29 znaków

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

Test

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

F #: 26 znaków

W języku F # nie ma wbudowanej funkcji produktu, ale możesz zrobić ją składając

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

C #, 20 lub 39 znaków w zależności od twojego punktu widzenia

Jako tradycyjna metoda instancji (39 znaków; przetestowano tutaj ):

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

Jako wyrażenie lambda (20 znaków, ale patrz wyłączenie odpowiedzialności; przetestowano tutaj ):

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

Musimy użyć, doubleponieważ 125! == 1,88 * 10 ²⁰⁹ , czyli znacznie więcej niż ulong.MaxValue.

Oświadczenie dotyczące liczby znaków wersji lambda:

Jeśli rekurencja odbywa się w C # lambda, oczywiście musisz przechowywać lambda w nazwie zmiennej, aby mogła się wywoływać. Ale w przeciwieństwie do (np.) JavaScript, samookreślająca się lambda musiała zostać zadeklarowana i zainicjowana w poprzednim wierszu. Nie możesz wywołać funkcji w tej samej instrukcji, w której deklarujesz i / lub inicjujesz zmienną.

Innymi słowy, to nie działa :

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

Ale to powoduje :

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

Od tego czasu nie ma dobrego powodu do tego ograniczenia f nigdy nie można go przypisać w momencie jego uruchomienia. Konieczność Func<int,double> f=null;linii to dziwactwo C #. To, czy to sprawiedliwe, aby zignorować to w liczbie znaków, zależy od czytelnika.

CoffeeScript, 21 19 znaków naprawdę

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

Testowany tutaj: http://jsfiddle.net/0xjdm971/

Brachylog , 7 6 bajtów

Przez utworzenie zakresu i pomnożenie go

-1 bajtowe zbiorniki na jaja mające pomysł na użycie funkcji max ()

;1⌉⟦₁×

Wyjaśnienie

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

Wypróbuj online!

Brachylog , 10 9 bajtów

rekurencja

≤1|-₁↰;?×

Wyjaśnienie

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

Wypróbuj online!

C (39 znaków)

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

D: 45 znaków

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

Bardziej czytelnie:

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

Cooler (choć dłuższa wersja) to szablonowy, który robi to wszystko w czasie kompilacji ( 64 znaki ):

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

Bardziej czytelnie:

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

Tytułowe szablony są jednak dość szczegółowe, więc nie można ich tak naprawdę używać w golfie kodowym. D jest już wystarczająco gadatliwy, jeśli chodzi o liczbę znaków, by być raczej kiepskim graczem w golfa kodowego (choć tak naprawdę jest) naprawdę dobrze radzi sobie z redukowaniem ogólnego rozmiaru programu w przypadku większych programów). Jest to jednak mój ulubiony język, więc sądzę, że równie dobrze mogę spróbować i przekonać się, jak dobrze radzę sobie z golfem kodowym, nawet jeśli pokochają go GolfScript.

PowerShell - 36

Naiwny:

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

Test:

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

Scala, 39 znaków

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

Większość znaków zapewnia, że BigInts są używane, więc spełniony jest warunek dla wartości do 125.

JavaScript, ES6 17

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

ES6:

• Funkcja strzałki

PowerShell, 42 bajty

(zapisane 2 znaki przy użyciu filtru zamiast funkcji )

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

Wynik:

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

Rakieta (schemat) 40 35 29 bajtów

Oblicza 0! być 1 i oblicza 125! w 0 sekund zgodnie z zegarem. Regularne podejście rekurencyjne

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

Nowa wersja do pokonania wspólnego lisp: zwielokrotnia wszystkie elementy listy (tak samo jak rozwiązanie Haskell)

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

Nowsza wersja, aby pokonać inne rozwiązanie schematu i matematykę innego rozwiązania rakietowego, używając foldl zamiast stosować i używając range zamiast buildlist

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

Mornington Crescent , 1827 1698 znaków

Chciałem dzisiaj nauczyć się nowego języka i na tym właśnie wylądowałem ... (Dlaczego robię to dla siebie?) Ten wpis nie zdobędzie żadnych nagród, ale jak dotąd pokonuje wszystkie 0 innych odpowiedzi za pomocą taki sam język!

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

Wypróbuj online!

Każdy, kto podróżował po Londynie, zrozumie to natychmiast, więc jestem pewien, że nie muszę udzielać pełnego wyjaśnienia.

Większość pracy na początku dotyczy obsługi przypadku 0. Po zainicjowaniu produktu na 1, mogę go użyć do obliczenia maksimum (wkład, 1), aby uzyskać nowy wkład, wykorzystując fakt, że 0! = 1! Następnie można rozpocząć główną pętlę.

(EDYCJA: Cała garść podróży została uratowana przez usunięcie 1 z „Heathrow Terminals 1, 2, 3” zamiast generowania przez podzielenie 7 (Sióstr) sama. Korzystam też z tańszej metody generowania -1 w Następny krok.)

Zmniejszanie jest kosztowne w Mornington Crescent (choć tańsze niż sama Tube). Aby uczynić rzeczy bardziej wydajnymi, generuję -1, biorąc NOT z przeanalizowanego 0 i przechowuję to w Hammersmith przez większą część pętli.

Befunge - 2x20 = 40 znaków

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

Jest to funkcja polegająca na tym, że jest to samodzielny blok kodu, który nie wykorzystuje zawijania. Musisz umieścić argument na górze stosu, a następnie wejść od lewego górnego rogu w prawo, funkcja zakończy się w prawym dolnym rogu, przechodząc w prawo z wynikiem na górze stosu.

Np. Obliczyć silnię 125

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

Testowanie 0

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

J - 6 znaków

*/>:i.

Czy to się liczy? Wiem, że jest bardzo podobny do wcześniejszego przykładu J, ale jest trochę krótszy :)

Jestem początkującym w J, ale jak dotąd dużo zabawy!

W C (23 znaki)

To narusza „funkcję” GCC, która powoduje, że ostatnie przypisanie jest liczone jako zwrot, jeśli nie określono zwrotu.

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

W prawidłowym C, 28 znaków

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

Kona ( 11 6)

*/1.+!

K działa od prawej do lewej (w przeważającej części), więc wyliczamy x(tworzymy listę / tablicę liczb od 0do x-1), dodajemy 1do niej (zakresy list 0do x), a następnie mnożymy wszystkie liczby razem. Gdyby obliczenie nie było wymogiem 125!, mógłbym zaoszczędzić 1 bajt, eliminując .obok 1. W każdym razie 125! jest obliczany w zaledwie milisekundach:

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