Encuentra el máximo de 3 números sin ramificación

17

Esta vez, su objetivo es encontrar el máximo de 3 enteros (de - (2 ^ 31) a 2 ^ 31 - 1 en el complemento binario de 2) sin utilizar ramificaciones o bucles.

Usted está únicamente autorizado a utilizar

  • Desigualdad / Igualdad ( ==, >, >=, <, <=, !=) Estos cuentan como 2 fichas.

  • Aritmética ( +, -, *, /)

  • Operadores lógicos ( !no, &&y, || o)

  • Los operadores bit a bit ( ~no, &y, |o, ^xor, <<, >>, >>>izquierda aritmética y lógica y desplazamientos a la derecha)

  • Constantes 0 fichas

  • Asignación variable. 0 fichas

Ingrese 3 variables como a, by c. Salida del número máximo.

Se aplican las normas estándar de código de golf atómico. Si tienes alguna pregunta, déjala en los comentarios. Una ficha es cualquiera de las anteriores con las reglas especiales.

qwr
fuente
¿Qué hay de definir una función extra? Si esto está permitido, ¿cuántas fichas cuenta?
afuous
@voidpigeon Solo se le permite tener una función, la que toma las 3 entradas y salidas.
qwr
1
A primera vista pensé, " ya hemos tenido esto antes " , pero creo que los comparadores que cuestan 2 cambian bastante el juego.
primo
@primo Pedí específicamente 3 entradas porque realmente permite algunas mejoras interesantes
qwr
2
¿Podemos usar funciones incorporadas?
Usuario registrado

Respuestas:

7

Javascript 10 tokens

Editar utilizando <y * en lugar de violín de bits: como se señala en los comentarios, las operaciones de bits pueden fallar para la entrada cerca del límite del rango (más de 30 bits)

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

C 8 fichas

Lenguaje agnóstico de hecho, cualquier lenguaje similar a C servirá. Para ser exigente, en el estándar C no es portátil porque el desplazamiento a la derecha puede no extender el signo (pero en implementaciones comunes sí).

En C (y C ++, C # y Java, creo) podemos manejar fácilmente los problemas de desbordamiento utilizando valores temporales más grandes:

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
fuente
1
Estoy siendo exigente, pero usando C ints su código no funciona para x = 2147483647, y = -2, z = 0. Su elección si desea cambiarla
qwr
10

Javascript

6 fichas

function maxOf3(a, b, c) {
    (b>a) && (a=b);
    (c>a) && (a=c);
    return a;
}
abrir o cerrar
fuente
66
+1 Veo la evaluación de acceso directo como un tipo de ramificación, pero no está prohibido en las reglas
edc65
11
Consideraría esto como ramificación, jaja
solo el
2
@ edc65 lo es. Permitir &&y ||probablemente fue un descuido, que debería señalarse, en lugar de explotarse.
primo
@primo Este fue un tema interesante. Creo que algunas arquitecturas CISC tienen instrucciones que incluyen declaraciones condicionales, por lo que no estoy seguro de cómo se contarían.
qwr
2
Supongo que debería ser 4 tokens, es decir &&, 2 <y >. El =se utiliza como una tarea y cuenta como 0
Clyde Lobo
6

C: 10 fichas

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

Inspirado por la respuesta de @ openorclose, pero convertido a C y sin ramas utilizando multiplicación en lugar de operadores booleanos de corto circuito.

Paul R
fuente
3

Javascript

14 fichas

function max (a, b, c)
{
    var ab = (a >= b) * a + (a < b) * b;
    return (ab >= c) * ab + (ab < c) * c;
}
Fabricio
fuente
1
No tiene permiso para crear nuevas funciones
qwr
:( 14 fichas entonces
Fabricio
2

Muchos idiomas (Python) (10 tokens)

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, alguien ya lo publicó :)

Mardoxx
fuente
No está permitido crear nuevas funciones
qwr
¡Ahh ok! No leí los comentarios :)
Mardoxx
@qwr No lo entiendo, dijiste: You are only allowed to have one function, the one that takes the 3 inputs and outputs.Eso es exactamente lo que tiene esta respuesta. Las 2 impresiones son solo casos de prueba
Cruncher
1
@Cruncher Edité la respuesta que hice max2(max2(x,y),z)inicialmente :)
Mardoxx
@Mardoxx ah. Bueno +1
Cruncher
1

C ++ 11: 15 tokens

Usar solo operadores aritméticos y bit a bit (ya que los operadores de igualdad y lógica booleana lo hacen demasiado fácil)

#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;
}
Alboroto
fuente
Fallo para números grandes (> 2 ^ 30), vea el comentario codegolf.stackexchange.com/questions/32476/#comment68870_32477
edc65
Me parece bien: ideone.com/pEsvG3
Riot
¿Leíste realmente el comentario? Creo que 2 mil millones es mayor que 0 [ ideone.com/vlcnq9 ]
edc65
Ah, ya veo; sí, tiene un problema con esos números en su otro comentario, cuando se trata de un 0. Pero no por 2 ^ 30 como dijiste. ideone.com/LicmXa
Riot
No es el 0 involucrado. El problema son los números grandes y el desbordamiento, intente max (2000000000, -200000000, 1111111111).
edc65
0

J (no compitiendo)

Me preguntaba cómo sería la solución en J. Este utiliza una ,y #sin embargo, por lo que no competirá.

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

Esto competiría, pero es demasiado largo, con 9 tokens:

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

Tenemos los siguientes supuestos:

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

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

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

podemos usar el pseudocódigo:

función 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

volver a salir2

}

jihed gasmi
fuente
Escriba el código real y proporcione el recuento de tokens en su respuesta.
ProgramFOX
0

C # (segundo intento)

Lo tengo ... No hay funciones integradas ...

Pero, ¿está permitido usar otros tipos de datos integrados o simplemente int? Si lo permitiera, propondría:

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

javascript 8 tokens

aunque similar a la respuesta de @ openorclose, en realidad uso los operadores lógicos para la tarea en sí.

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

violín

Enfriador de matemáticas
fuente
0

R (10 fichas)

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

Brainfuck (No compite)

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

TIS-100, 8 operaciones

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

El proveedor (ARRIBA) solo hace MOV, por lo que no se muestra en el código Tal vez no funcione cuando está demasiado cerca del borde 999

l4m2
fuente
-1

VBA (6 fichas)

 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  

No estoy seguro si esto no es ramificado.

Alex
fuente
Es ramificado, solo en línea. Específicamente, el operador ternario omnipresente (que esto es esencialmente) no es una de las operaciones permitidas.
tomsmeding
Gracias @tomsmeding, ¿puedo preguntar cuál es el operador ternario omnipresente (¿es IIF () en mi código?)
Alex
sí, lo siento, con omnipresente quise decir que está presente en casi todos los idiomas, y el operador ternario es tu IIf, Inline-If. En la mayoría de los idiomas, es, por ejemplo a>=b ? a : b,. Se está ramificando de hecho.
tomsmeding
-1

JavaScript: 4 tokens (** basado en una interpretación amplia de "asignación")

¡Obviamente mi puntaje de 4 es extremadamente generoso / indulgente!

Para llegar a ese puntaje, asumí que "asignación" (con un valor de 0 tokens en la pregunta) incluye cosas como asignación aditiva, asignación sustractiva, asignación multiplicativa y asignación XOR-ing ( ^=)

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

Si esas tareas realmente cuentan, la puntuación es 14 :)

jcdude
fuente
Porque en d -= brealidad es lo mismo d = d - b, yo diría que usas aritmética y que debes contar esto como un token.
ProgramFOX
Sí, me doy cuenta de eso: estaba (en broma) tratando de aprovechar el significado de "asignación". ¡Creo que lo hice bastante obvio!
jcdude