Restricted minumum

Question

You need to find the sum of minimum values of two list (same size) of small numbers. In a C like language, that could be expressed as:

v = min(a[0],b[0]) + min(a[1],b[1])+ min(a[2],b[2]) ...

The range of values is 0..7 and the 2 list can have up to 7 values. If you like, all the values in each list can be stored as a single 32 bit number.

My goal is avoiding branches in code, so the rules are

• Single line expression,
• No function calls or method calls (except for basic operations like sum, if your language mandate this),
• No if statements, including things that compile to if statements such as ternary operators or "greater than" operators

Edit 1 To clarify, what I want is 'no branches in code'. So, no if, no calls (function of methods). Loops with fixed ranges (0..7) could be OK because can be unrolled. Sorry if was not crystal clear about this.

All what your language can do inline is OK. So if a functional language has a strange syntax that resembles a function call but is inlined, that's OK.

Shortest code wins.

As a side note: this challenge is related to a quasi-real problem: a fast scoring function in mastermind game.

Answer 1

C/C++ with SSE intrinsics (11 instructions)

Because everything's better with SIMD...

inline int foo(const int16_t *a, const int16_t *b) 
{
    __m128i va = _mm_loadu_si128((__m128i *)a);
    __m128i vb = _mm_loadu_si128((__m128i *)b);
    __m128i vmin = _mm_min_epi16(va, vb);
    vmin = _mm_add_epi32(_mm_unpacklo_epi16(vmin, vmin), _mm_unpackhi_epi16(vmin, vmin));
    vmin = _mm_add_epi32(vmin, _mm_srli_si128(vmin, 4));
    vmin = _mm_add_epi32(vmin, _mm_srli_si128(vmin, 8));
    return _mm_cvtsi128_si32(vmin);
}

No branches, loops or function calls. This might not be the shortest source code, but it compiles to just 11 SSE instructions, so I claim shortest generated code.

Answer 2

vb.net

v = a.Zip(b,Function(p,q) Math.Min(p,q)).Sum
v = a.Zip(b,AddressOf Math.Min).Sum 

Edit: A no function call version. Just a single expression.

Dim v = {a(0), a(0), b(0)}(1 + ((a(0) - b(0)) / ((a(0) - b(0)) * (a(0) - b(0)) ^ (1 / 2)))) +
        {a(1), a(1), b(1)}(1 + ((a(1) - b(1)) / ((a(1) - b(1)) * (a(1) - b(1)) ^ (1 / 2)))) +
        {a(2), a(2), b(2)}(1 + ((a(2) - b(2)) / ((a(2) - b(2)) * (a(2) - b(2)) ^ (1 / 2)))) +
        {a(3), a(3), b(3)}(1 + ((a(3) - b(3)) / ((a(3) - b(3)) * (a(3) - b(3)) ^ (1 / 2)))) +
        {a(4), a(4), b(4)}(1 + ((a(4) - b(4)) / ((a(4) - b(4)) * (a(4) - b(4)) ^ (1 / 2)))) +
        {a(5), a(5), b(5)}(1 + ((a(5) - b(5)) / ((a(5) - b(5)) * (a(5) - b(5)) ^ (1 / 2)))) +
        {a(6), a(6), b(6)}(1 + ((a(6) - b(6)) / ((a(6) - b(6)) * (a(6) - b(6)) ^ (1 / 2)))) +
        {a(7), a(7), b(7)}(1 + ((a(7) - b(7)) / ((a(7) - b(7)) * (a(7) - b(7)) ^ (1 / 2))))

Note: Above fails in a(x)=b(x) as a(x)-b(x) = 0 which results in divide by zero .

((a(0) - b(0)) / ((a(0) - b(0)) * (a(0) - b(0)) ^ (1 / 2)))
 delta = a(x)-b(x)
   abs = (delta * delta)^(1/2)  ; Sqr(delta^2) 
  sign = delta / abs            ; This is where the 0/0 happens. 
 index = sign + 1               ; Since sign in normalise to -1 to +1
                                ; when need offset it by +1 for 0-Indexed arrays.

Version using < in mathematical sense. (akin to @Heiko Oberdiek entry)

Dim v = {a(0),b(0)}((a(0)<b(0))+1)+{a(1),b(1)}((a(1)<b(1))+1)+{a(2),b(2)}((a(2)<b(2))+1)+{a(3),b(3)}((a(3)<b(3))+1)+
        {a(4),b(4)}((a(4)<b(4))+1)+{a(5),b(5)}((a(5)<b(5))+1)+{a(6),b(6)}((a(6)<b(6))+1)+{a(7),b(7)}((a(7)<b(7))+1)

Answer 3

APL, 7 (should be invalid)

v←+/a⌊b

a⌊b is the minimum of each corresponding pair of items.

+/ adds everything together in the last dimension, which is the only dimension in this case.

Thanks to Adam Speight who pointed out that these symbols are called "functions" in APL. So this answer should be invalid and not fixable...

Answer 4

Perl, 52 bytes

$v+=(($A=$a[$_])<=($==$b[$_]))*$A+($A>$=)*$=for 0..7

It is a single line expression without functions and if statements.

In an updated question, loops are excluded because of the end condition. In this case the for operator unfolds an array. It is not clear, whether this is acceptable or not, thus it is something for the OP to decide. (Of course, for could be avoided by making the summation explicit, but such a solution would be too boring for me).

The input numbers are expected in arrays @a and @b. The sum is stored in $v. (If it is used a second time, $v needs to be reset to zero.)

The minimum summand for each value in the index array 0..7 is calculated and added to the result variable $v. As far as I have understood the question, the for operator is not excluded.

The result of the comparison operators <= and > are not used inside an if condition, but in a numerical context.

Ungolfed with test:

@a = (1,7,3,4,5,0,3);
@b = (3,1,4,1,5,2,6);
$v = 0;

for $_ (0..7) {
    $A = $a[$_];
    $B = $b[$_];
    $v += ($A <= $B) * $A
        + ($A > $B) * $B
}
# The use of $= instead of $B in the golfed version saves one byte.

print  "Result: $v\n";

Result: 14

Answer 5

C, 81 68

Not the shortest, but I found this interesting, so here's mine. Thanks to @edc65 for the improvement, which is not only shorter, but also faster.

int s,i;for(s=i=0;i<7;s+=(((x[i]-y[i])>>31)&(x[i]-y[i]))+y[i],i++);

Just &, shift, multiplication and addition, no division. Replace 0x80000000 and 31 with the appropriate constants for non-4-bytes ints. Loop can be unrolled (and gcc with -O3 unrolls it for me.) Usage:

int main(void) {
  signed int x[7] = {1,2,3,4,5,6,7};
  signed int y[7] = {9,0,5,7,1,2,7};
  int s,i;
  for (s=0,i=0;i!=7;s+=(((x[i]-y[i])&0x80000000)>>31)*(x[i]-y[i])+y[i],i++);
  return s; 
}

produces

gcc min_bare.c && ./a.out ; echo $?
18

Let's compare with the forked if version (b)

if x[i] > y[i]
  s+=y[i]
else
  s+=x[i]
end

and with (c)

s+= ((x[i] > y[i]) ? y[i] : x[i]);

Let's benchmark with (taking the arrays from stdin)

int main(void) {
  int l,i,j,s;
  scanf("%d",&l);
  signed int x[l], y[l];
  for (i=0; i!=l; scanf("%d",&(x[i++])));
  for (i=0; i!=l; scanf("%d",&(y[i++])));
  for (j=0; j!=99999999;j++) {
    for (s=0,i=0;i!=l;i++) {
      // put code to test here
    }
  }
  printf("%d\n",s);
  return 0;
}

The if version (b) takes ~4.3s, version (c) ~3.4s, the original ~5.3s ~4.3s; all with -O3. So don't optimize prematurely ; )

Answer 6

JavaScript - 84 89 97 98

The code:

for(s=i=7;i--;s+=x*r/r|0+y*l/l|0){x=~-a[i];y=~-b[i];l=0xff&1<<(x-y);r=0xff&1<<(y-x)}

49 if the comparison operators are allowed in numerical context:

for(s=i=7;i--;s+=(x=~-a[i])-(x-y)*(y<x))y=~-b[i];

The input is in the a and b arrays. The result is stored in the s variable.

Ungolfed version:

for(s = i = 7; i--; s += x*r/r|0 + y*l/l|0, --s) {
    // Get the last elements of the arrays
    x = a[i];
    y = b[i];

    // Calculate which is greater
    l = 0xff & 1 << (x - y);
    r = 0xff & 1 << (y - x)
}

Sample usage:

> a=[1,4,3];b=[2,3,5];
[ 2, 3, 5 ]
> for(s=i=7;i--;s+=x*r/r|0+y*l/l|0,--s){x=a[i];y=b[i];l=0xff&1<<(x-y);r=0xff&1<<(y-x)}
4
> s
7

Answer 7

Perl, 42

$s+=($a[$_],$b[$_])[$b[$_]<$a[$_]]for 0..7

I expect scripting/C-like languages with sigil-free syntax will fare slightly better in terms of their code-golf scores. Loops over the indices and creates a list with the element from @a and @b. The index is determined by the result of the < comparison.

Just for kicks, one could write the following to make the logic scale for any number of elements by selecting the upper limit for the index variable to be the larger of $#a or $#b:

$s+=($a[$_],$b[$_])[$b[$_]<$a[$_]]for 0..($#a,$#b)[@a<@b]

Answer 8

J (9)

v=:+/a<.b

Someone is going to need to help me out on this one. Does this match the rules?

Single line expression

Check.

No function calls or method calls (except for basic operations like sum, if your language mandate this)

The things J is made of are called verbs (it is basically impossible to write any J without verbs), are those considered functions?

No if statements, including things that compile to if statements such as ternary operators or "greater than" operators

<. is basically equal to min, and +/ is basically equal to sum. Are those considered to compile to if statements?

Answer 9

Golfscript, 13

0\~zip{$0=+}/

The arguments have to be passed to the program as a list of the two lists (e.g. [ [0 1 2] [4 2 0] ]). I'm really not sure if it matches the rules, though (you said you won't forbid basic list operations? - zip in this case).

Explanation:

• Golfscript pushes the arguments it get as a string into the stack before the program runs.
• 0\ pushes 0 and switching top elements of the stack (will be used for the sum).
• ~ executes the code in the string, which is just pushing the array down the stack.
• zip transposes array's rows with columns (e.g. [[0 1 2][4 2 0]] -> [[0 4][1 2][2 0]]).
• {...}/ executes a block ({...}) over each element of the array.
• $0=+ sorts each array in the big array gets the first element and adds to the "sum".

At the end of the program only the sum is left on stack and the stack values are printed.