Finde das Maximum von 3 Zahlen ohne Verzweigung

17

Dieses Mal ist es Ihr Ziel, das Maximum von 3 ganzen Zahlen (von - (2 ^ 31) bis 2 ^ 31 - 1 im binären 2er-Komplement) zu finden, ohne Verzweigungen oder Schleifen zu verwenden.

Du darfst nur benutzen

  • Ungleichheits / Gleichheit ( ==, >, >=, <, <=, !=) Diese Zählung als 2 - Tokens.

  • Arithmetic ( +, -, *, /)

  • Logische Operatoren ( !nicht &&und || oder)

  • Bitweise Operatoren ( ~nicht, &und, |oder, ^xor, <<, >>, >>>arithmetische und logische linke und rechte Verschiebungen)

  • Konstanten. 0 Token

  • Variablenzuordnung. 0 Token

Geben Sie 3 Variablen als a, bund ein c. Geben Sie die maximale Anzahl aus.

Standard Atomic Code-Golf-Regeln gelten. Wenn Sie Fragen haben, hinterlassen Sie diese bitte in den Kommentaren. Ein Token ist eines der oben genannten mit den Sonderregeln.

qwr
quelle
Was ist mit der Definition einer zusätzlichen Funktion? Wenn dies erlaubt ist, wie viele Token zählt es?
ängstlich
@voidpigeon Sie dürfen nur eine Funktion haben, die die 3 Ein- und Ausgänge belegt.
Qwr
1
Auf den ersten Blick dachte ich: "Das hatten wir schon einmal. " , Aber ich denke, dass Komparatoren, die 2 kosten, das Spiel ziemlich verändern.
Primo
@primo Ich habe speziell nach 3 Eingängen gefragt, weil es tatsächlich einige interessante Verbesserungen
zulässt
2
Können wir eingebaute Funktionen verwenden?
Registrierter Benutzer

Antworten:

7

Javascript 10 Token

Bearbeiten mit <und * anstelle von Bitfummeln - Wie in den Kommentaren erwähnt, können Bitoperationen bei Eingaben nahe der Bereichsgrenze (über 30 Bit) fehlschlagen.

function Max(x,y,z)
{
  var d=y-x;
  x=y-d*(d<0);
  d=x-z;
  return x-d*(d<0);
}

C 8 Token

Sprachunabhängig ist in der Tat jede C-ähnliche Sprache. Um wählerisch zu sein, ist es in Standard C nicht portierbar, da die Rechtsverschiebung das Vorzeichen möglicherweise nicht erweitert (in gängigen Implementierungen jedoch).

In C (und C ++, C # und Java, glaube ich) können wir Überlaufprobleme mit größeren temporären Werten leicht bewältigen:

int Max(int x, int y, int z)
{
    long long X = x;
    long long Y = y;
    long long Z = z;
    long long D = Y-X;
    X=Y-((D>>63)&D);
    D=X-Z;
    return (int) (X-((D>>63)&D));
}
edc65
quelle
1
Ich bin wählerisch, aber mit C ints funktioniert Ihr Code nicht für x = 2147483647, y = -2, z = 0. Ihre Wahl, wenn Sie es ändern möchten
qwr
10

Javascript

6 Spielmarken

function maxOf3(a, b, c) {
    (b>a) && (a=b);
    (c>a) && (a=c);
    return a;
}
öffnen oder schließen
quelle
6
+1 Ich sehe die Verknüpfungsauswertung als eine Art Verzweigung, aber das ist in den Regeln nicht verboten
edc65
11
Ich würde das als Verzweigung betrachten, haha
Hälfte des
2
@ edc65 Es ist. Zulassen &&und ||war wahrscheinlich ein Versehen, auf das hingewiesen werden sollte, anstatt es auszunutzen.
Primo
@primo Dies war ein interessantes Thema. Ich glaube, dass einige CISC-Architekturen Anweisungen enthalten, die bedingte Anweisungen enthalten, daher bin ich mir nicht sicher, wie diese gezählt werden.
QWR
2
Ich denke , es sollte 4 Token 2 , dh &&, <und >. Die =wird als Aufgabe verwendet und zählt als 0
Clyde Lobo
6

C: 10 Marken

int max(int a, int b, int c)
{
    a += (b > a) * (b - a);
    a += (c > a) * (c - a);
    return a;
}

Inspiriert von der Antwort von @ openorclose, aber in C konvertiert und mithilfe von Multiplikation anstelle von Kurzschluss-Booleschen Operatoren verzweigungslos gemacht.

Paul R
quelle
3

Javascript

14 Spielmarken

function max (a, b, c)
{
    var ab = (a >= b) * a + (a < b) * b;
    return (ab >= c) * ab + (ab < c) * c;
}
Fabricio
quelle
1
Sie dürfen keine neuen Funktionen erstellen
qwr
:( 14 Tokens dann
Fabricio
2

Viele Sprachen (Python) (10 Token)

def max3(x,y,z):
    m = x ^ ((x ^ y) & -(x < y))
    return m ^ ((m ^ z) & -(m < z))

print max3(-1,-2,-3) # -1
print max3(-1,2,10) # 10

https://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax

Oh, jemand hat es bereits gepostet :)

Mardoxx
quelle
Sie dürfen keine neuen Funktionen erstellen
qwr
Ahh ok!
Hab
@qwr Ich verstehe nicht, du hast gesagt: You are only allowed to have one function, the one that takes the 3 inputs and outputs.Genau das hat diese Antwort. Die 2 Drucke sind nur Testfälle
Cruncher
1
@ Cruncher Ich habe die Antwort bearbeitet, die ich max2(max2(x,y),z)ursprünglich gemacht habe :)
Mardoxx
@Mardoxx ah. Gut +1
Cruncher
1

C ++ 11: 15-Token

Verwenden Sie nur arithmetische und bitweise Operatoren (da Gleichheits- und Boolesche Logikoperatoren es zu einfach machen) ...

#include <iostream>

auto max(int32_t a, int32_t b, int32_t c)->int32_t {
  return c - ((c - (a - ((a - b) & (a - b) >> 31))) & (c - (a - ((a - b) & (a - b) >> 31))) >> 31);
}

auto main()->int {
  // test harness
  std::cout << max(9, 38, 7) << std::endl;
  return EXIT_SUCCESS;
}
Randalieren
quelle
Fehler bei großen Zahlen (> 2 ^ 30), siehe Kommentar codegolf.stackexchange.com/questions/32476/#comment68870_32477
edc65
Sieht für mich gut aus: ideone.com/pEsvG3
Riot
Hast du den Kommentar tatsächlich gelesen? Ich denke, 2billions ist größer als 0 [ ideone.com/vlcnq9 ]
edc65
Ah ich sehe; Ja, es gibt ein Problem mit diesen Zahlen in Ihrem anderen Kommentar, wenn eine 0 involviert ist. Aber nicht für 2 ^ 30 wie du gesagt hast. ideone.com/LicmXa
Aufstand
Es ist nicht die 0 beteiligt. Das Problem sind große Zahlen und Überlauf, versuchen Sie es mit max (2000000000, -200000000, 1111111111).
EDC65
0

J (nicht im Wettbewerb)

Ich habe mich nur gefragt, wie die Lösung in J aussehen würde. Dies verwendet ein ,und ein #obwohl, so dass es nicht konkurrieren wird.

((a<b),(b<c),(c<a))#b,c,a

Dies würde mit 9 Token konkurrieren, ist aber viel zu lang:

(b*a<:b)+(c*b<c)+(a*c<a)
ɐɔıɐɔuʇǝɥʇs
quelle
0

Wir haben die folgenden Annahmen:

  • max (a; b) = (a + b + | ab |) / 2

  • max (a; b; c) = max (max (a; b); c)

  • abs (a) = (a + (a >> 31)) ^ (a >> 31)

wir können den Pseudocode verwenden:

Funktion max (a, b, c)

{

out1 = ((a + b) + (((ab) + ((ab) >> 31)) ^ ((ab) >> 31)) div 2

out2 = ((out1 + c) + (((out1-c) + ((out1-c) >> 31)) ^ ((out1-c) >> 31)) div 2

return out2

}

jihed gasmi
quelle
Bitte schreiben Sie den tatsächlichen Code und geben Sie die Anzahl der Token in Ihrer Antwort an.
ProgramFOX
0

C # (2. Versuch)

Ich habe es verstanden ... Keine integrierten Funktionen ...

Aber ist es erlaubt, andere integrierte Datentypen zu verwenden oder einfach nur int? Wenn erlaubt, würde ich vorschlagen:

int foo2(int a, int b, int c)
{
   var x = new SortedList<int,int>();

   x[a] = 1;
   x[b] = 1;
   x[c] = 1;

   return x.Keys[2];
}
EvilFonti
quelle
0

Javascript 8 Token

Obwohl es der Antwort von @ openorclose ähnelt, verwende ich tatsächlich die logischen Operatoren für die Zuweisung selbst.

function max( a, b, c ) {
    x=( a > b && a) || b;
    return ( x > c && x ) || c;
}

Geige

Mathekühler
quelle
0

R (10 Token)

function max(a, b, c) {
  max <- a
  max <- max + (b - max) * (b > max)
  max <- max + (c - max) * (c > max)
  return(max)
}
Djhurio
quelle
0

Brainfuck (nicht im Wettbewerb)

>,[-<+>>>+<<]>,[-<+>>>+<<]>[>[-<->>]<<]<[-]>[-]>[-]<<<[->>>>+<<<<]>>>>[-<+>>>+<<]>,[-<+>>>+<<]>[>[-<->>]<<]<<
rpax
quelle
0

TIS-100, 8 Operationen

MOV ACC UP #A
SUB UP     #B
SUB 999
ADD 999
ADD UP     #B
SUB UP     #C
SUB 999
ADD 999
ADD UP     #C
MOV ACC DOWN

Der Provider (UP) führt nur MOVs durch, die im Code nicht angezeigt werden. Funktioniert möglicherweise nicht, wenn er sich zu nahe an der 999-Kante befindet

l4m2
quelle
-1

VBA (6 Token)

 Function max3(a As Integer, b As Integer, c As Integer)
 i = IIf(a >= b And a >= c, a, IIf(b >= c, b, c))
 max3 = i
 End Function  

nicht sicher, ob dies nicht verzweigt ist.

Alex
quelle
Es ist verzweigt, nur inline. Insbesondere ist der allgegenwärtige ternäre Operator (bei dem es sich im Wesentlichen um einen handelt) keine der zulässigen Operationen.
Tomsmeding
Danke @tomsmeding, darf ich fragen, was ist der allgegenwärtige ternäre Operator (ist es IIF () in meinem Code?)
Alex
ja sorry, mit allgegenwärtig habe ich gemeint, dass es in so ziemlich jeder Sprache vorhanden ist, und der ternäre Operator ist Ihr IIf, Inline-If. In den meisten Sprachen zum Beispiel a>=b ? a : b. Es verzweigt sich tatsächlich.
Tomsmeding
-1

JavaScript: 4 Token (** basierend auf einer breiten Interpretation von "Zuweisung"!)

Offensichtlich ist meine Punktzahl von 4 extrem großzügig / nachsichtig!

Um zu dieser Punktzahl zu gelangen, habe ich angenommen, dass "Zuweisung" (Wert 0 in der Frage) solche Dinge wie additive Zuweisung, subtraktive Zuweisung, multiplikative Zuweisung und XOR-ing ( ^=) -Zuweisung umfasst

function f(a, b, c) {
  d = a;
  d -= b;
  d = d >= 0;

  a *= d;  //a = a if (a>=b), else 0
  d ^= true; //invert d
  b *= d;  //b = b if (b<a), else 0

  a += b;  //a is now max(a,b)

  d = a;
  d -= c;
  d = d >= 0;

  a *= d;  //a = a if (a>=c), else 0
  d ^= true; //invert d
  c *= d;  //c = c if (c<a), else 0
  a += c;  //a is now max(max(a,b),c)

  return a;
}

Wenn diese Aufgaben tatsächlich zählen, ist die Punktzahl 14 :)

jcdude
quelle
Weil d -= bes eigentlich dasselbe ist wie d = d - b, würde ich sagen, dass Sie Arithmetik verwenden und dass Sie dies als Token zählen sollten.
ProgramFOX
Ja, mir ist klar, dass ich (im Scherz) versucht habe, die Bedeutung von "Zuweisung" auszunutzen. Ich denke, ich habe das ziemlich offensichtlich gemacht!
jcdude