Справочная информация: число Рамсея дает минимальное количество вершин в полном графе , так что раскраска краев в красный / синий цвет имеет хотя бы один красный или один синий . Оценки для увеличения очень трудно установить. $R(r,s)$ $v$ $K_v$ $K_v$ $K_r$ $K_s$ $r, s$

Ваша задача - вывести число для . $R(r,s)$ $1 \le r,s \le 5$

вход

Два целых числа с и . $r, s$ $1 \le r \le 5$ $1 \le s \le 5$

Выход

как указано в этой таблице: $R(r,s)$

  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

Обратите внимание, что и являются взаимозаменяемыми: . $r$ $s$ $R(r,s) = R(s,r)$

Для вы можете вывести любое целое число от до включительно. На момент публикации этого вопроса это самые известные границы. $R(5,5)$ $43$ $48$

code-golf integer graph-theory qwr
источник

Я думаю (даже с диапазоном для 5,5), что это может подходить для колмогоровской сложности (или подходит только для ввода без фиксированного вывода?)

Джонатан Аллан

Когда 49 было исключено для R (5,5)? (Я не оспариваю; кажется, я пропустил газету после Экзоо, Маккея и Радзишовского.)

Эрик Тауэрс

1

@EricTowers arxiv.org/abs/1703.08768

18:30

@qwr: Спасибо! Я наслаждаюсь этим до сих пор.

Эрик Тауэрс,

7

JavaScript (ES6), 51 49 байт

Принимает ввод в синтаксисе карри (r)(s).

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

Попробуйте онлайн!

Как?

В первом приближении используем формулу:

(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

Если у нас , мы просто добавляем : $\min(r,s)<3$ $1$

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

В противном случае, мы добавим значения выбираются из справочной таблицы, ключ определяется по формуле: $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
источник

Хорошо, первые две строки - аккуратное выражение.

Qwr

5

JavaScript (Node.js) , 56 55 байт

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

Попробуйте онлайн! Я заметил, что таблица напоминает треугольник Паскаля, но с поправочными коэффициентами. Редактировать: 1 байт сохранен благодаря @sundar.

Neil
источник

1

Yep, the Pascal's triangle identity comes from a simple upper bound on the Ramsey numbers (see Jonathan Allan's post)

qwr

1

You can save 1 byte replacing x*y>19 with x+y>8.

sundar - Reinstate Monica

@sundar Thanks, my original solution was 50 bytes before I realised that my indexing was wrong and I forgot to try to golf it again after I'd fixed that.

Neil

4

Jelly, 17 16 bytes

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

Try it online! Or see a test-suite.

Replace the 0 with +, ,, -, ., or / to set $R(5,5)$ equal to $43$ , $44$ , $45$ , $46$ , or $47$ respectively (rather than the $48$ here).

How?

Since $R(r,s)\leq R(r-1,s)+R(r,s-1)$ we may find that:

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

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

This is ’ScḢƊ and would produce:

 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

If we subtract one for each time nine goes into the result we align three more with our goal (this is achieved with _:¥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

The remaining two incorrect values, $32$ and $63$ may then be translated using Jelly's y atom and code-page indices with “ ı?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
источник

If you can set it to any number I recommend 43 as conjectured by McKay, Radziszowski and Exoo ;)

qwr

2

Python 2, 62 bytes

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

Try it online!

Python 2, 63 bytes

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

Try it online!

This is ridiculous, I will soon regret having posted this... But eh, ¯\_(ツ)_/¯. Shaved off 1 byte thanks to our kind Jonathan Allan :). Will probably be outgolfed by about 20 bytes shortly though...

Mr. Xcoder
источник

Porting Arnauld's JS answer is still 62 bytes.

Mr. Xcoder

2

Julia 0.6, 71 61 59 57 bytes

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

Try it online!

Ungolfed (well, a bit more readable):

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

What does it do?

Takes input as array A containing r and s. Unpacks the array into r and s with the smaller number as r, using (r,s)=sort(A).

If r is 1, output should be 1. If r is 2, output should be whatever s is.
$s^{r - 1}$ will be $s^0 = 1$ for r=1, and $s^1 = s$ for r = 2.
So, r<3?s^(r-1) or shorter, r<3?s^~-r

For the others, I started with noticing that the output is:

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

(I initially worked with f(5,5)=45 for convenience.)

This looked like a potentially usable pattern - they all have 2r in common, 17 is 8*2+1, 35 is 17*2+1, 10 is 3*3+1. I started with extracting the base value from [0, 3, 8], as [0 3 8][s-2] (this later became the shorter (s^2-4s+3)).

Attempting to get correct values for r = 3, 4, and 5 with this went through many stages, including

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

and

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

Expanding the latter and simplifying it led to the posted code.

sundar - Reinstate Monica
источник

2

x86, 49 37 bytes

Not very optimized, just exploiting the properties of the first three rows of the table. While I was writing this I realized the code is basically a jump table so a jump table could save many bytes. Input in eax and ebx, output in eax.

-12 by combining cases of r >= 3 into a lookup table (originally just r >= 4) and using Peter Cordes's suggestion of cmp/jae/jne with the flags still set so that r1,r2,r3 are distinguished by only one cmp! Also indexing into the table smartly using a constant offset.

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
источник

2

Don't be so sure a jump table would be optimal. r1: cmp $2, %al / jae r2 will set flags such that you can use r2: jne r3 without another cmp. The jump target in r1 can be a ret somewhere else, and fall through to r2. (Reverse the condition). BTW, this is the first code-golf question I looked at after answering your Short jump offset table usage question on SO. I guess I picked the right one from HNQ :)

Peter Cordes

1

r4 can be one instruction: mov table-8(%ebx,%eax), %al. IDK why you used a separate instruction to mov the table address into a register. But one of the key things is that constant offsets from symbols don't cost anything extra because it already assembles to a 32-bit absolute address. Object file formats can represent symbol refs with an offset for when the linker fills in the final address so compilers don't have to put separate labels on every field of a struct, or every array element...

Peter Cordes

@PeterCordes I didn't even realize this made HNQ. And yes for some reason I thought the table address had to be in a register before realizing I had the syntax wrong. I fixed it here codegolf.stackexchange.com/a/168503/17360 which is just a lookup table. But I didn't know about the constant offset which is handy. I think I'll try a table for the last 3 rows instead of the multiplication.

qwr

1

Note to self: it is still possible to save 1 byte by using one ret for r1 and r2.

qwr

1

Nice update, looks good. What if you move the mov %ebx, %eax to exit, so it always runs after r3, and r2 jumps there or falls through into r3? Then r3 produces its result in BL with sub %bl, %al / cmp $10, %al / jne exit / add $4, %bl (neutral size change: cmp vs. add can use the al,imm8 short form). The gain is that it removes the ret from r2 as well. Hmm no that doesn't work, well maybe if you negate the table entries or something? And that probably clobbers something you need. I haven't thought this through and unfortunately don't have time to do so :/

Peter Cordes

1

Python 2, 70 bytes

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)

Try it online!

Chas Brown
источник

1

MATL, 25 21 bytes

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

Try it on MATL Online

Attempt to port Jonathan Allan's Jelly answer to MATL.

+2-lGqXn - same as that answer: compute $\binom{r+s-2}{r-1}$

t8/k - duplicate that, divide by 8 and floor

- - subtract that from previous result (We subtract how many times 8 goes in the number, instead of 9 in the Jelly answer. The result is the same for all but the 35 and 70, which here give 31 and 62.)

t20/k - duplicate that result too, divide that by 20 and floor (gives 0 for already correct results, 1 for 31, 3 for 62)

6* - multiply that by 6

- - subtract that from the result (31 - 6 = 25, 62 - 18 = 44)

Older:

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

Try it on MATL Online

sundar - Reinstate Monica
источник

0

Python 3, 74 bytes

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

Try it online!

Neil
источник

0

Proton, 52 bytes

Near-port of my Python answer.

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

Try it online!

Mr. Xcoder
источник

0

Java 8, 62 bytes

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

Lambda function, port of Arnauld's JavaScript answer. Try it online here.

Java, 83 bytes

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

Recursive function, port of Neil's JavaScript answer. Try it online here.

O.O.Balance
источник

0

C (gcc), 57 bytes

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

Recursive function, port of Neil's JavaScript answer. Try it online here.

C (gcc), 63 bytes

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's JavaScript answer. Try it online here.

O.O.Balance
источник

49 bytes

ceilingcat

Маленькие номера Рамси

вход

Выход

Ответы:

JavaScript (ES6), 51 49 байт

Как?

JavaScript (Node.js) , 56 55 байт

Jelly, 17 16 bytes

How?

Python 2, 62 bytes

Python 2, 63 bytes

Julia 0.6, 71 61 59 57 bytes

Ungolfed (well, a bit more readable):

What does it do?

x86, 49 37 bytes

Python 2, 70 bytes

MATL, 25 21 bytes

Python 3, 74 bytes

Proton, 52 bytes

Java 8, 62 bytes

Java, 83 bytes

C (gcc), 57 bytes

C (gcc), 63 bytes