Postępy arytmetyczne tego samego koloru

15

Twierdzenie Van der Waerdena mówi, że

Dla dowolnej dodatniej liczby całkowitej ri kistnieje pewna liczba Ntaka, że ​​jeśli liczby całkowite {1, 2, ..., N}są pokolorowane, każda z jednym w r innym kolorze, wówczas istnieją co najmniej kliczby całkowite w postępie arytmetycznym tego samego koloru. Najmniejszy Nto numer Van der Waerden W(r, k).

Twoim celem jest obliczenie liczby Van der Waerden na podstawie W(r, k)dodatnich liczb całkowitych ri k. Wygrywa najmniej bajtów.

Uwaga: ta funkcja rozwija się bardzo szybko i jest czasochłonna. Nawet W(4, 4)nie jest znany. Możesz założyć, że kod działa na idealnym komputerze z nieograniczonymi zasobami (czas, pamięć, głębokość stosu itp.). Twój kod musi teoretycznie dać prawidłową odpowiedź, nawet dla wartości, dla których odpowiedź nie jest znana.

Wbudowane funkcje obliczające tę funkcję są niedozwolone.

Przykład

Dla r = 2kolorów i progresji długości k = 3istnieje 8sekwencja długości , która pozwala uniknąć takiej progresji, tj. 3Równomiernie rozmieszczone elementy tego samego koloru:

B R R B B R R B

Ale nie ma takiej 9sekwencji długości, więc W(2, 3) == 9. Na przykład,

R B B R B R R B R
  ^     ^     ^

zawiera 3pokazany postęp arytmetyczny o tym samym kolorze.

Przypadki testowe

Prawdopodobnie będziesz mógł testować tylko małe przypadki.

+-----+-----+-----+-----+-----+-----+------+
|     | k=1 | k=2 | k=3 | k=4 | k=5 | k=6  |
+-----+-----+-----+-----+-----+-----+------+
| r=1 |   1 |   2 |   3 |   4 |   5 |    6 |
| r=2 |   1 |   3 |   9 |  35 | 178 | 1132 |
| r=3 |   1 |   4 |  27 | 293 |     |      |
| r=4 |   1 |   5 |  76 |     |     |      |
+-----+-----+-----+-----+-----+-----+------+

Pokaż fragment kodu

code-golf math sequence combinatorics subsequence xnor
źródło

Odpowiedzi:

7

Python 3.5, 125 124 119 bajtów

f=lambda r,k,*L:any(L[:x*k:x]==k*(*{*L[:x*k:x]},)for x in range(1,len(L)+1))*len(L)or max(f(r,k,i,*L)for i in range(r))

To zabawne, ponieważ w trakcie gry w golfa program stał się bardziej wydajny. Jednak wszystko, co trwa f(2,4)lub f(3,3)nadal trwa wiecznie.

Wyjaśnienie

Początkowa wersja sprawdziła, czy sekwencja zawierała postęp długości k, wypróbowując wszystkie możliwe wskaźniki i kroki początkowe.

def f(r,k,L=[]):
 for i in range(len(L)):
  for j in range(len(L)):
   if len(set(L[i::j+1]))==1 and len(L[i::j+1])==k:
    return len(L)
 return max(f(r,k,L+[i])for i in range(r))

Wersja grałem tylko musi wypróbować wszystkie możliwe kroki, ponieważ wstawia nowe elementy sekwencji. x*kCzapka jest, aby dbać o takich przypadkach [0, 0, 1], które zawiera progresji długości 2, ale nie spełniają wyjątkowość check nieograniczonej.

Co do czeku

L[:x*k:x]==k*(*{*L[:x*k:x]},)

Przy pierwszym przejściu wersji golfowej, gdy Ljest pusta, len(L)wynosi 0. W ten sposób druga połowa orzawsze będzie wykonywana. Po tym Ljest niepuste, więc {*L[:x*k:x]}(co jest po prostu Python 3.5 dlaset(L[:x*k:x]) ) będzie miał co najmniej jeden element.

Ponieważ L[:x*k:x]może mieć co najwyżej kelementy, a dla Lniepustych k*(*{*L[:x*k:x]},)ma co najmniej kelementy, dwa mogą być równe tylko wtedy, gdy kw obu znajdują się dokładnie elementy. Aby tak się stało, {*L[:x*k:x]}musi mieć dokładnie jeden element, tj. Mamy tylko jeden kolor w naszym postępie.

Sp3000
źródło