Temukan maksimal 3 angka tanpa bercabang

17

Kali ini di sekitar tujuan Anda adalah untuk menemukan maksimum 3 bilangan bulat (dari - (2 ^ 31) hingga 2 ^ 31 - 1 dalam komplemen biner 2) tanpa menggunakan percabangan atau loop.

Anda hanya diperbolehkan menggunakan

  • Ketidaksetaraan / Kesetaraan ( ==, >, >=, <, <=, !=) count ini sebagai 2 token.

  • Aritmatika ( +, -, *, /)

  • Operator Logis ( !bukan, &&dan, || atau)

  • Bitwise Operator ( ~tidak, &dan, |atau, ^xor, <<, >>, >>>aritmatika dan logis kiri dan pergeseran kanan)

  • Konstanta. 0 token

  • Tugas variabel. 0 token

Masukkan 3 variabel sebagai a, bdan c. Keluarkan jumlah maksimum.

Aturan golf-atom standar berlaku. Jika Anda memiliki pertanyaan, silakan tinggalkan di komentar. Satu token adalah salah satu di atas dengan aturan khusus.

qwr
sumber
Bagaimana dengan mendefinisikan fungsi ekstra? Jika ini dibolehkan, berapa token yang dihitung?
afuous
@ voidpigeon Anda hanya diperbolehkan memiliki satu fungsi, fungsi yang mengambil 3 input dan output.
qwr
1
Pada pandangan pertama saya berpikir, " kita pernah mengalami ini sebelumnya. " , Tapi saya pikir pembanding biaya 2 perubahan permainan cukup sedikit.
primo
@rimo Saya secara khusus meminta 3 input karena sebenarnya memungkinkan untuk beberapa perbaikan yang menarik
qwr
2
Bisakah kita menggunakan fungsi inbuilt?
Pengguna Terdaftar

Jawaban:

7

Javascript 10 token

Edit Menggunakan <dan * alih-alih mengutak-atik bit - seperti yang ditunjukkan dalam komentar, operasi bit mungkin gagal untuk input di dekat batas rentang (lebih dari 30 bit)

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

Bahasa agnostik sebenarnya, bahasa C seperti apa yang akan dilakukan. Untuk pilih-pilih, dalam standar C itu tidak portabel karena pergeseran yang tepat mungkin tidak memperpanjang tanda (tetapi dalam implementasi umum itu tidak).

Dalam C (dan C ++, C #, dan Java saya pikir) kita dapat dengan mudah menangani masalah overflow menggunakan nilai sementara yang lebih besar:

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
sumber
1
Saya pilih-pilih, tetapi menggunakan Cs intkode Anda tidak berfungsi untuk x = 2147483647, y = -2, z = 0. Pilihan Anda jika Anda ingin mengubahnya
qwr
10

Javascript

6 token

function maxOf3(a, b, c) {
    (b>a) && (a=b);
    (c>a) && (a=c);
    return a;
}
openorclose
sumber
6
+1 Saya melihat evaluasi pintas sebagai jenis percabangan, tetapi tidak dilarang dalam aturan
edc65
11
Saya akan menganggap ini sebagai percabangan, haha
justhalf
2
@ edc65 Ya. Mengizinkan &&dan ||kemungkinan merupakan kekhilafan, yang harus ditunjukkan, bukan dieksploitasi.
Primo
@ primo Ini adalah masalah yang menarik. Saya percaya beberapa arsitektur CISC memiliki instruksi yang mencakup pernyataan bersyarat, jadi saya tidak yakin bagaimana itu akan dihitung.
qwr
2
Saya kira itu harus 4 token yaitu 2 &&, <dan >. Ini =digunakan sebagai tugas dan dihitung sebagai 0
Clyde Lobo
6

C: 10 token

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

Terinspirasi oleh jawaban @ openorclose, tetapi dikonversi menjadi C dan menjadikan branchless menggunakan multiplikasi daripada operator boolean hubung singkat.

Paul R
sumber
3

Javascript

14 token

function max (a, b, c)
{
    var ab = (a >= b) * a + (a < b) * b;
    return (ab >= c) * ab + (ab < c) * c;
}
Fabricio
sumber
1
Anda tidak diizinkan membuat fungsi baru
qwr
:( 14 token kemudian
Fabricio
2

Banyak bahasa (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, seseorang sudah mempostingnya :)

Mardoxx
sumber
Anda tidak diizinkan membuat fungsi baru
qwr
Ahh ok! Tidak membaca komentar :)
Mardoxx
@ qr Saya tidak mengerti, Anda berkata: You are only allowed to have one function, the one that takes the 3 inputs and outputs.Itulah yang dimiliki jawaban ini. 2 cetakan hanyalah kasus uji
Cruncher
1
@Cruncher Saya mengedit jawaban yang saya lakukan max2(max2(x,y),z)pada awalnya :)
Mardoxx
@ Martoxx ah. Baik +1
Cruncher
1

C ++ 11: 15 token

Hanya menggunakan operator aritmatika dan bitwise (karena operator logika kesetaraan dan boolean membuatnya terlalu mudah) ...

#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;
}
Kerusuhan
sumber
Gagal untuk angka besar (> 2 ^ 30), lihat komentar codegolf.stackexchange.com/questions/32476/#comment68870_32477
edc65
Terlihat baik-baik saja untuk saya: ideone.com/pEsvG3
Kerusuhan
Apakah Anda benar-benar membaca komentar? Saya pikir 2billions lebih besar dari 0 [ ideone.com/vlcnq9 ]
edc65
Ah saya mengerti; ya itu memang memiliki masalah dengan angka-angka di komentar Anda yang lain, ketika 0 terlibat. Tetapi tidak untuk 2 ^ 30 seperti yang Anda katakan. ideone.com/LicmXa
Riot
Bukan 0 yang terlibat. Masalahnya adalah angka besar dan melimpah, coba maks (2000000000, -200000000, 1111111111).
edc65
0

J (Tidak bersaing)

Saya hanya ingin tahu seperti apa solusi di J nantinya. Ini menggunakan a ,dan a #, jadi itu tidak akan bersaing.

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

Ini akan bersaing, tetapi terlalu lama, dengan 9 token:

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

kami memiliki asumsi berikut:

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

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

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

kita bisa menggunakan pseudo-code:

fungsi maks (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

kembali keluar2

}

jihed gasmi
sumber
Harap tulis kode aktual, dan berikan jumlah token dalam jawaban Anda.
ProgramFOX
0

C # (percobaan ke-2)

Saya mendapatkannya ... Tidak ada fungsi terintegrasi ...

Tetapi apakah itu diperbolehkan untuk menggunakan tipe data terintegrasi lainnya atau hanya int? Jika diizinkan saya akan mengusulkan:

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

javascript 8 token

meskipun mirip dengan jawaban @ openorclose, saya benar-benar menggunakan operator logis untuk tugas itu sendiri.

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

biola

Chiller matematika
sumber
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
sumber
0

Brainfuck (Tidak bersaing)

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

TIS-100, 8 operasi

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

Penyedia (UP) hanya melakukan MOV jadi tidak ditampilkan dalam kode. Mungkin tidak bekerja ketika terlalu dekat dengan tepi 999

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

tidak yakin apakah ini tidak bercabang.

Alex
sumber
Ini bercabang, hanya sebaris. Secara khusus, operator ternary di mana-mana (yang pada dasarnya adalah ini) bukan salah satu dari operasi yang diizinkan.
tomsmeding
Terima kasih @tomsmeding, bolehkah saya bertanya apa operator ternary yang ada di mana-mana (apakah ini IIF () dalam kode saya?)
Alex
ya maaf, dengan di mana-mana saya maksudkan bahwa itu hadir dalam hampir semua bahasa, dan operator ternary adalah Anda IIf, Inline-If. Dalam sebagian besar bahasa, misalnya a>=b ? a : b,. Ini memang bercabang.
tommeding
-1

JavaScript: 4 token (** berdasarkan interpretasi luas "penugasan"!)

Jelas skor saya 4 sangat murah hati / toleran!

Untuk mencapai skor itu, saya mengasumsikan "penugasan" (bernilai 0 token dalam pertanyaan) mencakup hal-hal seperti penugasan aditif, penugasan subtraktif, penugasan multiplikatif, dan penugasan 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;
}

Jika tugas-tugas itu benar-benar menghitung skornya adalah 14 :)

Ya Tuhan
sumber
Karena d -= bsebenarnya sama dengan d = d - b, saya akan mengatakan bahwa Anda menggunakan aritmatika dan Anda harus menghitung ini sebagai token.
ProgramFOX
Ya, saya menyadari bahwa - saya (dengan bercanda) mencoba mengambil keuntungan dari arti "penugasan". Saya pikir saya membuatnya cukup jelas!
jcdude