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\$
10
  • \$\begingroup\$ What about defining an extra function? If this is allowed, how many tokens does it count as? \$\endgroup\$
    – afuous
    Jun 25, 2014 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, 2014 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, 2014 at 0:36
  • \$\begingroup\$ @primo I specifically asked for 3 inputs because it actually allows for some interesting improvements \$\endgroup\$
    – qwr
    Jun 25, 2014 at 0:39
  • 2
    \$\begingroup\$ Can we use inbuilt functions? \$\endgroup\$ Jun 25, 2014 at 4:44

15 Answers 15

11
\$\begingroup\$

Javascript

6 tokens

function maxOf3(a, b, c) {
    (b>a) && (a=b);
    (c>a) && (a=c);
    return a;
}
\$\endgroup\$
6
  • 6
    \$\begingroup\$ +1 I see shortcut evaluation as a type of branching, but it's not forbidden in the rules \$\endgroup\$
    – edc65
    Jun 25, 2014 at 1:33
  • 12
    \$\begingroup\$ I would consider this as branching, haha \$\endgroup\$
    – justhalf
    Jun 25, 2014 at 2:52
  • 3
    \$\begingroup\$ @edc65 It is. Allowing && and || was likely an oversight, which should be pointed out, rather than exploited. \$\endgroup\$
    – primo
    Jun 25, 2014 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, 2014 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, 2014 at 12:40
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
  • 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, 2014 at 0:48
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\$
2
  • 1
    \$\begingroup\$ You are not allowed to create new functions \$\endgroup\$
    – qwr
    Jun 25, 2014 at 1:16
  • \$\begingroup\$ :( 14 tokens then \$\endgroup\$
    – Fabricio
    Jun 25, 2014 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\$
5
  • \$\begingroup\$ You are not allowed to create new functions \$\endgroup\$
    – qwr
    Jun 25, 2014 at 9:28
  • \$\begingroup\$ Ahh ok! Didn't read the comments :) \$\endgroup\$
    – Mardoxx
    Jun 25, 2014 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, 2014 at 14:40
  • 1
    \$\begingroup\$ @Cruncher I edited the answer I did max2(max2(x,y),z) initially :) \$\endgroup\$
    – Mardoxx
    Jun 25, 2014 at 15:02
  • \$\begingroup\$ @Mardoxx ah. Well +1 \$\endgroup\$
    – Cruncher
    Jun 25, 2014 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\$
5
  • \$\begingroup\$ Fail for big numbers (>2^30), see comment codegolf.stackexchange.com/questions/32476/#comment68870_32477 \$\endgroup\$
    – edc65
    Jun 25, 2014 at 21:08
  • \$\begingroup\$ Looks fine to me: ideone.com/pEsvG3 \$\endgroup\$
    – Riot
    Jun 26, 2014 at 8:06
  • \$\begingroup\$ Did you atctually read the comment? I think 2billions is greater than 0 [ideone.com/vlcnq9 ] \$\endgroup\$
    – edc65
    Jun 26, 2014 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, 2014 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, 2014 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\$
1
  • \$\begingroup\$ Please write actual code, and provide the count of tokens in your answer. \$\endgroup\$
    – ProgramFOX
    Jun 25, 2014 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\$
3
  • \$\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, 2014 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, 2014 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, 2014 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\$
2
  • \$\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, 2014 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, 2014 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.