17
\$\begingroup\$

This time around your goal is to find the maximum of 3 integers (from -(2^31) to 2^31 - 1 in binary 2's complement) without using branching or loops.

You are only allowed to use

  • Inequality/Equality (==, >, >=, <, <=, !=) These count as 2 tokens.

  • Arithmetic (+, -, *, /)

  • Logical Operators (! not, && and, || or)

  • Bitwise Operators (~ not, & and, | or, ^ xor, <<, >>, >>> arithmetic and logical left and right shifts)

  • Constants. 0 tokens

  • Variable assignment. 0 tokens

Input 3 variables as a, b and c. Output the maximum number.

Standard atomic code-golf rules apply. If you have any questions please leave them in the comments. One token is any of the above with the special rules.

\$\endgroup\$
  • \$\begingroup\$ What about defining an extra function? If this is allowed, how many tokens does it count as? \$\endgroup\$ – afuous Jun 25 '14 at 0:16
  • \$\begingroup\$ @voidpigeon You are only allowed to have one function, the one that takes the 3 inputs and outputs. \$\endgroup\$ – qwr Jun 25 '14 at 0:20
  • 1
    \$\begingroup\$ At first glance I thought, "we've had this before.", but I think comparators costing 2 changes the game quite a bit. \$\endgroup\$ – primo Jun 25 '14 at 0:36
  • \$\begingroup\$ @primo I specifically asked for 3 inputs because it actually allows for some interesting improvements \$\endgroup\$ – qwr Jun 25 '14 at 0:39
  • 2
    \$\begingroup\$ Can we use inbuilt functions? \$\endgroup\$ – Registered User Jun 25 '14 at 4:44

15 Answers 15

7
\$\begingroup\$

Javascript 10 tokens

Edit Using < and * instead of bit fiddling - as pointed out in comments, bits operations may fail for input near the range limit (over 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 tokens

Language agnostic in fact, any C like language will do. To be picky, in standard C it's not portable because right shift may not extend the sign (but in common implementations it does).

In C (and C++, C#, and Java I think) we can easily handle overflow problems using bigger temporary values:

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));
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm being picky, but using C ints your code doesn't work for x=2147483647, y = -2, z=0. Your choice if you want to change it \$\endgroup\$ – qwr Jun 25 '14 at 0:48
10
\$\begingroup\$

Javascript

6 tokens

function maxOf3(a, b, c) {
    (b>a) && (a=b);
    (c>a) && (a=c);
    return a;
}
\$\endgroup\$
  • 6
    \$\begingroup\$ +1 I see shortcut evaluation as a type of branching, but it's not forbidden in the rules \$\endgroup\$ – edc65 Jun 25 '14 at 1:33
  • 11
    \$\begingroup\$ I would consider this as branching, haha \$\endgroup\$ – justhalf Jun 25 '14 at 2:52
  • 2
    \$\begingroup\$ @edc65 It is. Allowing && and || was likely an oversight, which should be pointed out, rather than exploited. \$\endgroup\$ – primo Jun 25 '14 at 5:09
  • \$\begingroup\$ @primo This was an interesting issue. I believe some CISC architectures have instructions that include conditional statements, so I'm not sure how those would be counted. \$\endgroup\$ – qwr Jun 25 '14 at 5:54
  • 2
    \$\begingroup\$ I guess it should be 4 tokens i.e 2 &&, < and >. The = is used as an assignment and counts as 0 \$\endgroup\$ – Clyde Lobo Jun 25 '14 at 12:40
6
\$\begingroup\$

C: 10 tokens

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

Inspired by @openorclose's answer, but converted to C and made branchless using multiplication rather than short circuit boolean operators.

\$\endgroup\$
3
\$\begingroup\$

Javascript

14 tokens

function max (a, b, c)
{
    var ab = (a >= b) * a + (a < b) * b;
    return (ab >= c) * ab + (ab < c) * c;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You are not allowed to create new functions \$\endgroup\$ – qwr Jun 25 '14 at 1:16
  • \$\begingroup\$ :( 14 tokens then \$\endgroup\$ – Fabricio Jun 25 '14 at 1:17
2
\$\begingroup\$

Many languages (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, someone already posted it :)

\$\endgroup\$
  • \$\begingroup\$ You are not allowed to create new functions \$\endgroup\$ – qwr Jun 25 '14 at 9:28
  • \$\begingroup\$ Ahh ok! Didn't read the comments :) \$\endgroup\$ – Mardoxx Jun 25 '14 at 10:24
  • \$\begingroup\$ @qwr I don't get it, you said: You are only allowed to have one function, the one that takes the 3 inputs and outputs. That's exactly what this answer has. The 2 prints are just test cases \$\endgroup\$ – Cruncher Jun 25 '14 at 14:40
  • 1
    \$\begingroup\$ @Cruncher I edited the answer I did max2(max2(x,y),z) initially :) \$\endgroup\$ – Mardoxx Jun 25 '14 at 15:02
  • \$\begingroup\$ @Mardoxx ah. Well +1 \$\endgroup\$ – Cruncher Jun 25 '14 at 15:57
1
\$\begingroup\$

C++11: 15 tokens

Using only arithmetic and bitwise operators (since equality and boolean logic operators make it too easy)...

#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;
}
\$\endgroup\$
  • \$\begingroup\$ Fail for big numbers (>2^30), see comment codegolf.stackexchange.com/questions/32476/#comment68870_32477 \$\endgroup\$ – edc65 Jun 25 '14 at 21:08
  • \$\begingroup\$ Looks fine to me: ideone.com/pEsvG3 \$\endgroup\$ – Riot Jun 26 '14 at 8:06
  • \$\begingroup\$ Did you atctually read the comment? I think 2billions is greater than 0 [ideone.com/vlcnq9 ] \$\endgroup\$ – edc65 Jun 26 '14 at 8:19
  • \$\begingroup\$ Ah i see; yes it does have a problem with those numbers in your other comment, when a 0 is involved. But not for 2^30 as you said. ideone.com/LicmXa \$\endgroup\$ – Riot Jun 26 '14 at 22:00
  • \$\begingroup\$ It's not the 0 involved. The problem are big numbers and overflow, try max(2000000000, -200000000, 1111111111). \$\endgroup\$ – edc65 Jun 26 '14 at 22:07
0
\$\begingroup\$

J (Not competing)

I was just wondering what the a solution in J would look like. This uses a , and a # though, so it won't be competing.

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

This would compete, but is way too long, with 9 tokens:

(b*a<:b)+(c*b<c)+(a*c<a)
\$\endgroup\$
0
\$\begingroup\$

we have the following assumptions:

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

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

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

we can use the pseudo-code:

function max(a,b,c)

{

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

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

return out2

}

\$\endgroup\$
  • \$\begingroup\$ Please write actual code, and provide the count of tokens in your answer. \$\endgroup\$ – ProgramFOX Jun 25 '14 at 18:20
0
\$\begingroup\$

C# (2nd try)

I got it... No integrated functions...

But is it allowed to use other integrated datatypes or just plain int? If allowed I would propose:

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];
}
\$\endgroup\$
0
\$\begingroup\$

javascript 8 tokens

although similar to @openorclose's answer, i do actually use the logical operators for the assignment itself.

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

fiddle

\$\endgroup\$
0
\$\begingroup\$

R (10 tokens)

function max(a, b, c) {
  max <- a
  max <- max + (b - max) * (b > max)
  max <- max + (c - max) * (c > max)
  return(max)
}
\$\endgroup\$
0
\$\begingroup\$

Brainfuck (Not competing)

>,[-<+>>>+<<]>,[-<+>>>+<<]>[>[-<->>]<<]<[-]>[-]>[-]<<<[->>>>+<<<<]>>>>[-<+>>>+<<]>,[-<+>>>+<<]>[>[-<->>]<<]<<
\$\endgroup\$
0
\$\begingroup\$

TIS-100, 8 operations

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

The provider(UP) only do MOVs so not shown in the code Maybe not work when too near the 999 edge

\$\endgroup\$
-1
\$\begingroup\$

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  

not sure if this is not branching.

\$\endgroup\$
  • \$\begingroup\$ It is branching, only inline. Specifically, the ubiquitous ternary operator (which this essentially is) is not one of the allowed operations. \$\endgroup\$ – tomsmeding Jun 25 '14 at 18:04
  • \$\begingroup\$ Thanks @tomsmeding, may I ask what is the ubiquitous ternary operator (is it IIF() in my code?) \$\endgroup\$ – Alex Jun 25 '14 at 18:55
  • \$\begingroup\$ yes sorry, with ubiquitous I meant that it's present in pretty much every language, and the ternary operator is your IIf, Inline-If. In most languages, it is, for example, a>=b ? a : b. It is branching indeed. \$\endgroup\$ – tomsmeding Jun 25 '14 at 18:57
-1
\$\begingroup\$

JavaScript: 4 tokens (** based on broad interpretation of "assignment"!)

Obviously my score of 4 is extremely generous/lenient!

To arrive at that score I've assumed "assignment" (worth 0 tokens in the question) includes such things as additive assignment, subtractive assignment, multiplicative assignment, and XOR-ing (^=) assignment

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

If those assignments actually count the score is 14 :)

\$\endgroup\$
  • \$\begingroup\$ Because d -= b is actually the same as d = d - b, I would say that you use arithmetic and that you should count this as a token. \$\endgroup\$ – ProgramFOX Jun 26 '14 at 14:27
  • \$\begingroup\$ Yes, I realise that - I was (jokingly) trying to take advantage of the meaning of "assignment". I think I made that fairly obvious! \$\endgroup\$ – jcdude Jun 26 '14 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.