13
\$\begingroup\$

Background: the Ramsey number \$R(r,s)\$ gives the minimum number of vertices \$v\$ in the complete graph \$K_v\$ such that a red/blue edge coloring of \$K_v\$ has at least one red \$K_r\$ or one blue \$K_s\$. Bounds for larger \$r, s\$ are very difficult to establish.

Your task is to output the number \$R(r,s)\$ for \$1 \le r,s \le 5\$.

Input

Two integers \$r, s\$ with \$1 \le r \le 5\$ and \$1 \le s \le 5 \$.

Output

\$R(r,s)\$ as given in this table:

  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

Note that \$r\$ and \$s\$ are interchangeable: \$R(r,s) = R(s,r)\$.

For \$R(5,5)\$ you may output any integer between \$43\$ and \$48\$, inclusive. At the time of this question being posted these are the best known bounds.

\$\endgroup\$
  • \$\begingroup\$ I think (even with the range for 5,5) that this may fit under kolmogorov-complexity (or does only a non-input, fixed output fit?) \$\endgroup\$ – Jonathan Allan Jul 15 '18 at 19:47
  • \$\begingroup\$ When was 49 excluded for R(5,5)? (I'm not challenging; I seem to have missed a paper after Exoo's and McKay and Radziszowski's.) \$\endgroup\$ – Eric Towers Jul 15 '18 at 21:47
  • 1
    \$\begingroup\$ @EricTowers arxiv.org/abs/1703.08768 \$\endgroup\$ – qwr Jul 15 '18 at 23:50
  • \$\begingroup\$ @qwr : Thanks! I'm enjoying it so far. \$\endgroup\$ – Eric Towers Jul 16 '18 at 1:42

12 Answers 12

7
\$\begingroup\$

JavaScript (ES6), 51 49 bytes

Takes input in currying syntax (r)(s).

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

Try it online!

How?

As a first approximation, we use the formula:

$$(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

If we have \$\min(r,s)<3\$, we simply add \$1\$:

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

Otherwise, we add a value picked from a lookup table whose key \$k\$ is defined by:

$$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
\$\endgroup\$
  • \$\begingroup\$ Nice, The first two rows is a neat expression. \$\endgroup\$ – qwr Jul 16 '18 at 6:55
5
\$\begingroup\$

JavaScript (Node.js), 56 55 bytes

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

Try it online! I noticed that the table resembles Pascal's triangle but with correction factors. Edit: Saved 1 byte thanks to @sundar.

\$\endgroup\$
  • 1
    \$\begingroup\$ Yep, the Pascal's triangle identity comes from a simple upper bound on the Ramsey numbers (see Jonathan Allan's post) \$\endgroup\$ – qwr Jul 15 '18 at 23:54
  • 1
    \$\begingroup\$ You can save 1 byte replacing x*y>19 with x+y>8. \$\endgroup\$ – sundar Jul 16 '18 at 1:14
  • \$\begingroup\$ @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. \$\endgroup\$ – Neil Jul 16 '18 at 8:17
4
\$\begingroup\$

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}$$

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
\$\endgroup\$
  • \$\begingroup\$ If you can set it to any number I recommend 43 as conjectured by McKay, Radziszowski and Exoo ;) \$\endgroup\$ – qwr Jul 16 '18 at 0:08
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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                                    |....+|
\$\endgroup\$
  • 2
    \$\begingroup\$ 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 :) \$\endgroup\$ – Peter Cordes Jul 16 '18 at 6:30
  • 1
    \$\begingroup\$ 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... \$\endgroup\$ – Peter Cordes Jul 16 '18 at 6:36
  • \$\begingroup\$ @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. \$\endgroup\$ – qwr Jul 16 '18 at 14:37
  • 1
    \$\begingroup\$ Note to self: it is still possible to save 1 byte by using one ret for r1 and r2. \$\endgroup\$ – qwr Jul 19 '18 at 2:09
  • 1
    \$\begingroup\$ 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 :/ \$\endgroup\$ – Peter Cordes Jul 19 '18 at 2:24
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.