Progressões aritméticas da mesma cor

15

O teorema de Van der Waerden diz que

Para qualquer número inteiro positivo re k, existe um número Ntal que, se os números inteiros {1, 2, ..., N}forem coloridos, cada um com uma de r cores diferentes, haverá pelo menos knúmeros inteiros na progressão aritmética da mesma cor. O mínimo Né o número de Van der Waerden W(r, k).

Seu objetivo é calcular o número de Van der Waerden W(r, k)com entradas inteiras positivas re k. Menos bytes ganha.

Lembre-se de que essa função cresce extremamente rapidamente e consome muito tempo para calcular. Even W(4, 4)é desconhecido. Você pode supor que seu código seja executado em um computador ideal com recursos ilimitados (tempo, memória, profundidade da pilha, etc.). Teoricamente, seu código deve fornecer a resposta correta, mesmo para valores pelos quais a resposta não é conhecida.

Built-ins que calculam essa função não são permitidos.

Exemplo

Para r = 2cores e progressões de comprimento k = 3, existe uma 8sequência de comprimento que evita essa progressão, ou seja, 3elementos igualmente espaçados da mesma cor:

B R R B B R R B

Mas, não existe essa 9sequência de comprimento , então W(2, 3) == 9. Por exemplo,

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

contém a 3progressão aritmética da mesma cor mostrada.

Casos de teste

Você provavelmente só poderá testar casos pequenos.

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

Mostrar snippet de código

code-golf math sequence combinatorics subsequence xnor
fonte

Respostas:

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

É engraçado porque, ao longo do jogo, o programa ficou mais eficiente. Qualquer coisa além f(2,4)ou f(3,3)ainda leva uma eternidade, no entanto.

Explicação

A versão inicial verificou se uma sequência continha uma progressão de comprimento k, tentando todos os possíveis índices e etapas de início.

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

A versão golfed precisa apenas tentar todas as etapas possíveis, pois inclui novos elementos de sequência. O x*klimite é cuidar de casos como [0, 0, 1], que contêm uma progressão de comprimento 2, mas não satisfariam a verificação de exclusividade sem limite.

Quanto ao cheque

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

No primeiro passo da versão golf, quando Lestá vazio, len(L)é 0. Portanto, a segunda metade do orsempre será executada. Depois que ele Lestiver vazio, então {*L[:x*k:x]}(que é apenas para o Python 3.5 set(L[:x*k:x])) terá pelo menos um elemento.

Como L[:x*k:x]pode ter no máximo kelementos e para Lnão-vazio k*(*{*L[:x*k:x]},)possuir pelo menos kelementos, os dois só podem ser iguais quando houver exatamente kelementos em ambos. Para que isso aconteça {*L[:x*k:x]}deve ter exatamente um elemento, ou seja, temos apenas uma cor em nossa progressão.

Sp3000
fonte