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.
źródło
1, możesz odjąć1wszystko, a następnie zapakować rozwiązanie dla tej odpowiedziK(). Przykład: Rozwiązanie dla2 -> 1jestK, więc rozwiązanie dla3 -> 2jestKK, rozwiązanie dla4 -> 3jestK(KK)itd.Odpowiedzi:
Haskell , wynik 5017
Łączy to najgłupszy możliwy algorytm eliminacji abstrakcji ((λ x . X ) = I; (λ x . Y ) = K y ; (λ x . M N ) = S (λ x . M N ) (λ x . N ) ) z optymalizatorem wizjera używanym po każdej aplikacji. Najważniejszą regułą optymalizacji jest S (K x ) (K y ) ↦ K ( xy ), która powstrzymuje algorytm przed wysadzaniem w sposób wykładniczy.
Zestaw reguł jest skonfigurowany jako lista par ciągów, dzięki czemu można łatwo bawić się nowymi regułami. Jako specjalny bonus ponownego użycia parsera wejściowego do tego celu, S, K i I są również akceptowane w kombinatorach wejściowych.
Reguły nie są bezwarunkowo stosowane; raczej zachowywane są zarówno stara, jak i nowa wersja, a wersje nieoptymalne są przycinane tylko wtedy, gdy ich długość przekracza długość najlepszej wersji o więcej niż pewną stałą (obecnie 3 bajty).
Wynik jest nieznacznie poprawiany przez traktowanie I jako podstawowego kombinatora, dopóki stopień wyjściowy nie przepisuje go do SKK. W ten sposób KI = K (SKK) można skrócić o 4 bajty do SK na wyjściu, nie myląc pozostałych optymalizacji.
Wypróbuj online!
Wynik
źródło
S (K x) (K y) = K (x y))?ruleStrings. Gdybyśmy tego nie zrobili, wynik byłby wykładniczo dłuższy: dla tego małego przykładu otrzymalibyśmy S (S (KS) (S (S (KS) (S (KK) (KS))) (S (S (KS) (S (KK) (KK))) (S (KK) (SKK))))) (S (S (KS) (S (S (KS) (S (KK) (KS))) ( S (S (KS) (S (KK) (KK))) (SK)))) (S (KK) (SK))) zamiast S (KS) K.Suma długości roztworów:
12945 85085872Kod Haskell, który pobiera linie wejściowe ze standardowego wejścia i nie dba o to, czy separatorem jest
=czy->:Implementuje ulepszoną abstrakcję nawiasów z sekcji 3.2 John Tromp: Binary Lambda Calculus and Combinatory Logic, która jest powiązana z artykułem Wikipedii na temat logiki kombinatorycznej. Najbardziej przydatne przypadki specjalne używają
Skombinatora tylko do przechwytywania subtermów w celu uniknięcia głębokiego zagnieżdżania zmiennych. Sprawa, która sprawdza równość niektórych podtermów, nie jest potrzebna dla żadnego z przypadków testowych. Chociaż nie ma specjalnego przypadku obsługiWkombinatora (patrz odpowiedź Piotra), reguły współdziałają w celu znalezienia krótszegoSS(SK)wyrażenia. (Najpierw popełniłem błąd, próbując zoptymalizować wewnętrzne wywołaniaabstract, a następnie taWoptymalizacja nie doszła do skutku, a ogólny wynik był o 16 bajtów dłuższy.)A oto wyniki z przypadków testowych:
źródło
8486 przy użyciu S, K, I, W
Wyjaśnienie
Standardowy algorytm (jak opisano na przykład w rozdziale 18 MOCK przedrzeźniacz ) wykorzystuje cztery przypadki, odpowiadających złożone jest
S,K,I = SKKi proste lewej związek. Myślę, że to właśnie realizuje odpowiedź Christiana. Jest to wystarczające, ale niekoniecznie optymalne, a ponieważ wolno nam na stałe zakodować do 10 kombinacji, pozostawia 7 opcji.Inne znane kombinatory kombinatoryczne to
które wraz z
K, wykonać pełną podstawę . W SK są toi
SKIreguły wywodzą te same wyrażenia dlaBiC, ale dlaWwywodząS S (K (S K K)). Dlatego postanowiłem wdrożyćWjako specjalny przypadek.Program (CJam)
Zestaw testów online
Wygenerowane wyniki:
źródło