Wprowadzenie: Logika kombinacyjna
Logika kombinacyjna (CL) opiera się na rzeczach zwanych kombinatorami , które są w zasadzie funkcjami. Istnieją dwa podstawowe „wbudowane” kombinatory Si K, które zostaną wyjaśnione później.
Lewicowe skojarzenie
CL jest lewostronnie asocjatywny , co oznacza, że nawiasy (zawierające elementy) znajdujące się po lewej stronie innej pary nawiasów zawierających je można usunąć, po zwolnieniu elementów. Na przykład coś takiego:
((a b) c)
Można zredukować do
(a b c)
Gdzie (a b)jest po lewej stronie większego wspornika ((a b) c), aby można go było usunąć.
Znacznie większy przykład lewostronnego skojarzenia (wyjaśnienia w nawiasach kwadratowych):
((a b) c ((d e) f (((g h) i) j)))
= (a b c ((d e) f (((g h) i) j))) [((a b) c...) = (a b c...)]
= (a b c (d e f (((g h) i) j))) [((d e) f...) = (d e f...)]
= (a b c (d e f ((g h i) j))) [((g h) i) = (g h i)]
= (a b c (d e f (g h i j))) [((g h i) j) = (g h i j)]
Wsporniki można również zmniejszyć, gdy więcej niż jedna para owija te same obiekty. Przykłady:
((((a)))) -> a
a ((((b)))) -> a b
a (((b c))) -> a (b c) [(b c) is still a group, and therefore need brackets.
Note that this doesn't reduce to `a b c`, because
`(b c)` is not on the left.]
Wbudowane
CL ma dwa „wbudowane” kombinatory Si K, które mogą przełączać obiekty (pojedyncze kombinatory lub grupa kombinacji / grup owiniętych wokół nawiasów) w taki sposób:
K x y = x
S x y z = x z (y z)
Gdzie x, yi zmoże być stand-in do niczego.
Przykład Si Ksą następujące:
(S K K) x [x is a stand-in for anything]
= S K K x [left-associativity]
= K x (K x) [S combinator]
= x [K combinator]
Inny przykład:
S a b c d
= a c (b c) d [combinators only work on the n objects to the right of it,
where n is the number of "arguments" n is defined to have -
S takes 3 arguments, so it only works on 3 terms]
Powyższe są przykładami normalnych instrukcji CL, w których instrukcja nie może być dalej oceniana i osiąga wynik końcowy w skończonym czasie. Istnieją niestandardowe instrukcje (które są instrukcjami CL, które nie kończą się i będą podlegać ciągłej ocenie), ale nie mieszczą się w zakresie wyzwania i nie trzeba ich obejmować.
Jeśli chcesz dowiedzieć się więcej o CL, przeczytaj tę stronę w Wikipedii .
Zadanie:
Twoim zadaniem jest stworzenie dodatkowych kombinatorów, biorąc pod uwagę liczbę argumentów i to, co ocenia jako dane wejściowe, które podaje się w następujący sposób:
{amount_of_args} = {evaluated}
Gdzie {amount_of_args}jest dodatnią liczbą całkowitą równą liczbie argumentów i {evaluated}składa się z:
- argumenty do ilości argumentów, przy
1czym pierwszy argument,2drugi argument itd.- Masz gwarancję, że liczby argumentów powyżej ilości argumentów (więc
4kiedy{amount_of_args}jest tylko3), nie pojawią się w{evaluated}.
- Masz gwarancję, że liczby argumentów powyżej ilości argumentów (więc
- nawiasy klamrowe
()
Przykładami danych wejściowych są:
3 = 2 3 1
4 = 1 (2 (3 4))
Pierwszym wejściem jest prośba o kombinator (powiedzmy R) z trzema argumentami ( R 1 2 3), który następnie przekształca się w:
R 1 2 3 -> 2 3 1
Drugie wejście wymaga tego (z nazwą kombinacji A):
A 1 2 3 4 -> 1 (2 (3 4))
Ze względu na wejście w tym formacie, musisz wrócić ciąg S, Ka (), który po zastąpieniu nazwy combinator i biegać z argumentów, zwraca ten sam oceniany jako oświadczenie {evaluated}bloku, gdy blok poleceń jest podstawiony z powrotem do tej nazwy combinator.
Wyjściowa instrukcja kombinatora może mieć usunięte białe spacje i zewnętrzne nawiasy, więc (S K K (S S))można zamienić coś podobnego SKK(SS).
Jeśli chcesz przetestować wyjścia Twój program, @aditsu dokonał rachunek kombinatorów parsera (co obejmuje S, K, Ia nawet inne te lubią Bi C) tutaj .
Wynik:
Ponieważ jest to metagolf , celem tego wyzwania jest osiągnięcie jak najmniejszej możliwej liczby bajtów na wyjściu, biorąc pod uwagę te 50 przypadków testowych . Podaj swoje wyniki dla 50 przypadków testowych w odpowiedzi lub utwórz pastebin (lub coś podobnego) i opublikuj link do tego pastebinu.
W przypadku remisu wygrywa najwcześniejsze rozwiązanie.
Zasady:
- Twoja odpowiedź musi zwracać PRAWIDŁOWE wyjście - więc biorąc pod uwagę dane wejściowe, musi zwracać prawidłowe dane wyjściowe zgodnie z definicją w zadaniu.
- Twoja odpowiedź musi pojawić się w ciągu godziny na nowoczesnym laptopie dla każdego przypadku testowego.
- Wszelkie kodowanie rozwiązań jest niedozwolone. Możesz jednak zakodować na stałe do 10 kombinacji.
- Twój program musi za każdym razem zwracać to samo rozwiązanie dla tego samego wejścia.
- Twój program musi zwrócić poprawny wynik dla każdego podanego wejścia, a nie tylko przypadków testowych.
1, możesz odjąć 1wszystko, a następnie zapakować rozwiązanie dla tej odpowiedzi K(). Przykład: Rozwiązanie dla 2 -> 1jest K, więc rozwiązanie dla 3 -> 2jest KK, rozwiązanie dla 4 -> 3jest K(KK)itd.