To wyzwanie zostało zainspirowane blogiem programistycznym, który często odwiedzam. Zobacz oryginalny post tutaj: A Programming Puzzle
Wyzwanie
Zdefiniuj funkcję f:Q->Q
taką, że f(f(n)) = -n
dla wszystkich niezerowych liczb całkowitych n
, i gdzie Q
jest zbiorem liczb wymiernych.
Detale
W jakimkolwiek języku, który preferujesz, proszę zdefiniować jedną funkcję lub program, f
który przyjmuje jako parametr jeden numer n
i zwraca lub wyprowadza jeden numer f(n)
.
Dane wejściowe mogą być dostarczane za pomocą dowolnego mechanizmu najbardziej naturalnego dla Twojego języka: argument funkcji, odczyt z STDIN, argument wiersza poleceń, pozycja stosu, wejście głosowe, znaki gangów itp.
Wyjście powinno być wartością zwracaną z funkcji / programu lub drukowane do STDOUT.
Chciałbym ograniczyć odpowiedzi do funkcji, które nie wykorzystują stanu programu lub globalnej pamięci / danych widocznych z zewnątrz funkcji f
. Na przykład trzymanie licznika poza f
tym liczy liczbę wywołań, f
a samo wykonanie negacji na podstawie tej liczby nie jest bardzo trudne ani interesujące dla nikogo. Decyzje f
powinny opierać się wyłącznie na danych w f
zakresie leksykalnym.
Jednak to ograniczenie jest prawdopodobnie nieodpowiednie dla niektórych języków zorientowanych na stos lub innych typów języków, które nie rozróżniają tych typów danych ani zakresów. Prosimy o dokonanie najlepszego osądu, aby zachować ducha tego wyzwania.
Punktacja
Obowiązują wspólne zasady gry w golfa - twój wynik to liczba bajtów w kodzie źródłowym.
Minimalna odpowiedź wymaga, aby domena i kodomain f
były podzbiorem racjonalności Q
. Jeśli ograniczysz swoją domenę i kodomainę f
do liczb całkowitych Z
, twój wynik to pułap 90% liczby bajtów w kodzie źródłowym.
Tiebreak
W przypadku remisu zostaną użyte następujące elementy:
- Najmniejsza liczba drukowanych symboli spacji w kodzie źródłowym
- Najwcześniejsza data i godzina przesłania odpowiedzi
Edytować
Nie musisz obsługiwać liczb o dowolnych rozmiarach. Interpretuj zestawy Z
i Q
typy danych w wybranym języku (zwykle odpowiednio liczby całkowite i zmiennoprzecinkowe).
Jeśli twoje rozwiązanie opiera się całkowicie na podstawowej strukturze lub strukturze bitowej typu danych, opisz jego ograniczenia i sposób użycia.
f:Q->Q
to znaczy?f
jest funkcją mapującą członkówQ
(liczb wymiernych) na inne elementy (być może takie same)Q
. patrz en.wikipedia.org/wiki/Function_(mathematics)#NotationOdpowiedzi:
J, 9 punktów (10 znaków)
Na podstawie odpowiedzi stackoverflow :
Pierwszy pomysł (13 znaków):
źródło
Python:
61 34 30 2927 punktówf: Q -> Q
w matematyce:
w Pythonie:
testowane z
logika tego:
Gdy weźmiesz liczbę całkowitą
n
i włożysz ją dof
siebie, dostanieszx+0.5
. To nie jest liczbą całkowitą dłużej, więc kolejna aplikacja będzie0.5-(x+0.5)
co jest-x
.Kredyty
Dzięki
Notatki
Najpierw pomyślałem, że będzie dobrze
ale jego f: N-> C i to jest niedozwolone: - /
źródło
f=lambda x:x%1>0and(-x+x%1)or x+.1
który ma tylko 34 znaki.f=lambda x:[x+.1,x%1-x](x%1>0)
jest tylko 30f=lambda x:[x+.5,.5-x][x%1>0]
. Zwróć uwagę na użycie .5 zamiast .1 do obejścia problemów z precyzjąf:Q->Q
oznacza tylko, że f odwzorowuje liczbę wymierną na liczby wymierne. Co robi moja definicja f.C, 41 punktów (41 lub 45 znaków)
Działa zarówno w wersji 32-, jak i 64-bitowej.
f : Z -> Z
(opróczINT_MAX
):Jeśli nie musimy dołączać
0
, możemy ogolić niektóre znaki (41 znaków):f : Z -> Z
(z wyjątkiem0
&INT_MAX
):Ta funkcja polega na podzieleniu wszystkich liczb całkowitych na 4 grupy na podstawie ich znaku i parzystości.
Mamy więc 4 różne kombinacje:
Ponieważ musimy zmienić znak liczby, ale nie parzystości po dwóch przejściach, otrzymujemy dwie różne możliwe sekwencje:
W tym przykładzie wybrałem pierwszy.
Najpierw musimy zmapować wszystkie parzyste dodatnie liczby całkowite na nieparzyste ujemne liczby całkowite. Robimy to, zmieniając znak i zwiększając liczbę (możesz też zamiast tego zmniejszyć liczbę):
Następnie musimy zmapować wszystkie nieparzyste ujemne liczby całkowite na nawet ujemne liczby całkowite. Musimy upewnić się, że
f2(f1(n)) = -n
:Stosując te same metody, które znajdujemy
f3
if4
:Aby połączyć te funkcje w jedną funkcję, obserwujemy, że za każdym razem
n
zmieniamy znakn
i za każdym razem, gdyn
jest dodatni, zwiększamy o jedną, a w przeciwnym razie zmniejszamy o jedną:Można to zatem przepisać jako:
gdzie
odd(n)
zwraca1
liczby nieparzyste i-1
parzyste.Łącznie są 4 rozwiązania:
INT_MIN
zawsze może być uważany za przypadek zbocza we wszystkich 4 funkcjach jako-INT_MIN == INT_MIN
=>f(f(INT_MIN)) = INT_MIN
.źródło
0
3 innych liczb.Z
bonusu, jeśli pokryjesz przynajmniej 0.Oto mój wybór.
Przykład na żywo :
Typy wejściowe cn można dowolnie dostosować do własnych potrzeb. Ta wersja działa dla literałów całkowitych, które są mniejsze niż 2 ^ 32-1.
źródło
f:Q->Q
, nief:Z->Z
.f:Z->Z
, przepraszam za mylące sformułowaniereturn -i
JavaScript, 18
Korzystanie z nowej notacji grubej strzałki (Firefox 22).
Inna wersja (18):
Poprzednia wersja (20):
Przykład:
źródło
Mathematica 18
Oto
⌊...⌋
funkcja podłogi. Używa tylko liczb wymiernych (nie list, liczb zespolonych itp.)źródło
język asemblera x86 (FASM). Argument i wynik znajdują się w rejestrze eax.
Działa poprawnie dla -2 ^ 30 <N <+ 2 ^ 30-1
16-bajtowy kod wykonywalny.
źródło
Common Lisp: 35 bajtów
Schemat (i rakieta): 36 bajtów
Niegolfowany z komentarzami i objaśnieniami:
Na dowolny numer
x
w zamieni się frakcji , która jest prawdziwym dokładna liczba w obu językach.[1,->]
if
1/2
Część podziału stanie się wtedy,
(/ 1/2 x)
aby ułamek stał się1/(x*2)
zawsze poniżej1
. Bo1
tak będzie1/2
, bo2
to jest1/4
itd.Dla dowolnej liczby poniżej 1
if
zamieni się na ułamek-1/2
, co sprawia, że funkcja robi(/ -1/2 x)
to, co jest,-1/(2*x)
ale ponieważ możemy spodziewać się, że wartość będzie wynikiem poprzedniego przebiegu, możemy podstawić x na 1 / (x * 2) wykonując podwójną aplikację-1/((1/(x*2))*2) = -x
Np. Skoro
1
zamienia się1/2
w drugą aplikację to(/ -1/2 1/2) ==> -1
źródło
C, 60 (⌈66 * .9⌉)
Oto nieskondensowana wersja:
Ta metoda działa tylko przy użyciu liczb całkowitych, więc otrzymuje premię w wysokości 90% wyniku. Początkowo pisałem go w Javie, ale zdałem sobie sprawę, że ten program może w szczególności skorzystać z operatorów logicznych typu C.
Ponieważ nie ma liczby całkowitej odpowiadającej
-INT_MIN
,f(f(INT_MIN))
zwracaINT_MIN
zamiast tego.Podstawowe mapowanie jest algebraicznie raczej proste. Wykonanie instrukcji
x=f(x)
zastępuje x przez:x+1
, jeślix
jest dodatnia i nieparzysta-x+1
, jeślix
jest dodatnia i równax-1
, jeślix
jest ujemne i nieparzyste-x-1
, jeślix
jest ujemne i parzysteWynik każdego przypadku znajdzie się w następnym przypadku przy następnym zastosowaniu funkcji do x.
Jak widać, komponowanie sprawy z przypadkiem następującym po niej daje wynik
-x
.Kod jest wynikiem sprytnego uproszczenia funkcji, aby wykorzystać strukturę bitową liczb całkowitych komplementu dwóch.
źródło
> <> , 21 + 3 = 24 bajty, 22 punkty
Użyj oficjalnego interpretera języka Python i użyj
-v
opcji wiersza polecenia, aby wprowadzić dane wejściowe, kosztem 3 bajtów.Mam wrażenie, że może być lepiej - będę na to patrzeć i próbować grać w golfa.
Podane dane
n
wyjściowe programugdzie
(n>0)
i(n<0)
są booleanami. Jest to równoważne z odpowiedzią Gelatona na Pythonale
><>
nie ma wbudowanego operatora potęgowania, więc(1 - 2*(n%2))
zamiast niego używamy(-1)**n
.Poniżej znajduje się teoria matematyczna - czytaj, jeśli jesteś (i tylko jeśli) zainteresowany:
Biorąc pod uwagę żadnej funkcji
f: Z -> Z
takich, żef(f(n)) = -n
dla wszystkichn
INZ
, widzimy od razu, żef(f(f(f(n)))) = n
, innymi słowy,f^4
jest to funkcja tożsamości. W szczególnościf
jest odwracalny, a jego funkcją odwrotną jestf^3
. W ten sposóbf
jest permutacjąZ
i od tegof^4 = Id
wynika, że każdy orbity (lub cykl) zf
ma wielkość albo1
,2
, lub4
.Następnie widzimy to
f(0) = 0
. Dowód:f(0) = f(-0) = f(f(f(0))) = -f(0)
, więcf(0) = 0
, zgodnie z życzeniem. I odwrotnie, załóżmy, żex
jest w cyklu długości1
lub2
takf(f(x)) = x
. Więc-x = x
takx = 0
.Tak więc
f
składa się całkowicie z 4 cykli, z wyjątkiem stałego punktu (1 cykl) przy0
.Ponadto, każdy 4-cykl musi mieć formę
(x, y, -x, -y)
, i obracając się wokół cyklu możemy założyć, żex
iy
to zarówno pozytywne. I odwrotnie, każdy taki iloczyn 4-cykli dzielących niezerowe liczby całkowite determinuje wybórf
.Zatem każdy wybór
f
odpowiada jednoznacznie wykresowi skierowanemu, którego wierzchołki są dodatnimi liczbami całkowitymi, tak że każdy wierzchołek pada dokładnie na jedną strzałkę, wchodząc lub wychodząc. Mówiąc ściślej, na podstawowym wykresie niekierowanym każdy wierzchołek ma dokładnie stopień1
. (W każdym cyklu 4(x y -x -y)
zx
iy
pozytywnych zgodny ze strzałkąx --> y
).Funkcja w tej odpowiedzi (oraz kilku innych odpowiedzi tutaj) odpowiada na wykresie, gdzie
1 --> 2
,3 --> 4
iw ogóle2k-1 --> 2k
.Takie wykresy są bijection z nieskończonymi sekwencjami uporządkowanych par
(a_n, p_n)
, gdzie każdaa_n
jest dodatnią liczbą całkowitą, a każdyp_n
jest albo0
albo1
: biorąc pod uwagę sekwencję(a_1, p_1), (a_2, p_2), (a_3, p_3), ...
, najpierw łączymy się1
z1 + a_1
, a następnie tworzymy strzałkę1 --> 1 + a_1
lub strzałkę w1 + a_1 --> 1
zależności od tego, czyp_1
jest0
lub1
. Zasadniczo strzałka jest albo<
znakiem, albo>
znakiem, w zależności od parytetup_1
.Następnie weź najmniejszą niesparowaną dodatnią liczbę całkowitą
k
i policz odk
, dokładniea_2
kroków, POMIŃ dowolnej liczby, która jest już z czymś sparowana. Sparujk
z wynikiem i ustaw kierunek strzałki w zależności odp_2
powyższego. Następnie powtórz za pomocą(a_3, p_3)
itd.Każda strzałka zostanie ostatecznie określona w ten sposób, więc proces jest dobrze zdefiniowany. Funkcja w tej odpowiedzi odpowiada sekwencji
(1,0), (1,0), (1,0), ...
, ponieważ na etapien
najmniejsza niesparowana liczba całkowita jest2n-1
i nie ma liczb całkowitych większych niż2n-1
zostały sparowane z czymkolwiek, więc otrzymujemy2n-1 --> 2n
dla każdegon
(strzałki są zorientowane w ten sposób, ponieważ każdyp_n
jest równy0
).Liczność tego zbioru jest równa liczności liczb rzeczywistych
(N*2)^N = N^N
w ostatnim akapicie tej odpowiedzi2^N
.źródło
Aby naprawić wcześniejszą odpowiedź J (nie mam wystarczającej reputacji, aby skomentować oryginał):
To po prostu zastępuje
_1&^
się1-~2*2|]
, co daje znak przeciwny. Więc zmieniłem na-
a+
(co ma znaczenie tylko na wejściu1
i_1
).Oto testy:
Jak widać, domena i zakres są liczbami rzeczywistymi, ale działa tylko dla liczb całkowitych (w tym 0).
Wyjaśnienie:
źródło
GolfScript
ceiling(26*.9)=24
Golfscript obsługuje tylko liczby całkowite, więc zastosuj
Z
premię za łącznie 24 punkty:Specjalny przypadek 0 oznacza 8 znaków. Ignorując 0, możemy uzyskać odpowiedź 17 punktów:
Ten kod wykonuje następujące operacje
x
na liczbie całkowitej na szczycie stosu:x
wynosi 0, zostaw0
na stosie i nie stosuj więcej reguł.x
jest parzysty, zanegujx
.x
jest dodatnia, dodaj1
.x
jest ujemne, odejmij1
.To logicznie łączy zestawy 4 liczb w cyklu, w których
f
elementy przecinają cykl, a przeciwległe rogi cyklu są względem siebie ujemne. Każda liczba całkowita jest częścią dokładnie 1 takiego cyklu, z wyjątkiem 0, która jest przypadkiem specjalnym. Na przykład dla{-8, -7, 7, 8}
:7 f -> 8
8 f -> -7
-7 f -> -8
-8 f -> 7
Jedynymi istotnymi przypadkami, o których mogłem pomyśleć, były nieparzyste ujemne, parzyste ujemne, parzyste nieparzyste, parzyste dodatnie
0
, a potem wrzuciłem,-1
a1
ponieważ ich bliskość0
mogła powodować problemy:Jestem pewien, że faktyczny GolfScript można nieco poprawić. Nie wydaje się, że powinno to zająć 26 znaków! Bardzo chciałbym usłyszeć kilka sugestii.
źródło
Java, dla zabawy
Oto implementacja, która wykonuje rzeczywisty biject między ℤ i ℤ², co jest jednocześnie funkcją nieparzystą (g (-x) == -g (x)). Traktuje odpowiedni element ℤ² jako liczbę zespoloną i mnoży go przez „i”, a następnie konwertuje z powrotem na ℤ.
f (x) = g⁻¹ (ig (x))
f (f (x)) = g⁻¹ (-g (x)) = - x
Funkcja działa w O (1).
PS Szczęśliwego Nowego Roku!
źródło
Python 3-38
Podobny do @ odpowiedź Moose, ale,
f(n) == n
. Działa dla wszystkich wartości całkowitych.źródło
Perl, 33 (bez białych znaków)
Edytować:
$=.".1"
skrócone do"$=.1"
(dzięki ardnew).Matematyka:
Nie golfowany:
Przykłady:
źródło
sub f{yzxzzc?-$_:x.$_}
sub f{yzxzzc?-$_:x.$_}
jest wolny od stanu, wykorzystuje stan za pośrednictwem zmiennej . Z tego powodu nie jest już funkcją (w sensie matematycznym), ponieważ możliwe są różne wartości dla tej samej wartości wejściowej w zależności od stanu (pogoda zawiera lub nie). Mój algorytm nie używa stanu. Informacja jest zakodowana w wartości wyjściowej. Dodając, liczby całkowite są konwertowane na liczby rzeczywiste . A liczby rzeczywiste są konwertowane z powrotem na liczby całkowite z przełączonym znakiem.$_
f
$_
x
.1
$=
?f
należy zdefiniowaćQ->Q
) dla tegox
znaku.$=.".1"
można również skrócić do"$=.1"
$=
jest to, że pobiera tylko liczby całkowite. To samo można osiągnąć za pomocą zwykłej zmiennej:$a=int$_[0]
. Ale to kosztuje trzy dodatkowe bajty z powodu funkcjiint
.Julia, 26 lat
Niezbyt konkurencyjny, ale bardzo Juliański, ponieważ polega na wielokrotnej wysyłce. Po prostu czyni na Rational, jeśli jest to Int, lub int ze znakiem minus, jeśli jest to coś innego. Można by sprzeciwić się, że są to 2 funkcje, ale Julia uważa, że jest to jedna funkcja z dwiema metodami i jest to równoważne z definicją jednej funkcji z instrukcją if dla typu
n
.źródło
3==3//1
wraca,true
alef(3//1)==f(3)
wracafalse
.Cukierki ,
2018 bajtówUżywa sztuczki 3 -> 4 -> -3 -> -4 -> 3.
Aby go wywołać, użyj przełącznika -i na tłumaczu
Przykład podwójnego wywołania:
Długa forma:
źródło
Dyalog APL, 9 punktów
Źródło ma długość 9 bajtów i kwalifikuje się do premii (co wcale nie pomaga). Wykorzystuje również formułę z górnej odpowiedzi SO.
źródło
Python: 32 bajty (29 punktów)
f: Z -> Z
Metoda Ben Reicha.
źródło
(n>0)-(n<0)
zcmp(n,0)
, aby zaoszczędzić kilka bajtów. (Ale nie w Pythonie 3: docs.python.org/3/whatsnew/3.0.html#ordering-comparisons )GTB , 22
źródło
Java, 113 bajtów
Podejście jest dość proste. Skończyło się to na większej liczbie bajtów, niż się spodziewałem, ale być może można trochę pograć w golfa.
Zasadniczo tworzy 4 różne „obszary” x, wykorzystując fakt, że Java szczęśliwie pozwala na zawijanie zmiennych. Musiałem wykonać trudną konwersję liczb ujemnych, co jest głównym powodem, dla którego skończyło się to na więcej niż oczekiwano.
Działa dla wszystkich x oprócz -2147483648.
źródło
Ta sama sekwencja liczb (3, 4, -3, -4, 3 ...) jak odpowiedź na skrypt golfowy, ale zaimplementowana w perlu (42 znaki po usunięciu białych znaków)
Bardziej czytelnie:
Lub jeszcze bardziej czytelnie:
Wynik:
źródło
Sed, 25 bajtów.
Stosowanie:
źródło
Matlab, 26 znaków
źródło
C ++ -
6355,8Oto jak wygląda kod:
Nie działa na liczbach całkowitych, których czwarty bajt jest równy 0xB, ponieważ używa tej wartości do śledzenia przebiegów. W przeciwnym razie działa na dowolnym elemencie Z, w tym na zero.
źródło
f
zmiennej statycznej. ale jaki jest sens tegosqrt
?sqrt
ponieważ i tak zaokrągla się w dół za pomocą rzutowania typu. Zmienię to tak, aby działało bez zmiennej statycznej.55.8
, ale twój obecny kod ma 62 bajty. Edycja: Nieważne, nie przeczytałem poprawnie pytania.Zaktualizowany o funkcję dostarczoną przez Synthetica (oczywiście ten, który powinien uzyskać teraz kredyt)
Język: Python
Liczba znaków: 41 w tym białe znaki
źródło
f=lambda x:-float(x) if str(x)==x else`x`
jest nieco krótszy: 41 w tym białe spacjef
zwraca ciąg; specyfikacja mówi, że musi zwrócić liczbę wymierną.Prolog, 36 bajtów
Kod:
Wyjaśniono:
Przykład:
źródło
JavaScript ES6,
2726 bajtówźródło
Mysz-2002 ,
211912 bajtówDefiniuje funkcję
A
; nazwij to jak#A,#A,?;;
(co będzie czekać, aż użytkownik wprowadzi dowolny numer). Możesz też nazwać to tak,#A,#A,n;;
gdzien
jest dowolny numer.źródło
Julia, 21 lat
Następnie
p // q to dosłowny zapis liczb wymiernych Julii.
źródło