Quines kombinator

tło

Właśnie dowiedziałeś się, czym jest logika kombinacyjna . Zaintrygowani różnymi kombinatorami spędzasz sporo czasu na poznawaniu ich. W końcu natkniesz się na to szczególne wyrażenie:

(S I I (S I I))

Zauważasz, że gdy próbujesz zredukować go do normalnej postaci, zmniejsza się do siebie po trzech krokach:

(S I I (S I I))
= (I (S I I) (I (S I I)))  (1)
= (S I I (I (S I I)))      (2)
= (S I I (S I I))          (3)

Jesteś zdeterminowany, aby znaleźć inne wyrażenia, które mają tę cechę i natychmiast zacząć nad tym pracować.

Zasady

Możesz użyć dowolnej kombinacji następujących kombinacji:

B f g x = f (g x)
C f x y = f y x
I x     = x
K x y   = x
S f g x = f x (g x)
W f x   = f x x

Aplikacja pozostanie skojarzona, co oznacza, że (S K K)tak naprawdę jest ((S K) K).
Redukcja jest minimalna, nie ma innej kolejności kroków redukcji, która wykorzystuje mniej kroków. Przykład: jeśli xma redukcję y, wówczas poprawna minimalna redukcja (W f x)to:
```
(W f x)
= (W f y) (1)
= f y y   (2)
```
i nie
```
(W f x)
= f x x   (1)
= f y x   (2)
= f y y   (3) 
```
Obowiązują standardowe luki.

Zadanie

Cykl wyrażenia definiujemy jako minimalną liczbę redukcji pomiędzy tymi samymi wyrażeniami.

Twoim zadaniem jest znalezienie wyrażenia o liczbie używanych kombinatorów <100, co daje najdłuższy cykl.

Punktacja

Twój wynik zostanie określony na podstawie długości cyklu wyrażenia. Jeśli ekspresja dwóch osób ma ten sam cykl, wygrywa odpowiedź, która używa mniejszej liczby kombinacji. Jeśli oba używają tej samej liczby kombinacji, wygrywa wcześniejsza odpowiedź.

Powodzenia i miłej zabawy!

code-challenge quine busy-beaver ThreeFx
źródło

golf atomowy pasuje do twojego remisu, ale nie dodałbym tagu do remisu. Jeśli nie ma odpowiedniego znacznika, domyślnie jest to wyzwanie kodowe , które wskazuje, że wyzwanie wykorzystuje niestandardowe kryterium wygranej.

Martin Ender

Myślę, że pomogłoby to, gdybyś powiedział, jakie konwencje asocjatywne stosuje twoja notacja.

xnor

Cykl jak już zdefiniowane niekoniecznie jest dobrze zdefiniowany, ponieważ dany wyraz może mieć wielokrotne redukcje dostępne.

Peter Taylor

@ThreeFx, jesteś w błędzie. Np. Jeśli xma redukcję do ytego czasu W f x -> W f y -> f y ylub W f x -> f x x -> f x y -> f y ymają różne długości.

Peter Taylor

Teraz podstępem jest to, że ktoś nie może zdobyć wyniku tylko przez opublikowanie cyklu; potrzebują dowodu, że nie ma krótszej redukcji, co może być trudne obliczeniowo.

xnor

Odpowiedzi:

Zaczynam od czegoś

1:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

2:(((C I (C (C I) (W I))) (W I) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

3:(((I (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

4:(((W I) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

5:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

6:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

7:(((C I (C (C I) (W I))) (W I) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

8:(((I (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

9:(((W I) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

10:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

11:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

12:(((C I (C (C I) (W I))) (W I) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

13:(((I (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

14:(((W I) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

15:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

16:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

17:(((C I (C (C I) (W I))) (W I) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

18:(((I (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

19:(((W I) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

20:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

21:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

22:(((C I (C (C I) (W I))) (W I) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

23:(((I (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

24:(((W I) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

25:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

26:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

27:(((C I (C (C I) (W I))) (W I) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

28:(((I (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

29:(((W I) (C (C I) (W I)) I I) (W I) ((C I) (W (C I)) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

30:(((I (C (C I) (W I))) (C (C I) (W I)) I I) (W I) (I (W (C I)) (W (C I)) (W (C I))) ((W I) (W I) (W I) I))

31:(((C (C I) (W I)) (C (C I) (W I)) I I) (W I) (W (C I) (W (C I)) (W (C I))) ((I (W I)) (W I) (W I) I))

śmigać
źródło