Progressions arithmétiques de même couleur

15

Le théorème de Van der Waerden dit que

Pour tout entier positif donné ret k, il existe un certain nombre Ntel que si les entiers {1, 2, ..., N}sont colorés, chacun avec une r couleur différente, alors il y a au moins des kentiers en progression arithmétique tous de la même couleur. Le moins tel Nest le nombre de Van der Waerden W(r, k).

Votre objectif est de calculer le nombre de Van der Waerden à partir d' W(r, k)entrées entières positives ret k. Le moins d'octets gagne.

Attention, cette fonction se développe extrêmement rapidement et prend beaucoup de temps à calculer. Même W(4, 4)est inconnu. Vous pouvez supposer que votre code s'exécute sur un ordinateur idéal avec des ressources illimitées (temps, mémoire, profondeur de pile, etc.). Votre code doit théoriquement donner la bonne réponse même pour les valeurs pour lesquelles la réponse n'est pas connue.

Les éléments intégrés qui calculent cette fonction ne sont pas autorisés.

Exemple

Pour les r = 2couleurs et les progressions de longueur k = 3, il existe une 8séquence de longueur qui évite une telle progression, c'est 3-à- dire des éléments également espacés de la même couleur:

B R R B B R R B

Mais, il n'y a pas une telle 9séquence de longueur , donc W(2, 3) == 9. Par exemple,

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

contient la 3progression arithmétique de la même couleur de longueur indiquée.

Cas de test

Vous ne pourrez probablement tester que de petits cas.

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

Afficher l'extrait de code

code-golf math sequence combinatorics subsequence xnor
la source

Réponses:

7

Python 3.5, 125 124 119 octets

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

C'est drôle parce que, au cours du golf, le programme est devenu plus efficace. Quoi que ce soit au f(2,4)- delà ou f(3,3)prend toujours une éternité, cependant.

Explication

La version initiale vérifiait si une séquence contenait une progression de longueur ken essayant tous les indices et étapes de démarrage possibles.

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

La version golfée n'a qu'à essayer toutes les étapes possibles car elle ajoute de nouveaux éléments de séquence. La x*kcasquette est destinée à prendre en charge des cas comme [0, 0, 1], qui contient une progression de longueur 2 mais ne satisferait pas au contrôle d'unicité non plafonné.

Quant au chèque

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

Lors de la première passe de la version golfée, quand Lest vide, len(L)est 0. Ainsi la seconde moitié du orsera toujours exécutée. Après que ce ne Lsoit pas vide, donc {*L[:x*k:x]}(qui n'est que Python 3.5 pour set(L[:x*k:x])) aura au moins un élément.

Puisque L[:x*k:x]peut avoir au plus des kéléments et pour Lnon-vide k*(*{*L[:x*k:x]},)a au moins des kéléments, les deux ne peuvent être égaux que lorsqu'il y a exactement des kéléments dans les deux. Pour que cela se produise, il {*L[:x*k:x]}doit avoir exactement un élément, c'est-à-dire que nous n'avons qu'une seule couleur dans notre progression.

Sp3000
la source