Latar belakang: angka Ramsey memberikan jumlah minimum simpul dalam grafik lengkap sehingga pewarnaan tepi merah / biru memiliki setidaknya satu merah atau satu biru . Batas untuk lebih besar sangat sulit untuk ditetapkan. $R(r,s)$ $v$ $K_v$ $K_v$ $K_r$ $K_s$ $r, s$

Tugas Anda adalah menampilkan angka untuk . $R(r,s)$ $1 \le r,s \le 5$

Memasukkan

Dua bilangan bulat dengan dan . $r, s$ $1 \le r \le 5$ $1 \le s \le 5$

Keluaran

$R(r,s)$ seperti yang diberikan dalam tabel ini:

  s   1    2    3    4      5
r +--------------------------
1 |   1    1    1    1      1
2 |   1    2    3    4      5
3 |   1    3    6    9     14
4 |   1    4    9   18     25
5 |   1    5   14   25  43-48

Perhatikan bahwa dan dapat dipertukarkan: . $r$ $s$ $R(r,s) = R(s,r)$

Untuk Anda dapat mengeluarkan bilangan bulat apa pun antara dan , inklusif. Pada saat pertanyaan ini diposting, ini adalah batasan yang paling dikenal. $R(5,5)$ $43$ $48$

code-golf integer graph-theory qwr
sumber

Saya pikir (bahkan dengan kisaran untuk 5,5) bahwa ini mungkin cocok di bawah kolmogorov-kompleksitas (atau apakah hanya input-non, input tetap cocok?)

Jonathan Allan

Kapan 49 dikecualikan untuk R (5,5)? (Saya tidak menantang; Sepertinya saya melewatkan kertas setelah karya Exoo dan McKay dan Radziszowski.)

Eric Towers

1

@EricTowers arxiv.org/abs/1703.08768

qwr

@ qwr: Terima kasih! Saya menikmatinya sejauh ini.

Eric Towers

7

JavaScript (ES6), 51 49 byte

Mengambil input dalam sintaks currying (r)(s).

r=>s=>--r*--s+[9,1,,13,2,,3,27,6][r<2|s<2||r*s%9]

Cobalah online!

Bagaimana?

Sebagai perkiraan pertama, kami menggunakan rumus:

(r - 1) (s - 1)

$(r-1)(s-1)$

 0  0  0  0  0
 0  1  2  3  4
 0  2  4  6  8
 0  3  6  9 12
 0  4  8 12 16

Jika kita memiliki , kita cukup menambahkan : $\min(r,s)<3$ $1$

 1  1  1  1  1
 1  2  3  4  5
 1  3  -  -  -
 1  4  -  -  -
 1  5  -  -  -

Jika tidak, kami menambahkan nilai yang diambil dari tabel pencarian yang key- nya didefinisikan oleh: $k$

k = (r - 1) (s - 1) mod 9

$k=(r-1)(s-1)\bmod9$

 k:                    table[k]:           (r-1)(s-1):         output:
 -  -  -  -  -         -  -  -  -  -       -  -  -  -  -       -  -  -  -  -
 -  -  -  -  -         -  -  -  -  -       -  -  -  -  -       -  -  -  -  -
 -  -  4  6  8   -->   -  -  2  3  6   +   -  -  4  6  8   =   -  -  6  9 14
 -  -  6  0  3         -  -  3  9 13       -  -  6  9 12       -  -  9 18 25
 -  -  8  3  7         -  -  6 13 27       -  -  8 12 16       -  - 14 25 43

Arnauld
sumber

Bagus, Dua baris pertama adalah ekspresi yang rapi.

qwr

5

JavaScript (Node.js) , 56 55 byte

f=(x,y)=>x<2|y<2||f(x,y-1)+f(x-1,y)-(x*y==12)-7*(x+y>8)

Cobalah online! Saya perhatikan bahwa tabelnya menyerupai segitiga Pascal tetapi dengan faktor koreksi. Sunting: Disimpan 1 byte berkat @sundar.

Neil
sumber

1

Yap, identitas segitiga Pascal berasal dari batas atas sederhana pada angka Ramsey (lihat posting Jonathan Allan)

qwr

1

Anda dapat menyimpan penggantian 1 byte x*y>19dengan x+y>8.

sundar - Reinstate Monica

@sundar Terima kasih, solusi asli saya adalah 50 byte sebelum saya menyadari bahwa pengindeksan saya salah dan saya lupa mencoba golf lagi setelah saya memperbaikinya.

Neil

4

Jelly , 17 16 byte

’ScḢƊ_:¥9“ ı?0‘y

Cobalah online! Atau lihat test-suite .

Ganti 0dengan +, ,, -, ., atau /untuk set sama dengan , , , , atau masing-masing (bukan di sini). $R(5,5)$ $43$ $44$ $45$ $46$ $47$ $48$

Bagaimana?

Karena kita mungkin menemukan bahwa: $R(r,s)\leq R(r-1,s)+R(r,s-1)$

R (r, s) \leq (\binom{r + s - 2}{r - 1})

$R(r,s)\leq \binom{r+s-2}{r-1}$

Ini ’ScḢƊdan akan menghasilkan:

 1  1  1  1  1
 1  2  3  4  5
 1  3  6 10 15
 1  4 10 20 35
 1  5 15 35 70

Jika kita kurangi satu untuk setiap kali sembilan masuk ke hasil, kita selaraskan tiga lagi dengan tujuan kita (ini dicapai dengan _:¥9):

 1  1  1  1  1
 1  2  3  4  5
 1  3  6  9 14
 1  4  9 18 32
 1  5 14 32 63

$32$ $63$ y“ ı?0‘y

’ScḢƊ_:¥9“ ı?0‘y - Link: list of integers [r, s]
’                - decrement              [r-1, s-1]
    Ɗ            - last 3 links as a monad i.e. f([r-1, s-1]):
 S               -   sum                  r-1+s-1 = r+s-2
   Ḣ             -   head                 r-1
  c              -   binomial             r+s-2 choose r-1
        9        - literal nine
       ¥         - last 2 links as a dyad i.e. f(r+s-2 choose r-1, 9):
      :          -   integer division     (r+s-2 choose r-1)//9
     _           -   subtract             (r+s-2 choose r-1)-((r+s-2 choose r-1)//9)
         “ ı?0‘  - code-page index list   [32,25,63,48]
               y - translate              change 32->25 and 63->48

Jonathan Allan
sumber

Jika Anda dapat mengaturnya ke nomor apa pun saya sarankan 43 sebagai dugaan oleh McKay, Radziszowski dan Exoo;)

qwr

2

Python 2 , 62 byte

def f(c):M=max(c);u=M<5;print[48,25-u*7,3*M+~u-u,M,1][-min(c)]

Cobalah online!

Python 2 , 63 byte

def f(c):M=max(c);print[48,M%2*7+18,3*~-M+2*(M>4),M,1][-min(c)]

Cobalah online!

Ini konyol, saya akan segera menyesal memposting ini ... Tapi eh, ¯ \ _ (ツ) _ / ¯. Dicukur 1 byte berkat Jonathan Allan kami yang baik :). Mungkin akan kalah oleh sekitar 20 byte segera ...

Tuan Xcoder
sumber

Jawaban Porting Arnauld's JS masih 62 byte .

Tn. Xcoder

2

Julia 0.6 , 71 61 59 57 byte

A->((r,s)=sort(A);r<3?s^~-r:3r+(s^2-4s+3)*((r==s)+r-2)-3)

Cobalah online!

Tidak digabungkan (well, sedikit lebih mudah dibaca):

function f_(A)
  (r, s) = sort(A)

  if r < 3
    result = s^(r-1)
  else
    result = 3*r + 
               (s^2 - 4*s + 3) * ((r == s) + r - 2) -
               3
  end

  return result
end

Apa fungsinya?

Mengambil input sebagai larik yang Amengandung r dan s. Buka paket array ke r dan s dengan angka lebih kecil sebagai r, menggunakan (r,s)=sort(A).

Jika r adalah 1, output harus 1. Jika r adalah 2, output harus menjadi apa pun s.
$s^{r - 1}$ akan $s^0 = 1$ untuk r = 1, dan $s^1 = s$ untuk r = 2.
Jadi, r<3?s^(r-1)atau lebih pendek,r<3?s^~-r

Untuk yang lain, saya mulai dengan memperhatikan bahwa outputnya adalah:

untuk r = 3, $2\times3 + [0, 3, 8]$ (untuk s = 3, 4, 5 masing-masing).
untuk r = 4, $2\times4 + \ \ [10, 17]$ (untuk s = 4, 5 masing-masing)
untuk r = 5, $2\times5 + \ \ \ \ \ [35]$ (untuk s = 5)

(Saya awalnya bekerja dengan f (5,5) = 45 untuk kenyamanan.)

Ini tampak seperti pola yang berpotensi digunakan - mereka semua memiliki 2rkesamaan, 17 adalah 8 * 2 + 1, 35 adalah 17 * 2 + 1, 10 adalah 3 * 3 + 1. Saya mulai dengan mengekstraksi nilai dasar dari [0, 3, 8], karena [0 3 8][s-2](ini kemudian menjadi lebih pendek (s^2-4s+3)).

Mencoba untuk mendapatkan nilai yang benar untuk r = 3, 4, dan 5 dengan ini melewati banyak tahap, termasuk

2r+[0 3 8][s-2]*(r>3?3-s+r:1)+(r-3)^3+(r>4?1:0)

dan

2r+(v=[0 3 8][s-2])+(r-3)*(v+1)+(r==s)v

Memperluas yang terakhir dan menyederhanakannya menyebabkan kode yang diposting.

sundar - Pasang kembali Monica
sumber

2

x86, 49 37 byte

Tidak terlalu dioptimalkan, hanya mengeksploitasi properti dari tiga baris pertama tabel. Ketika saya sedang menulis ini, saya menyadari bahwa kode ini pada dasarnya adalah tabel lompat sehingga tabel lompat dapat menghemat banyak byte. Input eaxdan ebx, keluaran eax.

-12 dengan menggabungkan kasus r >= 3menjadi tabel pencarian (awalnya hanya r >= 4) dan menggunakan saran Peter Cordes dari cmp/ jae/ jnedengan bendera masih diatur sehingga r1,r2,r3hanya dibedakan oleh satu cmp! Juga mengindeks ke tabel dengan cerdas menggunakan offset konstan.

start:
        cmp     %ebx, %eax
        jbe     r1
        xchg    %eax, %ebx              # ensure r <= s

r1:
        cmp     $2, %al             
        jae     r2                      # if r == 1: ret r
        ret

r2:     
        jne     r3                      # if r == 2: ret s 
        mov     %ebx, %eax
        ret

r3:
        mov     table-6(%ebx,%eax),%al  # use r+s-6 as index
        sub     %al, %bl                # temp = s - table_val
        cmp     $-10, %bl               # equal if s == 4, table_val == 14
        jne     exit
        add     $4, %al                 # ret 18 instead of 14 

exit:
        ret                        

table:
        .byte   6, 9, 14, 25, 43

Hexdump

00000507  39 d8 76 01 93 3c 02 73  01 c3 75 03 89 d8 c3 8a  |9.v..<.s..u.....|
00000517  84 03 21 05 00 00 28 c3  80 fb f6 75 02 04 04 c3  |..!...(....u....|
00000527  06 09 0e 19 2b                                    |....+|

qwr
sumber

2

Jangan terlalu yakin meja lompat akan optimal. r1: cmp $2, %alSaya jae r2akan mengatur flag sehingga Anda dapat menggunakannya r2: jne r3tanpa yang lain cmp. Target lompat di r1bisa berupa rettempat lain, dan jatuh ke r2. (Membalikkan kondisinya). BTW, ini adalah pertanyaan kode-golf pertama yang saya lihat setelah menjawab pertanyaan pendek penggunaan tabel offset lompatan SO Anda. Saya kira saya memilih yang tepat dari HNQ :)

Peter Cordes

1

r4dapat menjadi salah satu instruksi: mov table-8(%ebx,%eax), %al. IDK mengapa Anda menggunakan instruksi terpisah untuk memindahkan alamat tabel ke dalam register. Tetapi salah satu hal utama adalah bahwa offset konstan dari simbol tidak memerlukan biaya tambahan karena sudah berkumpul ke alamat absolut 32-bit. Format file objek dapat mewakili referensi simbol dengan offset ketika linker mengisi alamat akhir sehingga kompiler tidak harus meletakkan label terpisah pada setiap bidang struct, atau setiap elemen array ...

Peter Cordes

@PeterCordes Aku bahkan tidak menyadari ini membuat HNQ. Dan ya untuk beberapa alasan saya pikir alamat tabel harus dalam register sebelum menyadari bahwa saya salah sintaks. Saya memperbaikinya di sini codegolf.stackexchange.com/a/168503/17360 yang hanya merupakan tabel pencarian. Tapi saya tidak tahu tentang offset konstan yang berguna. Saya pikir saya akan mencoba tabel untuk 3 baris terakhir bukan perkalian.

qwr

1

Catatan untuk diri sendiri: masih dimungkinkan untuk menyimpan 1 byte dengan menggunakan satu retuntuk r1 dan r2.

qwr

1

Pembaruan bagus, terlihat bagus. Bagaimana jika Anda memindahkan mov %ebx, %eaxke exit, jadi selalu berjalan setelah r3, dan r2 melompat ke sana atau jatuh ke r3? Kemudian r3 menghasilkan hasilnya dalam BL dengan sub %bl, %al/ cmp $10, %al/ jne exit/ add $4, %bl(perubahan ukuran netral: cmp vs add dapat menggunakan al, bentuk pendek imm8). Keuntungannya adalah ia menghapus retr2 juga. Hmm tidak itu tidak berfungsi, mungkin mungkin jika Anda meniadakan entri tabel atau sesuatu? Dan itu mungkin sesuatu yang Anda butuhkan. Saya belum memikirkan hal ini dan sayangnya tidak punya waktu untuk melakukannya: /

Peter Cordes

1

Python 2 , 70 byte

f=lambda R,S:R<=S and[1,S,[6,9,14][S-3],[18,25][S&1],45][R-1]or f(S,R)

Cobalah online!

Chas Brown
sumber

1

MATL, 25 21 byte

+2-lGqXnt8/k-t20/k6*-

Cobalah di MATL Online

Mencoba untuk mengirim jawaban Jelly Jonathan Allan ke MATL.

+2-lGqXn - sama dengan jawaban itu: hitung $\binom{r+s-2}{r-1}$

t8/k - Gandakan itu, bagi dengan 8 dan lantai

- - kurangi itu dari hasil sebelumnya (Kami kurangi berapa kali 8 masuk dalam angka, bukannya 9 dalam jawaban Jelly. Hasilnya sama untuk semua kecuali 35 dan 70, yang di sini berikan 31 dan 62.)

t20/k - duplikat hasil itu juga, bagi dengan 20 dan lantai (memberi 0 untuk hasil yang sudah benar, 1 untuk 31, 3 untuk 62)

6* - kalikan dengan 6

- - kurangi itu dari hasil (31 - 6 = 25, 62 - 18 = 44)

Lebih tua:

+t2-lGqXntb9<Q3w^/k-t20>+

Cobalah di MATL Online

sundar - Pasang kembali Monica
sumber

0

Python 3 , 74 byte

lambda *a:[[1]*5,[2,3,4,5],[6,9,14],[18,25],[43]][min(a)-1][max(a)-min(a)]

Cobalah online!

Neil
sumber

0

Proton , 52 byte

Dekat-port jawaban Python saya .

c=>[48,(M=max(c))%2*7+18,3*M-(M>4?1:3),M,1][-min(c)]

Cobalah online!

Tuan Xcoder
sumber

0

Java 8, 62 byte

(r,s)->--r*--s+new int[]{9,1,0,13,2,0,3,27,6}[r<2|s<2?1:r*s%9]

Fungsi Lambda, port dari jawaban JavaScript Arnauld . Cobalah online di sini .

Java, 83 byte

int f(int x,int y){return x<2|y<2?1:f(x,y-1)+f(x-1,y)-(x*y==12?1:0)-7*(x+y>8?1:0);}

Fungsi rekursif, port dari jawaban JavaScript Neil . Cobalah online di sini .

Ketidakseimbangan
sumber

0

C (gcc), 57 byte

f(x,y){x=x<2|y<2?:f(x,y-1)+f(x-1,y)-(x*y==12)-7*(x+y>8);}

Fungsi rekursif, port dari jawaban JavaScript Neil . Cobalah online di sini .

C (gcc), 63 byte

f(r,s){r=--r*--s+(int[]){9,1,0,13,2,0,3,27,6}[r<2|s<2?:r*s%9];}

Port of Arnauld menjawab JavaScript . Cobalah online di sini .

Ketidakseimbangan
sumber

49 byte

ceilingcat

Bilangan Ramsey Kecil

Memasukkan

Keluaran

Jawaban:

JavaScript (ES6), 51 49 byte

Bagaimana?

JavaScript (Node.js) , 56 55 byte

Jelly , 17 16 byte

Bagaimana?

Python 2 , 62 byte

Python 2 , 63 byte

Julia 0.6 , 71 61 59 57 byte

Tidak digabungkan (well, sedikit lebih mudah dibaca):

Apa fungsinya?

x86, 49 37 byte

Python 2 , 70 byte

MATL, 25 21 byte

Python 3 , 74 byte

Proton , 52 byte

Java 8, 62 byte

Java, 83 byte

C (gcc), 57 byte

C (gcc), 63 byte