Stack Cats , 62 + 4 = 66 bajtów
*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]
Musi być uruchamiany z -lnflagami wiersza poleceń (stąd +4 bajty). Wydruki 0liczb zespolonych i 1liczb pierwszych.
Wypróbuj online!
Myślę, że to pierwszy nietrywialny program Stack Cats.
Wyjaśnienie
Szybkie wprowadzenie do Stack Cats:
- Stack Cats działa na nieskończonej taśmie stosów, a głowica taśmy wskazuje na bieżący stos. Każdy stos jest początkowo wypełniony nieskończoną liczbą zer. Generalnie zignoruję te zera w moim sformułowaniu, więc kiedy mówię „dolna część stosu”, mam na myśli najniższą niezerową wartość i jeśli mówię „stos jest pusty”, to znaczy, że są na nim tylko zera.
- Przed uruchomieniem programu a
-1jest umieszczany na początkowym stosie, a następnie na nim umieszczane jest całe wejście. W tym przypadku, ze względu na -nflagę, dane wejściowe są odczytywane jako liczba całkowita dziesiętna.
- Pod koniec programu bieżący stos jest używany do wyświetlania. Jeśli jest
-1na dole, zostanie zignorowany. Ponownie, ze względu na -nflagę, wartości ze stosu są po prostu drukowane jako liczby całkowite dziesiętne oddzielone wierszem.
- Stack Cats to odwracalny język programu: każdy fragment kodu można cofnąć (bez Stack Cats śledzącego jawną historię). Mówiąc dokładniej, aby odwrócić dowolny fragment kodu, po prostu dublujesz go, np .
<<(\-_)Staje się (_-/)>>. Ten cel projektowania nakłada dość surowe ograniczenia na to, jakie rodzaje operatorów i konstrukcje przepływu sterowania istnieją w języku i jakie funkcje można obliczyć na temat stanu pamięci globalnej.
Podsumowując, każdy program Stack Cats musi być samosymetryczny. Możesz zauważyć, że nie dotyczy to powyższego kodu źródłowego. Do tego służy -lflaga: domyślnie odzwierciedla kod po lewej stronie, używając pierwszego znaku na środku. Stąd faktyczny program to:
[<(*>=*(:)*[(>*{[[>[:<[>>_(_-<<(-!>)>(>-)):]<^:>!->}<*)*[^:<)*(>:^]*(*>{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}*<)]*(:)*=<*)>]
Efektywne programowanie przy użyciu całego kodu jest wysoce nietrywialne i nieintuicyjne i tak naprawdę nie odkryłem jeszcze, jak człowiek może to zrobić. Brutalnie zmusiliśmy taki program do prostszych zadań, ale nie bylibyśmy w stanie zbliżyć się do niego ręcznie. Na szczęście znaleźliśmy podstawowy wzorzec, który pozwala zignorować połowę programu. Chociaż z pewnością nie jest to optymalne, obecnie jest to jedyny znany sposób skutecznego programowania w Stack Cats.
W tej odpowiedzi szablon tego wzorca jest następujący (istnieje pewna zmienność w sposobie jego wykonywania):
[<(...)*(...)>]
Po uruchomieniu programu taśma stosu wygląda następująco ( 4powiedzmy na wejściu ):
4
... -1 ...
0
^
W [przesuwa wierzchu stosu po lewej stronie (a głowica taśmy wzdłuż) - nazywamy to „pchanie”. I <porusza głową taśmy. Po pierwszych dwóch poleceniach mamy następującą sytuację:
... 4 -1 ...
0 0 0
^
Teraz (...)jest to pętla, której można dość łatwo używać jako warunkowego: pętla jest wprowadzana i opuszczana tylko wtedy, gdy góra bieżącego stosu jest dodatnia. Ponieważ obecnie wynosi zero, pomijamy całą pierwszą połowę programu. Teraz centralne polecenie to *. Jest to po prostu XOR 1, tzn. Przełącza najmniej znaczący bit górnej części stosu, w tym przypadku zamieniając 0w 1:
... 1 4 -1 ...
0 0 0
^
Teraz spotykamy lustrzane odbicie (...). Tym razem wierzchołek stosu jest dodatnia, a my zrobić wprowadzić kod. Zanim przejdziemy do tego, co dzieje się w nawiasach, pozwól mi wyjaśnić, jak zakończymy na końcu: chcemy upewnić się, że na końcu tego bloku znów będziemy mieć wartość dodatnią na głowie taśmy (tak aby pętla kończy się po pojedynczym iteracji i służy jedynie jako liniowy warunkowy), aby papier w prawo posiada wyjście i prawy stos , który trzyma -1. W takim przypadku opuszczamy pętlę, >przechodzimy do wartości wyjściowej i ]wypychamy ją na -1tak, aby uzyskać czysty stos dla danych wyjściowych.
To tyle. Teraz w nawiasach możemy zrobić wszystko, co chcemy, aby sprawdzić pierwotność, o ile upewnimy się, że wszystko skonfigurowaliśmy zgodnie z opisem w poprzednim akapicie na końcu (co można łatwo zrobić, przesuwając głowę i przesuwając taśmę). Najpierw próbowałem rozwiązać problem z twierdzeniem Wilsona, ale skończyło się to na ponad 100 bajtach, ponieważ kwadratowe obliczenia czynnikowe są w rzeczywistości dość drogie w Stack Cats (przynajmniej nie znalazłem krótkiej drogi). Więc zamiast tego poszedłem z podziałem próbnym i to rzeczywiście okazało się znacznie prostsze. Spójrzmy na pierwszy bit liniowy:
>:^]
Widziałeś już dwa z tych poleceń. Ponadto :zamienia dwie górne wartości bieżącego stosu, a ^XOR drugą wartość na najwyższą. Powoduje :^to wspólny wzorzec do powielania wartości na pustym stosie (ciągniemy zero na górze wartości, a następnie zamieniamy zero na 0 XOR x = x). Po tym sekcja naszej taśmy wygląda następująco:
4
... 1 4 -1 ...
0 0 0
^
Zaimplementowany przeze mnie algorytm podziału próby nie działa na dane wejściowe 1, dlatego w takim przypadku powinniśmy pominąć kod. Możemy łatwo mapować 1do 0i wszystko co do wartości dodatnie *, więc oto jak to zrobić:
*(*...)
To znaczy zamieniamy się 1w 0, pomijamy dużą część kodu, jeśli rzeczywiście otrzymujemy 0, ale w środku natychmiast cofamy, *aby odzyskać naszą wartość wejściową. Musimy tylko upewnić się, że kończymy na wartości dodatniej na końcu nawiasów, aby nie zaczęły się zapętlać. Wewnątrz trybu warunkowego przesuwamy jeden stos w prawo za pomocą, >a następnie uruchamiamy główną pętlę podziału próby:
{<-!<:^>[:((-<)<(<!-)>>-_)_<<]>:]<]]}
Nawiasy klamrowe (w przeciwieństwie do nawiasów) definiują inny rodzaj pętli: jest to pętla „do-while”, co oznacza, że zawsze działa przez co najmniej jedną iterację. Inną różnicą jest warunek zakończenia: po wejściu do pętli Stack Cat zapamiętuje najwyższą wartość bieżącego stosu ( 0w naszym przypadku). Pętla będzie następnie działać, dopóki ta sama wartość nie będzie ponownie widoczna na końcu iteracji. Jest to dla nas wygodne: w każdej iteracji po prostu obliczamy resztę następnego potencjalnego dzielnika i przenosimy na ten stos, na którym rozpoczynamy pętlę. Kiedy znajdziemy dzielnik, reszta jest, 0a pętla zatrzymuje się. Spróbujemy podzielić dzielniki, zaczynając od, n-1a następnie zmniejszamy je do 1. Oznacza to, że a) wiemy, że to się skończy, gdy dotrzemy1najpóźniej ib) możemy ustalić, czy liczba jest liczbą pierwszą, czy nie, sprawdzając ostatni dzielnik, którego próbowaliśmy (jeśli jest 1to liczba pierwsza, w przeciwnym razie nie jest).
Weźmy się za to. Na początku jest krótki odcinek liniowy:
<-!<:^>[:
Wiesz, co robi większość z tych rzeczy. Nowe polecenia to -i !. Koty stosu nie mają operatorów zwiększania ani zmniejszania. Jednak ma -(negacja, tj. Pomnożenie przez -1) i !(bitowe NIE, tj. Pomnożenie przez -1i zmniejszenie). Można je połączyć w przyrost !-lub zmniejszenie -!. Więc zmniejszamy kopię nna wierzchu -1, a następnie tworzymy kolejną kopię nna stosie po lewej stronie, a następnie pobieramy nowy dzielnik próbny i umieszczamy go pod spodem n. Tak więc przy pierwszej iteracji otrzymujemy:
4
3
... 1 4 -1 ...
0 0 0
^
W kolejnych iteracjach 3zostanie zastąpiony kolejnym dzielnikiem testowym i tak dalej (podczas gdy dwie kopie nzawsze będą miały tę samą wartość w tym momencie).
((-<)<(<!-)>>-_)
To jest obliczenie modulo. Ponieważ pętle kończą się na wartościach dodatnich, chodzi o to, aby zacząć od -ni wielokrotnie dodawać ddo niego dzielnik próbny , aż do uzyskania wartości dodatniej. Gdy to zrobimy, odejmujemy wynik od, da to daje nam resztę. Problem polega na tym, że nie możemy po prostu umieścić -nna wierzchu stosu i uruchomić pętli, która dodaje d: jeśli górna część stosu jest ujemna, pętla nie zostanie wprowadzona. Takie są ograniczenia odwracalnego języka programowania.
Aby więc obejść ten problem, zaczynamy nod stosu, ale negujemy go tylko przy pierwszej iteracji. Znowu to brzmi prościej, niż się okazuje ...
(-<)
Kiedy górna część stosu jest dodatnia (tj. Tylko przy pierwszej iteracji), negujemy ją -. Jednak nie możemy tego zrobić, (-)ponieważ nie opuścilibyśmy pętli, dopóki nie zostanie -zastosowana dwukrotnie. Więc przesuwamy jedną komórkę w lewo, <ponieważ wiemy, że jest tam dodatnia wartość (the 1). Okej, więc teraz rzetelnie zanegowaliśmy npierwszą iterację. Ale mamy nowy problem: głowica taśmy znajduje się teraz w innej pozycji podczas pierwszej iteracji niż w każdym innym. Musimy to skonsolidować, zanim przejdziemy dalej. Następny <przesuwa głowicę taśmy w lewo. Sytuacja przy pierwszej iteracji:
-4
3
... 1 4 -1 ...
0 0 0 0
^
A przy drugiej iteracji (pamiętaj, że dodaliśmy ddo tego raz -n):
-1
3
... 1 4 -1 ...
0 0 0
^
Następny warunek ponownie łączy te ścieżki:
(<!-)
Podczas pierwszej iteracji głowica taśmy wskazuje zero, więc jest to całkowicie pomijane. Podczas kolejnych iteracji głowa taśmy wskazuje na jedną, więc wykonujemy to, przesuwamy się w lewo i zwiększamy tam komórkę. Ponieważ wiemy, że komórka zaczyna się od zera, teraz będzie zawsze dodatnia, więc możemy opuścić pętlę. To gwarantuje, że zawsze kończymy dwa stosy z głównego stosu i możemy teraz cofnąć się >>. Następnie robimy na końcu pętli modulo -_. Już wiesz -. _jest odejmowanie wartości ^XOR: jeśli górna część stosu znajduje się, aa wartość pod spodem bzastępuje asię b-a. Ponieważ jednak po raz pierwszy zanegowaliśmy a, -_zastępuje asię b+a, dodając w ten sposóbd do naszej bieżącej sumy.
Po zakończeniu pętli (osiągnęliśmy wartość dodatnią) taśma wygląda następująco:
2
3
... 1 1 4 -1 ...
0 0 0 0
^
Najbardziej lewą wartością może być dowolna liczba dodatnia. W rzeczywistości jest to liczba iteracji minus jedna. Teraz jest jeszcze jeden krótki liniowy bit:
_<<]>:]<]]
Jak powiedziałem wcześniej, musimy odjąć wynik, daby uzyskać rzeczywistą pozostałość ( 3-2 = 1 = 4 % 3), więc po prostu _raz jeszcze. Następnie musimy wyczyścić stos, który zwiększaliśmy po lewej stronie: kiedy próbujemy następnego dzielnika, musi on ponownie wynosić zero, aby pierwsza iteracja zadziałała. Więc przenosimy się tam i przesuwamy tę dodatnią wartość na drugi stos pomocników za pomocą, <<]a następnie wracamy na nasz stos operacyjny za pomocą innego >. Możemy podciągnąć dsię :i wsunąć go z powrotem na -1z ]a potem przenieść pozostałą na nasz stos z warunkowym <]]. To koniec pętli podziału próbnego: trwa to do momentu, aż otrzymamy resztę zera, w którym to przypadku zawiera stos po lewej stroniennajwiększy dzielnik (inny niż n).
Po zakończeniu pętli tuż *<przed ponownym połączeniem ścieżek z danymi wejściowymi 1. Po *prostu zamienia zero na a 1, które za chwilę będziemy potrzebować, a następnie przechodzimy do dzielnika za pomocą <(abyśmy byli na tym samym stosie, co na wejściu 1).
W tym momencie pomaga porównać trzy różne rodzaje danych wejściowych. Po pierwsze, szczególny przypadek, w n = 1którym nie zrobiliśmy żadnych rzeczy z tego działu próbnego:
0
... 1 1 -1 ...
0 0 0
^
Następnie, nasz poprzedni przykład n = 4, liczba złożona:
2
1 2 1
... 1 4 -1 1 ...
0 0 0 0
^
I wreszcie n = 3liczba pierwsza:
3
1 1 1
... 1 3 -1 1 ...
0 0 0 0
^
Tak więc dla liczb pierwszych mamy 1na tym stosie, a dla liczb zespolonych albo mamy 0liczbę dodatnią, albo większą niż 2. Zamieniamy tę sytuację w 0lub 1potrzebujemy za pomocą następującego końcowego fragmentu kodu:
]*(:)*=<*
]po prostu przesuwa tę wartość w prawo. Następnie *jest wykorzystywana w celu uproszczenia sytuacji warunkowego znacznie: przełączając najmniej znaczącego bitu, zwracamy 1(prime) do 0, 0(kompozytowe) do wartości dodatniej 1, a wszystkie inne wartości dodatnie będą nadal pozytywne. Teraz musimy tylko odróżnić od 0pozytywnego. Tam używamy innego (:). Jeśli górna część stosu to 0(a wejście było liczbą pierwszą), jest to po prostu pomijane. Ale jeśli górna część stosu jest dodatnia (a dane wejściowe były liczbą złożoną), zamienia to na 1, więc teraz mamy 0dla1dla liczb pierwszych - tylko dwie różne wartości. Oczywiście są one przeciwieństwem tego, co chcemy uzyskać, ale łatwo to naprawić za pomocą innego *.
Teraz wszystko, co pozostało jest przywrócenie wzór stosy oczekiwanych przez nas otaczającego ramy: głowy taśmy na wartości dodatniej, wynik na wierzchu stosu po prawej i jeden -1po prawej stronie stosu że . Po to =<*jest. =zamienia szczyty dwóch sąsiednich stosów, przesuwając w ten -1sposób na prawo od wyniku, np. w celu 4ponownego wprowadzenia :
2 0
1 3
... 1 4 1 -1 ...
0 0 0 0 0
^
Następnie przesuwamy się w lewo za pomocą <i zamieniamy to zero na jedno z *. I to jest to.
Jeśli chcesz głębiej poznać działanie programu, możesz skorzystać z opcji debugowania. Dodaj -dflagę i wstaw "tam, gdzie chcesz zobaczyć bieżący stan pamięci, np. Tak , lub użyj -Dflagi, aby uzyskać pełny ślad całego programu . Alternatywnie możesz użyć EsotericIDE firmy Timwi, która zawiera interpreter Stack Cats z debuggerem krok po kroku.
