Antecedentes: el número de Ramsey $R(r,s)$ da el número mínimo de vértices $v$ en el gráfico completo $K_v$ manera que una coloración de borde rojo / azul de $K_v$ tenga al menos una roja $K_r$ o una azul $K_s$ . Los límites para más grandes $r, s$ son muy difíciles de establecer.

Su tarea es generar el número $R(r,s)$ para $1 \le r,s \le 5$ .

Entrada

Dos enteros $r, s$ con $1 \le r \le 5$ y $1 \le s \le 5$ .

Salida

$R(r,s)$ como se indica en esta tabla:

  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

Tenga en cuenta que $r$ y $s$ son intercambiables: $R(r,s) = R(s,r)$ .

Para puede generar cualquier número entero entre y , inclusive. En el momento de publicación de esta pregunta, estos son los límites más conocidos. $R(5,5)$ $43$ $48$

code-golf integer graph-theory qwr
fuente

Creo (incluso con el rango para 5,5) que esto puede encajar bajo la complejidad de kolmogorov (¿o solo un ajuste fijo de salida sin entrada?)

Jonathan Allan

¿Cuándo se excluyeron 49 para R (5,5)? (No soy un desafío; parece que me he perdido un periódico después de Exoo's y McKay and Radziszowski's)

Eric Towers

1

@EricTowers arxiv.org/abs/1703.08768

qwr

@qwr: ¡Gracias! Lo estoy disfrutando hasta ahora.

Eric Towers

7

JavaScript (ES6), 51 49 bytes

Toma entrada en la sintaxis de curry (r)(s).

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

Pruébalo en línea!

¿Cómo?

Como primera aproximación, usamos la fórmula:

(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

Si tenemos , simplemente agregamos : $\min(r,s)<3$ $1$

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

De lo contrario, agregamos un valor seleccionado de una tabla de búsqueda cuya clave está definida por: $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
fuente

Agradable, las dos primeras filas es una expresión ordenada.

qwr

5

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)

Pruébalo en línea! Noté que la tabla se parece al triángulo de Pascal pero con factores de corrección. Editar: Guardado 1 byte gracias a @sundar.

Neil
fuente

1

Sí, la identidad del triángulo de Pascal proviene de un límite superior simple en los números de Ramsey (ver la publicación de Jonathan Allan)

qwr

1

Puede guardar 1 byte reemplazando x*y>19por x+y>8.

sundar - Restablecer Monica

@sundar Gracias, mi solución original era de 50 bytes antes de darme cuenta de que mi indexación estaba mal y me olvidé de intentar jugar golf nuevamente después de arreglarlo.

Neil

4

Jalea , 17 16 bytes

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

Pruébalo en línea! O ver un conjunto de pruebas .

Sustituir el 0con +, ,, -, ., o /al conjunto igual a , , , , o , respectivamente (en lugar del aquí). $R(5,5)$ $43$ $44$ $45$ $46$ $47$ $48$

¿Cómo?

Como podemos encontrar que: $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}$

Esto es ’ScḢƊy produciría:

 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

Si restamos uno por cada vez que entra nueve en el resultado, alineamos tres más con nuestro objetivo (esto se logra con _:¥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

Los dos valores incorrectos restantes, y , se pueden traducir utilizando el átomo de Jelly y los índices de página de códigos con . $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
fuente

Si puede establecerlo en cualquier número, le recomiendo 43 según lo conjeturado por McKay, Radziszowski y 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)]

Pruébalo en línea!

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

Pruébalo en línea!

Esto es ridículo, pronto lamentaré haber publicado esto ... Pero eh, ¯ \ _ (ツ) _ / ¯. Afeitado 1 byte gracias a nuestro amable Jonathan Allan :). Probablemente será superado por unos 20 bytes en breve ...

Sr. Xcoder
fuente

Portar la respuesta JS de Arnauld sigue siendo 62 bytes .

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

Pruébalo en línea!

Sin golf (bueno, un poco más legible):

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

¿Qué hace?

Toma la entrada como una matriz que Acontiene r y s. Desempaqueta la matriz en rys con el número menor como r, usando(r,s)=sort(A) .

Si r es 1, la salida debería ser 1. Si r es 2, la salida debería ser lo que sea s.
$s^{r - 1}$ estarán $s^0 = 1$ para r = 1, y $s^1 = s$ para r = 2.
Entonces, r<3?s^(r-1)o más corto,r<3?s^~-r

Para los demás, comencé a notar que la salida es:

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

(Inicialmente trabajé con f (5,5) = 45 por conveniencia).

Esto parecía un patrón potencialmente utilizable: todos tienen 2ren común, 17 es 8 * 2 + 1, 35 es 17 * 2 + 1, 10 es 3 * 3 + 1. Comencé extrayendo el valor base de [0, 3, 8], como [0 3 8][s-2](esto luego se hizo más corto (s^2-4s+3)).

Intentar obtener valores correctos para r = 3, 4 y 5 con esto pasó por muchas etapas, incluyendo

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

y

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

Expandir este último y simplificarlo condujo al código publicado.

sundar - Restablecer a Monica
fuente

2

x86, 49 37 bytes

No muy optimizado, solo explota las propiedades de las primeras tres filas de la tabla. Mientras escribía esto, me di cuenta de que el código es básicamente una tabla de salto, por lo que una tabla de salto podría ahorrar muchos bytes. Entrada eaxy ebxsalida eax.

-12 combinando casos de r >= 3en una tabla de búsqueda (originalmente solo r >= 4) y usando la sugerencia de Peter Cordes de cmp/ jae/ jnecon las banderas aún establecidas para que r1,r2,r3se distingan por una sola cmp. También indexando en la tabla de manera inteligente usando un desplazamiento constante.

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
fuente

2

No esté tan seguro de que una mesa de salto sería óptima. r1: cmp $2, %al/ jae r2establecerá marcas de modo que pueda usar r2: jne r3sin otra cmp. El objetivo de salto r1puede ser otro retlugar y caer a través de él r2. (Invierta la condición). Por cierto, esta es la primera pregunta de código de golf que vi después de responder a su pregunta de uso de la tabla de desplazamiento de salto corto en SO. Supongo que elegí el correcto de HNQ :)

Peter Cordes

1

r4puede ser una instrucción: mov table-8(%ebx,%eax), %al. IDK por qué usó una instrucción separada para mover la dirección de la tabla a un registro. Pero una de las cosas clave es que los desplazamientos constantes de los símbolos no cuestan nada extra porque ya se ensambla en una dirección absoluta de 32 bits. Los formatos de archivo de objetos pueden representar referencias de símbolos con un desplazamiento para cuando el enlazador completa la dirección final para que los compiladores no tengan que poner etiquetas separadas en cada campo de una estructura, o cada elemento de matriz ...

Peter Cordes

@PeterCordes Ni siquiera me di cuenta de que esto hizo HNQ. Y sí, por alguna razón, pensé que la dirección de la tabla tenía que estar en un registro antes de darme cuenta de que tenía la sintaxis incorrecta. Lo arreglé aquí codegolf.stackexchange.com/a/168503/17360, que es solo una tabla de búsqueda. Pero no sabía sobre el desplazamiento constante que es útil. Creo que probaré una tabla para las últimas 3 filas en lugar de la multiplicación.

qwr

1

Nota personal: aún es posible guardar 1 byte usando uno retpara r1 y r2.

qwr

1

Buena actualización, se ve bien. ¿Qué pasa si mueve el mov %ebx, %eaxa exit, por lo que siempre se ejecuta después de r3, y r2 salta allí o cae en r3? Entonces r3 produce su resultado en BL con sub %bl, %al/ cmp $10, %al/ jne exit/ add $4, %bl(cambio de tamaño neutral: cmp vs. add puede usar la forma corta al, imm8). La ganancia es que también elimina el retr2. Hmm no, eso no funciona, bueno, ¿tal vez si niegas las entradas de la tabla o algo así? Y eso probablemente encubra algo que necesitas. No he pensado en esto y desafortunadamente no tengo tiempo para hacerlo: /

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)

Pruébalo en línea!

Chas Brown
fuente

1

MATL, 25 21 bytes

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

Pruébalo en MATL Online

Intenta portar la respuesta Jelly de Jonathan Allan a MATL.

+2-lGqXn - igual que esa respuesta: calcular $\binom{r+s-2}{r-1}$

t8/k - duplicar eso, dividir por 8 y piso

- - reste eso del resultado anterior (restamos cuántas veces va 8 en el número, en lugar de 9 en la respuesta Jelly. El resultado es el mismo para todos menos para los 35 y 70, que aquí dan 31 y 62.)

t20/k - duplique ese resultado también, divídalo por 20 y piso (da 0 para resultados ya correctos, 1 para 31, 3 para 62)

6* - multiplique eso por 6

- - reste eso del resultado (31 - 6 = 25, 62 - 18 = 44)

Mayor:

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

Pruébalo en MATL Online

sundar - Reinstate Monica
fuente

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
fuente

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
fuente

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

Función recursiva, puerto de la respuesta JavaScript de Neil . Pruébelo en línea aquí .

OOBalance
fuente

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

Función recursiva, puerto de la respuesta JavaScript de Neil . Pruébelo en línea aquí .

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

La respuesta de JavaScript del puerto de Arnauld . Pruébelo en línea aquí .

OOBalance
fuente

49 bytes

ceilingcat

Pequeños números de Ramsey

Entrada

Salida

Respuestas:

JavaScript (ES6), 51 49 bytes

¿Cómo?

JavaScript (Node.js) , 56 55 bytes

Jalea , 17 16 bytes

¿Cómo?

Python 2 , 62 bytes

Python 2 , 63 bytes

Julia 0.6 , 71 61 59 57 bytes

Sin golf (bueno, un poco más legible):

¿Qué hace?

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