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.
code-golf
arithmetic
factorial
Kevin Brown
źródło
źródło
Odpowiedzi:
Golfscript - 12 znaków
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:
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 takien
bę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ć1
zamiast|
tutaj, co spowodowałoby usunięcie inicjalizacji).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.
Oto coś innego do przemyślenia. Usuwamy zmienną
n
ze 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.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ędne
0
po zakończeniu pętli stos, ale łatwo to naprawić.To prowadzi nas do naszego optymalnego
while
rozwiązania pętli!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ówwhile
o 4 w/
. Jeśli chodzi o todo
, przecinamywhile
o 3 znaki i łączymy dwa bloki, co może uratować kolejny znak lub dwa.Korzystanie z
do
pętli ma dużą wadę . Ponieważ sprawdzanie warunku jest wykonywane po jednokrotnym wykonaniu treści, wartość parametru0
będzie niepoprawna, więc może być konieczne użycie instrukcji if. Powiem wam teraz, że rozwinięcie jest krótsze (niektóre rozwiązaniado
są podane na końcu). Śmiało, spróbuj, kod, który już mamy, wymaga minimalnych zmian.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.
Cóż, to było łatwe - gdybyśmy wcześniej spróbowali rekurencji, moglibyśmy nawet nie spojrzeć na
while
pę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:
{block}/
: push, block, push, block, ...{block}%
: [push, block, push, block, ...] (ma to pewne niuanse, np. wartości pośrednie są usuwane ze stosu przed każdym push){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.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.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.
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.
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!Rozwiązania premiowe
Zaczynając od prostego
if
rozwiązania dlado
pętli:Możemy wycisnąć z tego kilka dodatkowych. Trochę skomplikowane, więc musisz się przekonać, że te działają. Upewnij się, że rozumiesz je wszystkie.
Lepszą alternatywą jest obliczenie (n + 1)! / (N + 1), co eliminuje potrzebę
if
budowy.Ale najkrótsze
do
rozwią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ć.Dla wszystkich zainteresowanych podajemy tutaj kilka alternatywnych rozwiązań rekurencyjnych o takiej samej długości jak powyżej:
* 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.
źródło
Haskell, 17
źródło
[1..0] ==> []
orazproduct [] ==> 1
f 0=1;f n=n*f$n-1
ma również 17 znaków.product
i, powiedzmy,(*)
albo(-)
„może obliczyć silnia”, a wszystkie one są zdefiniowane przez Prelude. Dlaczego jeden byłby fajny, a drugi nie?Python - 27
Po prostu:
źródło
0**x
.math.factorial
? To nie jest wbudowane, prawda?0**x
?APL (4)
Działa jako funkcja anonimowa:
Jeśli chcesz nadać mu nazwę, 6 znaków:
źródło
⍳
tworzy wektor indeksu, tzn .⍳5
Jest1 2 3 4 5
.×
jest (oczywiście) zwielokrotnia,/
zmniejsza i∘
jest składnikiem funkcji. Tak więc×/∘⍳
jest funkcją, która przyjmuje argumentx
i daje iloczyn liczb[1..x]
.J (12)
Standardowa definicja w J:
Mniej niż 1 sekunda na 125!
Na przykład:
źródło
([:*/1+i.)
dla 10 punktów, a nawet 8, ponieważ nawiasy są potrzebne tylko do wywołania funkcji, a nie do definicji.f 125x
co robix
? Czy to specjalny rodzaj liczby?Golfscript - 13 znaków (SYM)
definiuje funkcję
!
alternatywna wersja 13 znaków
cała wersja programu to 10 znaków
testy trwają krócej niż 1/10 sekundy:
Wejście:
wynik
Wejście
wynik
źródło
Perl 6: 13 znaków
[*]
jest taki sam jak Haskellproduct
i1..$_
jest liczeniem od 1 do$_
argumentu.źródło
[*]
(komunikat o błędzie „Dwa terminy z rzędu”).Matlab, 15
Przypadki testowe
źródło
Python, 28 bajtów
(w oparciu o rozwiązanie Alexandru)
źródło
MATL , 2 bajty
Wyjaśniono:
Wypróbuj online!
źródło
Rubin - 21 znaków
Test
źródło
Java, 85 znaków
źródło
import java.math.*;
(więc +19 bajtów).PostScript, 26 znaków
Przykład:
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:
źródło
1.#INF
. (Użyłem standardowego GNU Ghostscript 9.0.7 skompilowanego dla Windows x64.)JavaScript, 25
CoffeeScript, 19
Zwraca
true
w przypadku n = 0, ale JavaScript i tak wymusi to na 1.źródło
return
instrukcji w funkcji JavaScript?return
! Ale dlaczego nie?function f(n)n?n*f(--n):1
f=n=>!n||n*f(n-1)
Weź to, CoffeeScript!Rubin -
3029 znakówTest
źródło
end
bezpośrednio po nim:*
bez znaku nowej linii lub średnika.(1..10).inject :*
# => 3628800f(0)
?f=->n{(1..n).inject 1,:*}
. Zadzwoń za pomocąf[n]
.F #: 26 znaków
W języku F # nie ma wbudowanej funkcji produktu, ale możesz zrobić ją składając
źródło
C #, 20 lub 39 znaków w zależności od twojego punktu widzenia
Jako tradycyjna metoda instancji (39 znaków; przetestowano tutaj ):
Jako wyrażenie lambda (20 znaków, ale patrz wyłączenie odpowiedzialności; przetestowano tutaj ):
Musimy użyć,
double
ponieważ 125! == 1,88 * 10 209 , 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 :
Ale to powoduje :
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,
2119 znaków naprawdęTestowany tutaj: http://jsfiddle.net/0xjdm971/
źródło
Brachylog ,
76 bajtówPrzez utworzenie zakresu i pomnożenie go
-1 bajtowe zbiorniki na jaja mające pomysł na użycie funkcji max ()
Wyjaśnienie
Wypróbuj online!
Brachylog ,
109 bajtówrekurencja
Wyjaśnienie
Wypróbuj online!
źródło
;
zamiast,
pozwala na zwykłe wprowadzanie liczbowe. -1 bajt mimo toC (39 znaków)
źródło
double f(n){return!n?1:n*f(n-1);}
- 33 znaki.f(125)
przepełni sięD: 45 znaków
Bardziej czytelnie:
Cooler (choć dłuższa wersja) to szablonowy, który robi to wszystko w czasie kompilacji ( 64 znaki ):
Bardziej czytelnie:
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.
źródło
PowerShell - 36
Naiwny:
Test:
źródło
Scala, 39 znaków
Większość znaków zapewnia, że
BigInt
s są używane, więc spełniony jest warunek dla wartości do 125.źródło
(x:Int)=>(BigInt(1)to x).product
def f(x:Int)=(BigInt(1)to x).product
def f(x:BigInt)=(x.to(1,-1)).product
def f(x:BigInt)=(-x to-1).product.abs
JavaScript, ES6 17
ES6:
źródło
PowerShell, 42 bajty
(zapisane 2 znaki przy użyciu filtru zamiast funkcji )
Wynik:
źródło
filter f($x){if($x){$x*(f($x-1))}else{1}}
. Można go dodatkowo zmniejszyć do 36 znaków, jeśli jest wywoływany przez potok, ponieważ jest to filtr (np.125|f
):filter f{if($_){$_*($_-1|f)}else{1}}
Rakieta (schemat)
403529 bajtówOblicza 0! być 1 i oblicza 125! w 0 sekund zgodnie z zegarem. Regularne podejście rekurencyjne
Nowa wersja do pokonania wspólnego lisp: zwielokrotnia wszystkie elementy listy (tak samo jak rozwiązanie Haskell)
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
źródło
Mornington Crescent ,
18271698 znakówChciał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!
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.
Włożyłem w to sporo pracy, ale ponieważ jest to moja pierwsza gra w golfa w Mornington Crescent (właściwie moja pierwsza próba w dowolnym języku), spodziewam się, że przegapiłem kilka optymalizacji tu i tam. Jeśli jesteś zainteresowany programowaniem w tym języku (i dlaczego nie miałbyś być?), Esoteric IDE - z trybem debugowania i oknem oglądania - jest koniecznością!
źródło
Befunge - 2x20 = 40 znaków
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
Testowanie 0
źródło
&:!#@_>:# 1# -# :# _$>\# :#* _$.@
(gdzie i należy zastąpić danymi wejściowymi). Ma 32 znaki / bajtyJ - 6 znaków
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!
źródło
W C (23 znaki)
To narusza „funkcję” GCC, która powoduje, że ostatnie przypisanie jest liczone jako zwrot, jeśli nie określono zwrotu.
W prawidłowym C, 28 znaków
źródło
0 == ({printf("Hello, world!"); 0;});
Kona (
116)K działa od prawej do lewej (w przeważającej części), więc wyliczamy
x
(tworzymy listę / tablicę liczb od0
dox-1
), dodajemy1
do niej (zakresy list0
dox
), a następnie mnożymy wszystkie liczby razem. Gdyby obliczenie nie było wymogiem125!
, mógłbym zaoszczędzić 1 bajt, eliminując.
obok1
. W każdym razie 125! jest obliczany w zaledwie milisekundach:źródło
*/1.+!
: 6 bajtów.