Obrót struny odbywa się przez podzielenie struny na dwie części i odwrócenie ich kolejności, na przykład "world! Hello,"
obrót "Hello, world!"
. Możliwe jest tworzenie programów, które można obracać w celu utworzenia innego, ale wciąż aktualnego programu. Rozważ ten przykład w pythonie:
print ")import sys; sys.stdout.write("
Można go obrócić, aby utworzyć
import sys; sys.stdout.write("print ")
Który sam jest prawidłowym programem w języku Python.
Wyzwanie polega na napisaniu programu, który generuje sam obrót, który po uruchomieniu wygeneruje oryginalny program. Bonus wskazuje na każde wejście o długości cyklu większej niż dwa!
To jest golf golfowy, dokładna ocena będzie wynosić: (długość kodu) / (długość cyklu - 1).
EDYCJA: Mamy zwycięzcę (chyba że ktoś inny jest w stanie pokonać wynik 4)! Nadal byłbym bardzo zainteresowany wszelkimi innymi rozwiązaniami, bez względu na to, czy są to kandydaci, czy nie.
źródło
Odpowiedzi:
APL (158 znaków, wynik = 4)
Używam tutaj Dyalog APL. Liczbę cykli można zwiększyć o jeden, dodając
0
(0, a następnie spację) na końcu wyrażenia i na końcu łańcucha (przed'''
). Długość cyklu wynosi(# 0's) + 1
, a długość wyrażenia wynosi150 + 4*(cycle length))
. Zakładając, że nadal dodajemy zera na zawsze, wynikiem jestLimit[(150 + 4*n)/(n - 1), n -> Infinity] = 4
, gdzien
jest długość cyklu.Oto przykład z długością cyklu = 6:
192 znaki, wynik = 2
W zależności od implementacji jednym punktem awarii może być zbyt duża liczba przedrostkowa łańcucha. Teoretycznie możemy dodać cykl, dodając dwa znaki - a
1
na końcu ciągu (przed'''
) i a1
na końcu całej linii.200 znaków, wynik = 1
Moja implementacja APL nie ma domyślnie liczb całkowitych o nieograniczonej precyzji, więc liczba całkowita jest konwertowana na liczbę zmiennoprzecinkową, gdy staje się zbyt duża, co powoduje, że dane wyjściowe są nieprawidłowe. Więc ten jest najbardziej wybredny, ale teoretycznie (albo ręcznie, albo z innym interpreterem APL), powinien mieć wynik 1. Po prostu dodaj a
1
na końcu wyrażenia, a otrzymasz kolejny cykl.Przegląd (z krótszym okiem)
Przedstawię przegląd pierwszej wersji, ponieważ myślę, że jest to prawdopodobnie najłatwiejszy do zrozumienia. Zanim jednak zajmiemy się tą wersją, rozważymy prosty quine w APL :
Odkryłem, że jednym z najlepszych sposobów na zrozumienie niektórych wyrażeń APL jest spojrzenie na dane wyjściowe w kaskadzie operatorów / funkcji. Wszystkie operatory i funkcje w APL są skojarzone z prawą i mają taki sam priorytet, więc oto od prawej do lewej:
'''1⌽22⍴11⍴'''
: To tylko literał łańcuchowy (lista znaków).''
jest sposobem APL na unikanie pojedynczych cudzysłowów. Wyjście:'1⌽22⍴11⍴'
.11⍴'''1⌽22⍴11⍴'''
: Tutaj przekształcamy (⍴
) ciąg znaków na długość11
. Ponieważ długość łańcucha jest mniejsza niż 11, jest on powtarzany (tzn.5⍴'abc'
Dałby wynik'abcab'
). Wyjście:'1⌽22⍴11⍴''
. Mamy więc na końcu dwa znaki cudzysłowu - gdzieś się udajemy!22⍴11⍴'''1⌽22⍴11⍴'''
: Podobnie teraz przekształcamy nasze poprzednie dane wyjściowe na długość22
. Wyjście:'1⌽22⍴11⍴'''1⌽22⍴11⍴''
. Jesteśmy prawie na miejscu - wystarczy przesunąć pierwszy pojedynczy cytat na koniec.1⌽22⍴11⍴'''1⌽22⍴11⍴'''
: Tutaj obracamy (⌽
) listę znaków o1
. To przesuwa pierwszy znak ciągu na koniec. Jako kolejny przykład2⌽'abcdef'
zwraca'cdefab'
. Wyjście:1⌽22⍴11⍴'''1⌽22⍴11⍴'''
.Obracający się quine
Ten krótki quine jest główną podstawą naszego obrotowego quine. Mając to na uwadze, spójrzmy na nasz quine:
{ ... }
definiuje nienazwaną funkcję, w której będziemy wykonywać pracę. Zauważ, że funkcje w APL pobierają prawy argument oznaczony przez⍵
i opcjonalny lewy argument oznaczony przez⍺
(think infix). Chcemy zasilić tę funkcję zarówno naszym ciągiem znaków quine, jak i czymś, co pomoże nam w tworzeniu dowolnej liczby cykli. Aby ułatwić sobie (i każdemu, kto chce dodać cykle), ciąg quine jest lewym argumentem. Właściwy argument dotyczy zatem naszej listy cykli. 2 lub więcej elementów oddzielonych spacją tworzy listę, więc w tym przykładzie mamy 2-elementową listę składającą się z a1
i a0
.Widzimy, że funkcja wygląda podobnie do poprzedniej. Mamy taką samą
...⌽...⍴...⍴...
formę jak wcześniej. To dobrze - przynajmniej tyle rozumiemy! Spójrzmy prawdzie wniknąć głębiej elips, zaczynając wszystko od wyprodukowania ostatniego⍴
:⊃,/(~^/¨⍺=0)/⍺
.⍺=0
zwraca listę, w tym przypadku, o takim samym kształcie jak⍺
, gdzie każdy element⍺
jest zastępowany przez a,1
jeśli jest on równy0
, i w0
przeciwnym razie. Odbywa się to rekurencyjnie; więc jeśli mamy listę z listą znaków, poszczególne znaki zostaną przetestowane pod kątem 0, a otrzymasz listę list wartości binarnych.⍺
składa się tylko z naszego ciągu, otrzymujemy listę zer. W przeciwnym razie nasz lewy argument ma przedrostek 0 (np.0 0 0 'quinestring'
), Więc jest to lista składająca się z zer i innej listy, naszego łańcucha. Tak wygląda nasza produkcja1 1 1 <sub-list of zeros>
.^/¨⍺=0
: Stosujemy funkcję pochodną^/
, która redukuje (/
) za pomocą logicznej funkcji AND (^
), do każdego¨
elementu ( )⍺=0
. Ma to na celu spłaszczenie podlisty zer, abyśmy mogli traktować ciąg quine jako jedną wartość binarną. Biorąc pod uwagę poprzedni przykład, wynik byłby1 1 1 0
.~
: Binarnie NIE każdą z wcześniejszych wartości (np. Zwracamy0 0 0 1
).(~^/¨⍺=0)/⍺
: Dla każdego elementu⍺
replikujemy (/
) liczbę razy podaną przez odpowiedni element w lewym argumencie. To eliminuje wszystkie zera, pozostawiając nas tylko z naszym ciągiem znaków quine.⊃,/
jest niezbędną formalnością, aby upewnić się, że otrzymamy spłaszczoną listę znaków, zmniejszając wynik za pomocą funkcji konkatenacji (,
). Jeśli wejście jest już spłaszczoną listą (tzn. Lewym argumentem naszej funkcji głównej jest tylko ciąg znaków), otrzymujemy 1-elementową listę zawierającą tę listę. W innym przypadku, gdy mamy listę składającą się z podlisty ciągu, otrzymujemy tę samą rzecz z powrotem (listę z podlistą). Następnie rozpakowujemy to (⊃
), dając nam tylko pierwszy element listy (tj. Podlistę znaków). Może się to wydawać niepotrzebne, ale w przeciwnym razie próbowalibyśmy przekształcić listę 1-elementową!Następnie patrzymy na długość podaną dla pierwszego przekształcenia w nawiasach:
⍺,⍵
: Łączymy właściwy argument z pierwszym argumentem⊃,/⍺,⍵
: Tak jak poprzednio - spłaszcz listę.+/0=⊃,/⍺,⍵
: Dodaj liczbę zer na liście, zmniejszając (/
) za pomocą funkcji add (+
).2×+/0=⊃,/⍺,⍵
: Pomnóż tę liczbę przez dwa.z←2×+/0=⊃,/⍺,⍵
: Rola (←
) wynik do zmiennejz
. Reasumując,z
jest teraz dwa razy większa niż zero znalezione zarówno w lewym, jak i prawym argumencie.77+z←2×+/0=⊃,/⍺,⍵
: Następnie dodajemy77
dla znaków w ciągu znaków quine ignorowanie wszystkiego po następującym po nim spacji1
. Podobnie jak w pierwszym przykładzie quine, dodajemy 1 do długości ciągu, aby uzyskać kolejny pojedynczy cytat.'{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 ''
Argument dotyczący następującego przekształcenia jest prosty i odzwierciedla krótki quine (2-krotność długości pierwszego przekształcenia). Nasza produkcja jest teraz:
Teraz ostatni krok, w którym obliczamy, ile obrócić ciąg wyjściowy:
0
(i inna spacja) również przesunęła się na początek, chcemy obrócić ją o dodatkowe 3 znaki z powrotem.+/+/¨⍺=0
: Dodaj liczbę zer w lewym argumencie. Pierwszy (od prawej)+/¨
sumuje liczbę każdego elementu (tj. Podlistę lub tylko liczbę całkowitą), a drugi+/
daje nam sumę wynikowej listy.5+2×+/+/¨⍺=0
: Pomnóż przez dwa (aby również obrócić spacje) i dodaj 5 (wynik, który wymyśliliśmy wcześniej).-
aby obsłużyć sprawę po osiągnięciu końca naszego cyklu:(3+z)×^/⍵
: ORAZ wszystkie elementy we właściwym argumencie, aby sprawdzić, czy osiągnęliśmy koniec (1
), i pomnóż to przez3+z
.I skończone!
źródło
⍴
operatora (?). Myślę, że będę musiał przeczytać całość jeszcze kilka razy, zanim w pełni ją strawię!GolfScript, 10046/9999 ≈ 1,0047 (wynik asymptotyczny 1)
OK, spróbuję pokonać wpis APL DC w następujący sposób:
Powyższy kod nie jest prawdziwym quine - czułem, że opublikowanie jednego linijki 10kB nie byłoby dobrym pomysłem. Zamiast tego uruchomienie powyższego kodu powoduje wygenerowanie rzeczywistego programu GolfScript o długości 10046 znaków, który po iteracji opisanej w pytaniu generuje 9999 obrotów samego siebie, a na koniec samego siebie.
Długość cyklu (i programu) można regulować, zmieniając stałą
9999
. Dla zwięzłości i wygody pokażę, jak wygląda iterowane wyjście, jeśli stała zostanie zredukowana do9
:Wraz ze
9999
wzrostem stałej stosunek długości programu i długości cyklu (minus jeden) zmierza do jednego. Jestem prawie pewien, że tego rozwiązania nie da się pokonać, przynajmniej nie asymptotycznie. ;-)Jak to działa?
GolfScript jest dość łatwym językiem do pisania quinów, ponieważ w zasadzie każda literał liczbowy działa jak quine: na przykład program GolfScript
12345
generuje - tak się domyśliłeś -12345
. Ponadto łączenie wielu pinów zwykle powoduje powstanie quine. Tak więc mógłbym użyć prostej liczby, takiej11111...111
jak powtarzalna część mojej cyklicznej quine.Jednak, aby quine faktycznie przejechało, musimy przeprowadzić i wykonać nietrywialną „ładowność”. Najprostszym quine GolfScript, jakie mogłem wymyślić, jest to:
Tak więc moim planem było poprzedzenie takiego quinu powtarzalną stałą numeryczną i użycie ładunku, który odcina jedną cyfrę od liczby i przenosi ją na koniec programu. Jeżeli wykrywa programu, że nie jest bez stałą numeryczną przed nim (w tym przypadku wartość poniżej niego na stosie będzie pusty łańcuch, zakładając, że żaden sygnał), to zamiast dołączana do stałej długości stałą numeryczną z przodu samo.
Jest jednak jeszcze jedna zmarszczka - podczas „owijania się” ładunek musi także tłumić wynik liczby po sobie. Zwykle po zakończeniu programu GolfScript wszystkie wartości na stosie są automatycznie drukowane, co stanowiłoby problem.
Jednak okazuje się, że istnieje nieudokumentowany sposób (AFAIK), aby tego uniknąć: interpreter faktycznie wywołuje predefiniowaną funkcję w
puts
celu wykonania wydruku, więc ponowne zdefiniowanie tej funkcji jako braku operacji pomija automatyczne wyjście. Oczywiście oznacza to również, że musimy najpierw wezwaćputs
się do wydrukowania części stosu, którą chcemy wydrukować.Ostateczny kod wygląda dość niechlujnie (nawet dla GolfScript), ale przynajmniej działa. Podejrzewam, że mogą istnieć pewne sprytne sposoby, o których jeszcze nie myślałem, aby obniżyć ładunek o kilka znaków, ale w tej wersji koncentrowałem się głównie na asymptotycznym wyniku.
źródło
puts{}:puts
, chociaż mogłem zobaczyć argument{print}:puts
na tej podstawie, że nowa linia w wynikach oznaczałaby, że nie jest to wyłącznie cykliczne.]puts{}:puts
Jest potrzebny do owijania od{STUFF}.~111111111
do111111111{STUFF}.~
, w przeciwnym razie liczba1
s na końcu programu wciąż rośnie. ({}
Wydaje się to jednak niepotrzebne; najwyraźniej interpreter GolfScript pozwala na przypisanie z pustego stosu.)HTML, minus nieskończoność (prawie)
-2
AA
-10
AAAAAAAAAA
I tak dalej ... Jeśli ktoś powie, że to oszustwo, możemy się o to kłócić, ale znalazłem dziurę w pytaniu :)
Więc chyba wszyscy rozumieją, że kod ma, nie ma pętli, więc najdłuższa jest pętla,
0
a biorąc pod uwagę długość programun
, wynik ton / (0 - 1)
lub-n
, mogę napisać program, który man
równie dużą dodatnią liczbę całkowitą, ale jest bezużyteczny, ponieważ wszyscy go rozumieją.źródło