Encontre o máximo de 3 números sem ramificação

17

Desta vez, seu objetivo é encontrar o máximo de 3 números inteiros (de - (2 ^ 31) a 2 ^ 31 - 1 no complemento binário de 2) sem usar ramificações ou loops.

Você pode usar

  • Desigualdade / A igualdade ( ==, >, >=, <, <=, !=) Estes contagem como 2 fichas.

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

  • Operadores lógicos ( !não, &&e, || ou)

  • Bit a bit Operadores ( ~não, &e, |ou, ^xor, <<, >>, >>>mudanças certas aritmética e lógica esquerda e)

  • Constantes. 0 fichas

  • Atribuição variável. 0 fichas

Insira 3 variáveis ​​como a, be c. Emita o número máximo.

Aplicam-se regras atômicas de código-golfe padrão. Se você tiver alguma dúvida, deixe-a nos comentários. Um token é um dos itens acima com regras especiais.

qwr
fonte
Que tal definir uma função extra? Se isso for permitido, quantos tokens contam?
28514 afuous
@voidpigeon Você só pode ter uma função, a que aceita as 3 entradas e saídas.
QWR
11
À primeira vista, pensei: " já tivemos isso antes " , mas acho que os comparadores que custam 2 mudam bastante o jogo.
Primo
@primo Eu pedi especificamente 3 entradas porque na verdade permite algumas melhorias interessantes
qwr
2
Podemos usar funções embutidas?
Usuário registrado

Respostas:

7

Javascript 10 tokens

Editar Usando <e * em vez de mexer com bits - como apontado nos comentários, as operações de bits podem falhar na entrada perto do limite do intervalo (acima 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);
}

Tokens C 8

Linguagem independente de fato, qualquer linguagem semelhante ao C serve. Para ser exigente, no padrão C não é portátil porque a mudança à direita pode não estender o sinal (mas em implementações comuns).

Em C (e C ++, C # e Java, eu acho), podemos lidar facilmente com problemas de estouro usando valores temporários maiores:

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
fonte
11
Estou sendo exigente, mas, usando C ints, seu código não funciona para x = 2147483647, y = -2, z = 0. Sua escolha se você quiser mudá-lo
QWR
10

Javascript

6 fichas

function maxOf3(a, b, c) {
    (b>a) && (a=b);
    (c>a) && (a=c);
    return a;
}
openorclose
fonte
6
+1 vejo avaliação atalho como um tipo de ramificação, mas não é proibido nas regras
edc65
11
Eu consideraria isso como ramificação, haha
justhalf
2
@ edc65 É. Permitir &&e ||provavelmente era uma supervisão, que deveria ser apontada, e não explorada.
primo
@primo Esta foi uma questão interessante. Acredito que algumas arquiteturas do CISC têm instruções que incluem instruções condicionais, então não tenho certeza de como elas seriam contadas.
QWR
2
Eu acho que deve ser de 4 fichas, ou seja &&, 2 <e >. O =é usado como uma tarefa e conta 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 na resposta de @ openorclose, mas convertido em C e tornado sem ramificação usando multiplicação em vez de operadores booleanos de curto-circuito.

Paul R
fonte
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
fonte
11
Você não tem permissão para criar novas funções
qwr
:( 14 tokens então
Fabricio
2

Muitos 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

Ah, alguém já postou :)

Mardoxx
fonte
Você não tem permissão para criar novas funções
qwr
Ahh, certo! Não ler os comentários :)
Mardoxx
@qwr Eu não entendi, você disse: You are only allowed to have one function, the one that takes the 3 inputs and outputs.Isso é exatamente o que esta resposta tem. As 2 impressões são apenas casos de teste
Cruncher
11
@Cruncher Eu editei a resposta que eu fiz max2(max2(x,y),z)inicialmente :)
Mardoxx
@Mardoxx ah. Bem +1
Cruncher
1

C ++ 11: 15 tokens

Usando apenas operadores aritméticos e bit a bit (já que os operadores de igualdade e lógica booleana facilitam muito) ...

#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;
}
Tumulto
fonte
Falha para números grandes (> 2 ^ 30), ver comentário codegolf.stackexchange.com/questions/32476/#comment68870_32477
edc65
Looks bem para mim: ideone.com/pEsvG3
Motim
Você realmente leu o comentário? Acho 2billions é maior que 0 [ ideone.com/vlcnq9 ]
edc65
Ah entendo; sim, ele tem um problema com esses números no seu outro comentário, quando um 0 está envolvido. Mas não para 2 ^ 30, como você disse. ideone.com/LicmXa
Riot
Não é o 0 envolvido. O problema são grandes números e estouro, tente max (2000000000, -200000000, 1111111111).
edc65
0

J (Não competindo)

Eu só estava me perguntando como seria a solução em J. Isso usa a ,e a #embora, portanto, não estará competindo.

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

Isso competiria, mas é muito longo, com 9 tokens:

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

temos as seguintes suposições:

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

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

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

podemos usar o pseudo-código:

função max (a, b, c)

{

O resultado da equação de segundo grau é: (a + b) + ((b) + ((ab) >> 31)) ^ ((ab))

O resultado da equação de segundo grau é: a) (b) (b) (c) (b) (c) (c) (c)

retorno out2

}

jihed gasmi
fonte
Escreva o código real e forneça a contagem de tokens na sua resposta.
precisa
0

C # (segunda tentativa)

Entendi ... Sem funções integradas ...

Mas é permitido usar outros tipos de dados integrados ou simplesmente int? Se permitido, proporia:

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

javascript 8 tokens

embora semelhante à resposta do @ openorclose, na verdade eu uso os operadores lógicos para a atribuição em si.

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

violino

Resfriador de matemática
fonte
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
fonte
0

Brainfuck (Não competindo)

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

TIS-100, 8 operações

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

O provedor (UP) apenas realiza MOVs, de modo que não sejam mostrados no código. Talvez não funcione quando estiver muito próximo da borda 999

l4m2
fonte
-1

VBA (6 tokens)

 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  

não tenho certeza se isso não está ramificando.

Alex
fonte
Está ramificando, apenas em linha. Especificamente, o operador ternário onipresente (que é essencialmente) não é uma das operações permitidas.
tomsmeding
Graças @tomsmeding, gostaria de perguntar o que é o operador ternário ubiquitous (é IIF () no meu código?)
Alex
sim desculpe, com onipresente eu quis dizer que ele está presente em praticamente todos os idiomas, e o operador ternário é o seu IIf , Inline-If. Na maioria dos idiomas, é, por exemplo a>=b ? a : b,. Está se ramificando de fato.
tomsmeding
-1

JavaScript: 4 tokens (** com base na ampla interpretação de "atribuição"!)

Obviamente, minha pontuação de 4 é extremamente generosa / branda!

Para chegar a essa pontuação, assumi que "atribuição" (no valor de 0 fichas na pergunta) inclui itens como atribuição aditiva, atribuição subtrativa, atribuição multiplicativa e atribuição 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;
}

Se essas tarefas realmente contarem, a pontuação é 14 :)

jcdude
fonte
Como d -= bna verdade é o mesmo d = d - b, eu diria que você usa aritmética e que deve contar isso como um token.
precisa
Sim, eu percebo que - eu estava (brincando) tentando tirar proveito do significado de "tarefa". Eu acho que fiz isso bastante óbvio!
jcdude