Progresi aritmatika dengan warna yang sama

15

Teorema Van der Waerden mengatakan itu

Untuk bilangan bulat positif yang diberikan rdan k, ada beberapa angka Nsehingga jika bilangan bulat {1, 2, ..., N}berwarna, masing-masing dengan r warna yang berbeda, maka setidaknya ada kbilangan bulat dalam perkembangan aritmatika semua warna yang sama. Yang paling sedikit Nadalah nomor Van der Waerden W(r, k).

Tujuan Anda adalah menghitung angka Van der Waerden yang W(r, k)diberi input bilangan bulat positif rdan k. Bytes paling sedikit menang.

Berhati-hatilah karena fungsi ini tumbuh sangat cepat dan menghabiskan waktu untuk menghitung. Bahkan W(4, 4)tidak diketahui. Anda dapat mengasumsikan kode Anda berjalan pada komputer ideal dengan sumber daya tak terbatas (waktu, memori, kedalaman tumpukan, dll). Kode Anda secara teoritis harus memberikan jawaban yang benar bahkan untuk nilai yang jawabannya tidak diketahui.

Built-in yang menghitung fungsi ini tidak diizinkan.

Contoh

Untuk r = 2warna dan progresi panjang k = 3, ada 8urutan panjang yang menghindari progresi seperti itu, yaitu 3elemen dengan spasi sama dengan warna yang sama:

B R R B B R R B

Tapi, tidak ada 9urutan panjang seperti itu , jadi W(2, 3) == 9. Contohnya,

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

berisi 3progresi aritmatika dengan warna yang sama panjangnya dengan yang ditunjukkan.

Uji kasus

Anda mungkin hanya dapat menguji kasus-kasus kecil.

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

Tampilkan cuplikan kode

code-golf math sequence combinatorics subsequence Tidak
sumber

Jawaban:

7

Python 3.5, 125 124 119 byte

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

Ini lucu karena, selama bermain golf ini, program sebenarnya menjadi lebih efisien. Apa pun di luar f(2,4)atau f(3,3)masih membutuhkan selamanya.

Penjelasan

Versi awal memeriksa apakah suatu urutan berisi perkembangan panjang kdengan mencoba semua indeks dan langkah awal yang mungkin.

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

Versi golf hanya perlu mencoba semua langkah yang mungkin karena ini menambahkan elemen urutan baru. The x*ktopi adalah untuk mengurus kasus-kasus seperti [0, 0, 1], yang berisi perkembangan panjang 2 tapi tidak akan memuaskan cek keunikan membuka tutup.

Adapun cek

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

Pada pass pertama dari versi golf, ketika Lkosong, len(L)adalah 0. Dengan demikian paruh kedua orakan selalu dieksekusi. Setelah itu Ltidak kosong, jadi {*L[:x*k:x]}(yang hanya Python 3.5 for set(L[:x*k:x])) akan memiliki setidaknya satu elemen.

Karena L[:x*k:x]dapat memiliki paling banyak kelemen dan untuk Lnon-kosong k*(*{*L[:x*k:x]},)memiliki setidaknya kelemen, keduanya hanya bisa sama ketika ada kelemen yang tepat di keduanya. Agar ini terjadi {*L[:x*k:x]}harus memiliki tepat satu elemen, yaitu kita hanya memiliki satu warna dalam perkembangan kita.

Sp3000
sumber