Gleichfarbige arithmetische Folgen

15

Das sagt der Satz von Van der Waerden

Für alle gegebenen positiven Ganzzahlen rund kgibt es eine Nsolche Zahl , dass, wenn die Ganzzahlen {1, 2, ..., N}farbig sind, jede mit einer r anderen Farbe, es mindestens kGanzzahlen in arithmetischer Folge gibt, die alle die gleiche Farbe haben. Das geringste Nist die Van-der-Waerden-Zahl W(r, k).

Ihr Ziel ist es, die Van der Waerden-Zahl W(r, k)bei positiven Ganzzahleingaben rund zu berechnen k. Wenigste Bytes gewinnt.

Beachten Sie, dass diese Funktion extrem schnell wächst und in der Berechnung viel Zeit in Anspruch nimmt. Auch W(4, 4)ist unbekannt. Sie können davon ausgehen, dass Ihr Code auf einem idealen Computer mit unbegrenzten Ressourcen (Zeit, Speicher, Stapeltiefe usw.) ausgeführt wird. Ihr Code muss theoretisch die richtige Antwort auch für Werte geben, für die die Antwort nicht bekannt ist.

Built-Ins, die diese Funktion berechnen, sind nicht zulässig.

Beispiel

Für r = 2Farben und Längenverläufe k = 3gibt es eine Längenfolge 8, die ein solches Fortschreiten vermeidet, dh 3Elemente gleicher Farbe mit gleichem Abstand:

B R R B B R R B

Aber, gibt es keine solche längs- 9Sequenz, so W(2, 3) == 9. Zum Beispiel,

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

enthält den dargestellten Längen- 3und Farbverlauf.

Testfälle

Sie können wahrscheinlich nur kleine Fälle testen.

+-----+-----+-----+-----+-----+-----+------+
|     | 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 |     |     |      |
+-----+-----+-----+-----+-----+-----+------+

Code-Snippet anzeigen

code-golf math sequence combinatorics subsequence xnor
quelle

Antworten:

7

Python 3.5, 125 124 119 Bytes

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))

Es ist lustig , weil im Laufe dieses von Golf, das Programm tatsächlich bekam mehr effizient. Alles jenseits von f(2,4)oderf(3,3) noch ewig dauert.

Erläuterung

Die ursprüngliche Version überprüfte, ob eine Sequenz einen Längenverlauf enthielt, kindem alle möglichen Startindizes und -schritte ausprobiert wurden.

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))

Die Golfversion muss nur alle möglichen Schritte ausprobieren, da sie neuen Sequenzelementen vorangeht . Die x*kKappe soll sich um Fälle wie kümmern[0, 0, 1] , die eine Progression der Länge 2 enthalten, aber die Eindeutigkeitsprüfung ungekappt nicht erfüllen würden.

Wie für den Scheck

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

Beim ersten Durchgang der Golfversion ist, wenn Lleer, len(L)0. Somit orwird immer die zweite Hälfte von ausgeführt. Danach List nicht leer, also {*L[:x*k:x]}(das ist nur Python 3.5 fürset(L[:x*k:x]) ) mindestens ein Element hat.

Da L[:x*k:x]es höchstens kElemente geben kann und für LNicht-Leer k*(*{*L[:x*k:x]},)mindestens kElemente gibt, können die beiden nur dann gleich sein, wenn kin beiden Elementen genau Elemente vorhanden sind . Dazu {*L[:x*k:x]}muss genau ein Element vorhanden sein, dh wir haben nur eine Farbe in unserem Verlauf.

Sp3000
quelle