Hintergrund: Die Ramsey-Zahl gibt die minimale Anzahl von Eckpunkten im vollständigen Graphen so dass eine rot / blaue Kantenfärbung von mindestens ein rotes oder ein blaues . Grenzen für größere r, s sind sehr schwer zu ermitteln.V K V K V K r K s r , $R(r,s)$$v$$K_v$$K_v$$K_r$$K_s$$r, s$

Ihre Aufgabe ist es, die Zahl $R(r,s)$ für 1 \ le r, s \ le 5 auszugeben $1 \le r,s \le 5$.

Eingang

Zwei ganze Zahlen $r, s$ mit $1 \le r \le 5$ und $1 \le s \le 5$ .

Ausgabe

$R(r,s)$ wie in dieser Tabelle angegeben:

  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

Beachten Sie, dass $r$ und $s$ austauschbar sind: $R(r,s) = R(s,r)$ .

Für Sie eine beliebige ganze Zahl zwischen und einschließlich ausgeben . Zum Zeitpunkt der Veröffentlichung dieser Frage sind dies die bekanntesten Grenzen.43 $R(5,5)$$43$$48$

JavaScript (ES6), 51 bis 49 Byte

Übernimmt Eingaben in der Currying-Syntax (r)(s).

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

Probieren Sie es online!

Wie?

In erster Näherung verwenden wir die Formel:

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

Andernfalls fügen wir einen Wert hinzu, der aus einer Nachschlagetabelle ausgewählt wurde, deren Schlüssel definiert ist durch:$k$

 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

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)

Probieren Sie es online! Mir ist aufgefallen, dass die Tabelle dem Pascalschen Dreieck ähnelt, jedoch mit Korrekturfaktoren. Bearbeiten: 1 Byte dank @sundar gespeichert.

Jelly ,  17  16 Bytes

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

Probieren Sie es online! Oder sehen Sie sich eine Testsuite an .

Ersetzen der 0mit +, ,, -, ., oder , /um Als , die gleich 43 , 44 , 45 , 46 , oder 47 jeweils (statt dem 48 hier).$R(5,5)$$43$$44$$45$$46$$47$$48$

Wie?

Da , können wir feststellen, dass:$R(r,s)\leq R(r-1,s)+R(r,s-1)$

Dies ist ’ScḢƊund würde erzeugen:

 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

Wenn wir für jedes Mal eins abziehen, wenn neun in das Ergebnis einfließen, richten wir drei weitere nach unserem Ziel aus (dies wird erreicht mit _:¥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

Die verbleibenden zwei falschen Werte und 63 können dann unter Verwendung von Jellys Atom- und Codepage-Indizes mit übersetzt werden .$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

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

Probieren Sie es 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)]

Probieren Sie es online!

Das ist lächerlich, ich werde es bald bereuen, dies gepostet zu haben ... Aber äh, ¯ \ _ (ツ) _ / ¯. Dank unseres freundlichen Jonathan Allan 1 Byte weg rasiert :). Wird wohl in Kürze um ca. 20 Bytes überholt sein ...

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)

Probieren Sie es online!

Ungolfed (naja, etwas besser lesbar):

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

Was tut es?

Übernimmt die Eingabe als Array Amit r und s. Entpackt das Array mit r und s mit der kleineren Nummer als r (r,s)=sort(A).

$s^{r - 1}$$s^0 = 1$$s^1 = s$
r<3?s^(r-1)r<3?s^~-r

Für die anderen begann ich zu bemerken, dass die Ausgabe ist:

• $2\times3 + [0, 3, 8]$
• $2\times4 + \ \ [10, 17]$
• $2\times5 + \ \ \ \ \ [35]$

(Ich habe anfänglich mit f (5,5) = 45 gearbeitet.)

Dies sah nach einem potenziell verwendbaren Muster aus - sie haben alle eines 2rgemeinsam: 17 ist 8 * 2 + 1, 35 ist 17 * 2 + 1, 10 ist 3 * 3 + 1. Ich begann mit dem Extrahieren des Basiswerts aus [0, 3, 8] als [0 3 8][s-2](dies wurde später kürzer (s^2-4s+3)).

Der Versuch, die korrekten Werte für r = 3, 4 und 5 zu erhalten, durchlief viele Phasen, einschließlich

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

und

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

Letzteres zu erweitern und zu vereinfachen, führte zum gebuchten Code.

x86, 49 37 Bytes

Nicht sehr optimiert, nur die Eigenschaften der ersten drei Zeilen der Tabelle ausnutzen. Während ich dies schrieb, wurde mir klar, dass der Code im Grunde genommen eine Sprungtabelle ist, so dass eine Sprungtabelle viele Bytes sparen kann. Eingabe in eaxund ebxAusgabe in eax.

-12 von Fällen der Kombination r >= 3in eine Lookup - Tabelle (ursprünglich nur r >= 4) und mit Peter Cordes Vorschlag von cmp/ jae/ jnemit den Flags noch gesetzt , so dass r1,r2,r3zeichnen sich durch nur eine cmp! Indizieren Sie auch intelligent mit einem konstanten Versatz in die Tabelle.

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

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)

Probieren Sie es online!

MATL, 25 21 Bytes

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

Probieren Sie es auf MATL Online aus

Versuch, Jonathan Allans Jelly-Antwort auf MATL zu portieren.

+2-lGqXn - das gleiche wie diese Antwort: berechnen $\binom{r+s-2}{r-1}$

t8/k - duplizieren Sie das, teilen Sie durch 8 und Boden

- - subtrahiere das vom vorherigen Ergebnis (Wir subtrahieren, wie oft 8 in der Zahl vorkommt, anstatt 9 in der Gelee-Antwort. Das Ergebnis ist für alle gleich, mit Ausnahme der 35 und 70, die hier 31 und 62 ergeben.)

t20/k - Dupliziere auch dieses Ergebnis, dividiere es durch 20 und fülle (ergibt 0 für bereits korrekte Ergebnisse, 1 für 31, 3 für 62)

6* - multiplizieren Sie das mit 6

- - subtrahiere das vom Ergebnis (31 - 6 = 25, 62 - 18 = 44)

Älter:

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

Probieren Sie es auf MATL Online aus

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

Probieren Sie es online!

Proton , 52 Bytes

Near-Port meiner Python-Antwort .

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

Probieren Sie es online!

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-Funktion, Portierung der JavaScript- Antwort von Arnauld . Probieren Sie es hier online aus .

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

Rekursive Funktion, Port von Neils JavaScript- Antwort . Probieren Sie es hier online aus .

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

Rekursive Funktion, Port von Neils JavaScript- Antwort . Probieren Sie es hier online aus .

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

Die JavaScript- Antwort von Port of Arnauld . Probieren Sie es hier online aus .