Найти максимум 3 номера без ветвления

17

На этот раз ваша цель - найти максимум 3 целых числа (от - (2 ^ 31) до 2 ^ 31 - 1 в двоичном дополнении 2) без использования ветвления или циклов.

Вы только разрешено использовать

  • Неравенство / Равенство ( ==, >, >=, <, <=, !=) Эти количества , как 2 - маркеров.

  • Арифметика ( +, -,* , /)

  • Логические операторы ( !нет,&& и, || или)

  • Побитовые операторы ( ~не, &и, |или, ^исключающий, <<,>> , >>>арифметические и логические левые и правые сдвиги)

  • Константы. 0 жетонов

  • Переменная присваивания. 0 жетонов

Введите 3 переменные как a, bи c. Выведите максимальное количество.

Применяются стандартные атомные правила игры в гольф. Если у вас есть какие-либо вопросы, пожалуйста, оставьте их в комментариях. Один токен - любой из вышеперечисленных со специальными правилами.

qwr
источник
Как насчет определения дополнительной функции? Если это разрешено, то сколько токенов считается?
afuous
@voidpigeon Вам разрешено иметь только одну функцию, которая принимает 3 входа и выхода.
qwr
1
На первый взгляд, я подумал: «У нас было это раньше » , но я думаю, что компараторы, стоящие 2, сильно меняют игру.
Примо
@primo Я специально попросил 3 входа, потому что это на самом деле допускает некоторые интересные улучшения
qwr
2
Можем ли мы использовать встроенные функции?
Зарегистрированный пользователь

Ответы:

7

Javascript 10 токенов

редактировать используя <и * вместо перестановки битов - как указано в комментариях, операции с битами могут быть неудачными для ввода вблизи предела диапазона (более 30 бит)

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

C 8 токенов

Фактически, независимость от языка подойдет для любого языка, подобного C. Чтобы быть разборчивым, в стандарте C это не переносимо, потому что смещение вправо может не расширять знак (но в обычных реализациях это делает).

В C (и C ++, C # и Java, я думаю) мы можем легко справиться с проблемами переполнения, используя большие временные значения:

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
источник
1
Я привередлив, но с помощью C ints ваш код не работает для x = 2147483647, y = -2, z = 0. Ваш выбор, если вы хотите изменить его
qwr
10

Javascript

6 жетонов

function maxOf3(a, b, c) {
    (b>a) && (a=b);
    (c>a) && (a=c);
    return a;
}
openorclose
источник
6
+1 Я вижу ярлык оценки как тип ветвления, но это не запрещено в правилах
edc65
11
Я бы
расценил
2
@ edc65 Это так. Разрешение &&и, ||вероятно, было упущением, на которое следует указать, а не эксплуатировать.
Примо
@primo Это была интересная проблема. Я считаю, что в некоторых архитектурах CISC есть инструкции, включающие условные операторы, поэтому я не уверен, как они будут учитываться.
qwr
2
Я думаю, это должно быть 4 токена, т.е. 2 &&, <и >. =Используется как задание и рассчитывает как 0
Клайд Лобо
6

C: 10 жетонов

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

Вдохновлен ответом @ openorclose, но преобразован в C и сделан без ветвлений с использованием умножения, а не логических операторов короткого замыкания.

Пол Р
источник
3

Javascript

14 жетонов

function max (a, b, c)
{
    var ab = (a >= b) * a + (a < b) * b;
    return (ab >= c) * ab + (ab < c) * c;
}
Фабрисио
источник
1
Вам не разрешено создавать новые функции
qwr
:( Тогда 14 жетонов
Фабрика
2

Многие языки (Python) (10 токенов)

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

О, кто-то уже опубликовал это :)

Mardoxx
источник
Вам не разрешено создавать новые функции
qwr
О, хорошо! Не читал комментарии :)
Mardoxx
@ qwr Я не понимаю, вы сказали: You are only allowed to have one function, the one that takes the 3 inputs and outputs.это именно то, что есть этот ответ. 2 отпечатка - просто контрольные примеры
Cruncher
1
@Cruncher Я отредактировал ответ, который я сделал max2(max2(x,y),z)изначально :)
Mardoxx
@ Мардокс ах. Ну +1
Cruncher
1

C ++ 11: 15 токенов

Использование только арифметических и побитовых операторов (поскольку операторы равенства и логической логики делают это слишком простым) ...

#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;
}
буйство
источник
Ошибка для больших чисел (> 2 ^ 30), см. Комментарий codegolf.stackexchange.com/questions/32476/#comment68870_32477
edc65
Выглядит хорошо для меня: ideone.com/pEsvG3
Riot
Вы внимательно прочитали комментарий? Я думаю, что 2 миллиарда больше 0 [ ideone.com/vlcnq9 ]
edc65
Ах я вижу; да, у него есть проблема с этими числами в вашем другом комментарии, когда задействован 0. Но не на 2 ^ 30, как вы сказали. ideone.com/LicmXa
Бунт
Это не 0 вовлечен. Проблема в больших числах и переполнении, попробуйте max (2000000000, -200000000, 1111111111).
edc65
0

J (не конкурирует)

Мне было просто интересно, как будет выглядеть решение в J. Это использует ,и #хотя, поэтому он не будет конкурировать.

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

Это будет конкурировать, но это слишком долго, с 9 токенами:

(b*a<:b)+(c*b<c)+(a*c<a)
ɐɔıʇǝɥʇuʎs
источник
0

у нас есть следующие предположения:

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

  • макс (а, б, в) = тах (макс (а, б), в)

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

мы можем использовать псевдокод:

функция 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

возврат out2

}

Джихед Гасми
источник
Пожалуйста, напишите фактический код и укажите количество токенов в своем ответе.
Программа Fox
0

C # (вторая попытка)

Я понял ... Нет встроенных функций ...

Но разрешено ли использовать другие интегрированные типы данных или просто обычный int? Если позволено, я бы предложил:

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
источник
0

JavaScript 8 токенов

хотя и похож на ответ @ openorclose, я фактически использую логические операторы для самого назначения.

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

играть на скрипке

Математический чиллер
источник
0

R (10 жетонов)

function max(a, b, c) {
  max <- a
  max <- max + (b - max) * (b > max)
  max <- max + (c - max) * (c > max)
  return(max)
}
djhurio
источник
0

Brainfuck (не конкурирует)

>,[-<+>>>+<<]>,[-<+>>>+<<]>[>[-<->>]<<]<[-]>[-]>[-]<<<[->>>>+<<<<]>>>>[-<+>>>+<<]>,[-<+>>>+<<]>[>[-<->>]<<]<<
rpax
источник
0

ТИС-100, 8 операций

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

Поставщик (UP) выполняет только MOV, поэтому он не показан в коде. Может быть, не работает, когда слишком близко к краю 999

l4m2
источник
-1

VBA (6 токенов)

 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  

не уверен, что это не ветвление.

Alex
источник
Это ветвление, только встроенное. В частности, вездесущий троичный оператор (которым это по сути является) не является одной из разрешенных операций.
Томсминг
Спасибо @tomsmeding, могу я спросить, что такое вездесущий троичный оператор (это IIF () в моем коде?)
Алекс
да, извините, под вездесущим я имел в виду, что он присутствует практически на всех языках, а троичный оператор - ваш IIf, Inline-If. В большинстве языков это, например a>=b ? a : b,. Это действительно ветвление.
Томсминг
-1

JavaScript: 4 токена (** на основе широкого толкования «назначения»!)

Очевидно, мой счет 4 чрезвычайно щедрый / снисходительный!

Для достижения этого результата я предположил, что «назначение» (в вопросе стоит 0 токенов) включает в себя такие вещи, как аддитивное назначение, вычитающее назначение, мультипликативное назначение и назначение 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;
}

Если эти назначения на самом деле рассчитывают счет 14 :)

jcdude
источник
Потому d -= bчто на самом деле это то же самое d = d - b, что я бы сказал, что вы используете арифметику и вам следует считать это токеном.
ProgramFOX
Да, я понимаю, что - я (в шутку) пытался воспользоваться значением слова «назначение». Я думаю, что сделал это довольно очевидно!
jcdude