Chodzi tutaj o stworzenie niemal powtarzalnego wzoru. Oznacza to, że konstruowana sekwencja zmienia się w ostatniej chwili, aby uniknąć powtórzenia się niektórych podsekwencji. Należy unikać następstw typu AA i ABA (gdzie B nie jest dłuższy niż A).

Przykłady:

Zacznę od listy wszystkich małych przykładów, aby mój opis był jaśniejszy. Zacznijmy od 0.

Ważne: 0

Nieprawidłowy: 00 (wzór AA)
Ważne: 01

Nieprawidłowy: 010 (wzór ABA)
Nieprawidłowy: 011 (wzór AA)
Ważne: 012

Ważne: 0120
Nieprawidłowy: 0121 (wzór ABA)
Nieprawidłowy: 0122 (wzór AA)

Nieprawidłowy: 01200 (wzór AA)
Nieprawidłowy: 01201 (wzór ABA; 01-2-01)
Nieprawidłowy: 01202 (wzór ABA)
Ważne: 01203

Teraz mocno wierzę, że a 4nigdy nie jest potrzebne, chociaż nie mam dowodu, ponieważ z łatwością znalazłem sekwencje setek znaków, które używają tylko 0123. (Prawdopodobnie jest to ściśle związane z tym, jak potrzebne są tylko trzy znaki, aby mieć nieskończone ciągi znaków, które nie mają żadnych wzorców AA. Jest tam strona Wikipedii .)

Wejście wyjście

Dane wejściowe to pojedyncza, dodatnia, niezerowa liczba całkowita n. Możesz to założyć n <= 1000.

Dane wyjściowe to nsekwencja -znakowa bez podsekwencji pasujących do wzorca zabronionego (AA lub ABA).

Przykładowe wejścia i wyjścia

>>> 1
0

>>> 2
01

>>> 3
012

>>> 4
0120

>>> 5
01203

>>> 50
01203102130123103201302103120132102301203102132012

Zasady

• Dozwolone 0123są tylko postacie .
• B nie jest dłużej niż A. Ma to na celu uniknięcie sytuacji, w której 012345musi być przestrzegana przez 6ponieważ 0123451ma to: 1-2345-1. Innymi słowy, sekwencja byłaby trywialna i nieciekawa.
• nmogą być wprowadzane dowolną pożądaną metodą, z wyjątkiem kodowania na stałe.
• Dane wyjściowe mogą być listą lub łańcuchem, w zależności od tego, co jest łatwiejsze.
• Bez brutalnej siły ; czas pracy powinien być rzędu minut, najwyżej godziny na naprawdę wolnej maszynie n=1000. (Ma to na celu zdyskwalifikowanie rozwiązań, które po prostu przechodzą przez npermutacje na całej długości {0,1,2,3}, dzięki czemu lewy i podobne lewy są niedozwolone).
• Standardowe luki są jak zwykle niedozwolone.
• Punktacja jest w bajtach. To jestgolf-golf, więc wygrywa najkrótszy wpis (prawdopodobnie - patrz bonus).
• Bonus: wybierz najniższą dozwoloną cyfrę na każdym kroku. Jeśli 1i 3są możliwe opcje dla następnej cyfry w sekwencji, wybierz 1. Odejmij 5 bajtów od swojego wyniku. Zwróć jednak uwagę na notatkę poniżej.

Uwaga!

Ślepe zaułki są możliwe. Twój program lub funkcja musi tego unikać. Oto przykład:

Kikut: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012031023013201221
Kikut: 0120310213012310320130210312013210230120310213201230210312013023103201230213203102301203210231201302103123013203102130120321023013203123021032012310213012031023013201221
Kikut: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102312013021031230132031021301203210230132031230210320123102130120310230132012
Kikut: 01203102130123103201302103120132102301203102132012302103120130231032012302132031023012032102312013021031230132031021301203210230132031230210320123102130120310230132031010

Każda z tych sekwencji nie może być dalej przedłużana (bez użycia a 4). Ale zauważ też, że istnieje zasadnicza różnica między pierwszymi dwoma a drugimi dwoma. Zastąpię początkową podsekwencję literą, Xaby to było jaśniejsze.

Kikut: X2130120
Kikut: X2130123
Kikut: X320
Kikut: X321301203102130

Dwie ostatnie cyfry Xto 10, więc jedynymi możliwymi opcjami dla następnej cyfry są 2i 3. Wybór 2prowadzi do sytuacji, w której sekwencja musi się zakończyć. Chciwy algorytm tu nie zadziała. (W każdym razie nie bez powrotu).

Siatkówka , 86 bajtów - 5 = 81

$
_
(r`^(?<-2>.)+_((.)+)\b$
$1!
\b$
0
3#
#
0#
1
1#
2
2#
3
)r`\1(?<-2>.)*((.)+)$
$0#
!
<empty>

Gdzie <empty>oznacza pustą linię końcową. Możesz uruchomić powyższy kod z jednego pliku z -sflagą.

Wkład powinien być podany jednogłośnie , np 111111. Nie testowałem go jeszcze pod kątem wydajności rzędu tysięcy - dwa wyrażenia regularne mogą po chwili nieco zwolnić - ale może z łatwością obsłużyć kilkaset w kilka sekund.

Wyjaśnienie

Jest to proste rozwiązanie do cofania.

1. Dołącz a 0.
2. Podczas gdy bieżąca sekwencja jest nieprawidłowa, usuń wszystkie końcowe 3s i zwiększaj ostatnią inną niż 3.
3. Powtarzaj, aż uzyskamy prawidłową sekwencję o pożądanej długości.

Cofanie jest realizowane przez pętlę podstawień wyrażeń regularnych, które przerywają, gdy łańcuch pozostanie niezmieniony przez jedną iterację.

$
_

Dodaje to _do wejścia, które służy do oddzielenia jednoargumentowego wejścia od sekwencji, którą budujemy.

(r`^(?<-2>.)+_((.)+)\b$
$1!

Jest to pierwsze podstawienie w pętli (wskazane przez wiodące (). Wyrażenie regularne pasuje, jeśli a) na końcu łańcucha znajduje się znak słowa (tj. Cyfra) (co oznacza, że ​​łańcuch jest prawidłowy - zobaczymy poniżej, że niepoprawne sekwencje są oznaczone znakiem końcowym #) i b) istnieją co najmniej tyle znaków w sekwencji, co na wejściu (jest to sprawdzane za pomocą grup równoważących ). W takim przypadku usuwamy dane wejściowe i dodajemy !. To !służy do wykonywania wszystkich Wyrażenia regularne w pętli nie, tak, że kończy.

\b$
0

Jeśli na końcu znajduje się znak słowa (tzn. Sekwencja jest poprawna, a pętla nie została zakończona w poprzednim kroku), dodaj a 0.

3#
#

Jeśli (zamiast tego) sekwencja została oznaczona jako niepoprawna i zakończyła się w 3, usuwamy ją 3(ale pozostawiamy sekwencję jako niepoprawną, ponieważ nie ma możliwej kontynuacji dla bieżącego prefiksu ... więc następny znak również musi zostać cofnięty).

0#
1
1#
2
2#
3

Jeśli sekwencja jest oznaczona jako niepoprawna, a dowolna cyfra inna niż 3na końcu, zwiększamy cyfrę i usuwamy znacznik.

)r`\1(?<-2>.)*((.)+)$
$0#

Ostatnie podstawienie w pętli (wskazane przez )). Sprawdza, czy ciąg się kończy ABA(gdzie Bnie jest dłuższy niż, Aale potencjalnie pusty). Względne długości Ai Bsą ponownie sprawdzane za pomocą grup równoważących, a powtarzanie Ajest sprawdzane za pomocą prostego odwołania wstecznego.

Jeśli to wyrażenie regularne pasuje, oznaczamy sekwencję jako niepoprawną, dodając #.

!
<empty>

Gdy pętla się kończy, wszystko, co musimy zrobić, to usunąć !i pozostawia się z pożądanym wyjściem.

Python 2, 175-5 = 170 bajtów

n=input();s='';u=j=-1
while n>len(s):
 while u>2:u=int(s[0]);s=s[1:]
 u+=1;t=`u`+s;m=c=0
 while t[c:]*0**m:c+=1;i=t[c:].find(t[:c]);m=j<i<=c
 if c>=len(t):s=t;u=j
print s[::j]

To jest chciwy algorytm z cofaniem. Chciałbym, żeby były krótsze. Mam nadzieję, że jest poprawny (patrz poniżej).

Buduje ciąg po jednej cyfrze na raz. Biorąc pod uwagę ciąg dcyfr, który już znalazł, próbuje dołączyć 0jako (d+1)cyfrę st. Jeśli to nie zadziała, wtedy spróbuje a 1, a 2następnie a 3. Jeśli żadna z tych funkcji nie działa, to wraca do dcyfry th i zwiększa ją (jeśli jest mniejsza niż 3) lub usuwa ją (jeśli jest równa 3, w którym to przypadku zwiększa poprzednią cyfrę itp.).

Sprawdzenie ważności jest linią z .findnim. Jeśli ktoś zdecyduje się przeczytać mój kod, powinienem powiedzieć, że ten program faktycznie przechowuje ciąg znaków wstecz, co oznacza, że ​​dodaje cyfry z przodu . Sprawdzanie polega więc na szukaniu miejsc, w których pierwsze c cyfry pojawiają się ponownie później w ciągu (w cdowolnym miejscu po pierwszych cyfrach), a jeśli są takie miejsca, to czy długość pośrednia jest co najwyżej c.

(Oczywiście odwraca ciąg przed drukowaniem.)

Mogłoby to również być szybsze; Początkowo miałem wcześniej wychodzić z różnych pętli w celu zwiększenia wydajności, ale to kosztowało cenne bajty. n=1000Jednak nadal działa OK w zakresie .

W każdym razie program wydaje się preferować mniejsze cyfry, ale nie jest to bardzo silna preferencja. Na przykład uruchomienie go za pomocą n=2000dało mi ciąg z 523zerami, 502jedynymi, 497dwójkami i 478trójkami, kończącymi się na 30210312013021. Więc jeśli ktoś inny pracuje nad chciwym algorytmem, być może może potwierdzić ten wynik. Lub z n=1000dostałem [263, 251, 248, 238]do zliczeń cyfrowo.

Na koniec chciałbym wspomnieć, że te liczby sugerują symetrię, prawie (choć nie do końca) tak, jakbyśmy zaczęli od jednolitego rozkładu, a następnie przekonwertowali niektóre 3„na 0”, a niektóre 2„na 1” s. Ale oczywiście może to być zbieg okoliczności. Nie mam pojęcia!

Haskell, 115 (120 bajtów - 5 bonusów)

x?_|or[t x==t(drop i x)|i<-[1..length x],t<-[take$div(i+1)2]]=[]
x?0=[x]
x?n=(?(n-1)).(:x)=<<"0123"
f=reverse.head.([]?)

Uruchom online w Ideone

Przykładowy przebieg:

*Main> f 40
"0120310213012310320130210312013210230120"