Cykliczny układ znacznika jest bardzo małe, Turinga niepełny model obliczeniowy, składający się z dwóch alfabet symboli (będziemy używać {0,1}
) skończoną, liście niepusty cyklicznego produkcji , które składają się z tych dwóch symboli, a także nieograniczona słowo który również składa się z te dwa symbole.
Na każdym kroku:
- pierwszy element słowa jest usuwany
- jeśli tak,
0
obecna produkcja jest pomijana - jeśli tak, to
1
obecna produkcja jest dołączana na końcu słowa . - następna produkcja staje się aktywna. Jeśli to była ostatnia produkcja, wróć do pierwszej.
System zatrzymuje się, gdy słowo staje się puste.
Przykład (z Wikipedii):
Productions: (010, 000, 1111)
Initial word: 11001
Generation Production Word (before) Word (after)
0 010 11001 → 1001010
1 000 1001010 → 001010000
2 1111 001010000 → 01010000
3 010 01010000 → 1010000
4 000 1010000 → 010000000
5 1111 010000000 → 10000000
6 010 10000000 → 0000000010
7 000 0000000010 → 000000010
8 1111 000000010 → 00000010
9 010 00000010 → 0000010
Twoim zadaniem, jeśli zdecydujesz się go zaakceptować, jest napisanie programu lub funkcji, która wymaga:
- lista produkcji,
- początkowe słowo oraz
- generacja,
i drukuje lub zwraca słowo tego pokolenia.
Na przykład,
cyclic_tag(
prod=[[0,1,0],[0,0,0],[1,1,1,1]],
word=[1,1,0,0,1],
gen=4) => [1,0,1,0,0,0,0]
Szczegóły dotyczące wdrożenia:
Alfabet nie ma znaczenia. Możesz używać
0
i1
,True
iFalse
,T
iNIL
,A
aB
nawet1
a nawet0
cokolwiek innego możesz wymyślić, o ile jesteś konsekwentny. Wszystkie dane wejściowe i wyjściowe muszą używać tego samego alfabetu, a Ty musisz wskazać, do czego używasz0
i do czego1
.Długość słowa musi być teoretycznie nieograniczona. Oznacza to, że nie możesz zakodować na stałe maksymalnej długości słowa. Jeśli uruchomię twój program na idealnym komputerze z nieskończoną ilością pamięci, twój program musi teoretycznie być w stanie z niego skorzystać. (Możesz zignorować ograniczenia swojego tłumacza / kompilatora).
Jeśli dany system zatrzyma się przed osiągnięciem danego pokolenia, musisz zwrócić lub wydrukować puste słowo.
Pusta produkcja istnieje i musisz być w stanie sobie z nią poradzić. Jeśli napiszesz pełny program, twoje I / O również musi być w stanie go obsłużyć.
Edycja : Pierwotnie zamierzałem, aby generacja 0
była samym słowem wejściowym, a generacja 1
była wynikiem pierwszego kroku. To znaczy, chciałem, żebyś zwrócił kolumnę przed . Ponieważ jednak nie wyjaśniłem tego wystarczająco jasno, zaakceptuję obie opcje ; dla każdego pokolenia możesz zwrócić wartość w kolumnie przed lub po . Należy stwierdzić, że jesteś po po kolumnie, jeśli robisz tak. Musisz także zachować spójność w wybranej kolumnie.
Przyznam najmniejszy kod za tydzień od teraz (27.10.2014).
źródło
Odpowiedzi:
GolfScript (17–19 bajtów w zależności od formatu wejściowego i akceptowanego formatu wyjściowego)
18 bajtów:
Pobiera dane wejściowe w formularzu
[1 1 0 0 1] [[0 1 0] [0 0 0] [1 1 1 1]] 4
i podaje dane wyjściowe w formularzu[1 0 1 0 0 0 0]
. (Może być 17 bajtów bez ostatniego,`
jeśli dane wyjściowe1010000
są dopuszczalne).Demo online
19 bajtów:
Pobiera dane wejściowe w formularzu
"11001" ["010" "000" "1111"] 4
.Demo online
Sekcja
Kredytowej Martin Büttner „s rozwiązania CJam dla idei generowania listy produkcjach przez powtarzanie i obcięcia.
źródło
Haskell,
555351używa to
True
jako1
iFalse
jako0
. przykładowy bieg:źródło
CJam,
313028272418 bajtówDefiniuje to blok (najbardziej zbliżony do funkcji), który oczekuje, że wejście znajdzie się na stosie w ten sposób
Będzie podobnie zostawić tablicę
0
s oraz1
s na stosie.Sprawdź to tutaj. Wklej wejście w pierwszym wierszu, kod w trzecim wierszu i dołącz a,
~
aby faktycznie ocenić blok. Na przykładJeśli dane wyjściowe nie muszą mieć takiej samej postaci jak dane wejściowe
Wyjaśnienie:
Ostateczny stan słowa jest pozostawiony na stosie.
Dzięki Peter Taylor za ponowną wizytę.
źródło
l~{_,g{('1=@(:Pa+@@P*+}*}*\;
28 i wciąż istnieje możliwość ulepszeń (zwłaszcza(:P
części), ale czas na lunch:P
denerwuje mnie również: Dl~{_,g{(si@(:Pa+@@P*+}*}*\;
: 27 i po przyjrzeniu się,:P
jest faktycznie wydajny: P_,g
można również zastąpić_!!
takimi samymi bajtami._{...}{}?
wtedy użyć .Mathematica,
84 8077 znakówPrzykład:
źródło
Pyth 22
Wymaga wszystkich 3 argumentów jako osobnych danych wejściowych.
Przyjmuje argumenty takie jak:
Wyjaśnienie:
Python 2 - 61
67 91 105 124Ładna odpowiedź Joe Basic. Zakłada, że pusta produkcja jest
[[]]
.Dzięki @xnor za zwrócenie uwagi, że gra w golfa o 2 nad ranem to kiepska decyzja.
Dodatkowe podziękowania dla @xnor, któremu zawdzięczam 50% mojego wyniku.
Próba:
źródło
g and w
dlax
? Ponadto uważam, żeg*w
powinno działać, aby nadać prawdziwą wartość, gdy obag
są niezerowe iw
niepuste.if x else w
. Niex
zawsze będzie to prawdą, ponieważ ten kod jest uruchamiany tylkoif x
, czy coś mi brakuje?and
/or
p
n
c=lambda p,w,g:g*w and c(p[1:]+p[:1],w[1:]+w[0]*p[0],g-1)or w
JavaScript ES6 - 88 bajtów
Wygląda niesamowicie podobnie do odpowiedzi Fry'ego, która właśnie pojawiła się w mojej przeglądarce. (Bez kopiowania, uroczyście przysięgam.)
Wygląda jednak na to, że poszedł trasą tablicową, a ja trasą ciąg / wyrażenie regularne.
Rozszerzony:
Przykładowe dane wyjściowe
Teraz obserwuj, jak nadchodzą języki golfa i masakra nas obu. :RE
źródło
n
. Świetne umysły, prawda? : D