-3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Would you allow basic list operations in functional languages (like map and fold)? At minimum, you can create all of the other common operations from fold. \$\endgroup\$ – Jwosty Jun 22 '14 at 21:54
  • \$\begingroup\$ Also what about recursion and pattern matching? \$\endgroup\$ – Jwosty Jun 22 '14 at 21:55
  • \$\begingroup\$ @Jwosty Recursion involves function call (I think). I'm not fluent in functional languages, but I can't forbid basic list operation in (for instance) lisp. \$\endgroup\$ – edc65 Jun 22 '14 at 21:58
  • 3
    \$\begingroup\$ That's the second question I've seen recently which talks about comparison operators being compiled to if statements. What weird architecture does this? \$\endgroup\$ – Peter Taylor Jun 22 '14 at 22:07
  • 2
    \$\begingroup\$ Also, how do you expect us to iterate the array without branching? The code will have to know when to stop at some point... \$\endgroup\$ – Jwosty Jun 22 '14 at 22:41
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I really like it, but can't find any reference to _mm_loadu_epi16 (software.intel.com/sites/landingpage/IntrinsicsGuide) \$\endgroup\$ – edc65 Jun 22 '14 at 23:37
  • \$\begingroup\$ Sorry - I used one of my personal convenience macros without thinking - it's really just _mm_loadu_si128. I've updated the answer. \$\endgroup\$ – Paul R Jun 23 '14 at 5:29
2
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ I see Zip and Min as function calls, dont'you? \$\endgroup\$ – edc65 Jun 22 '14 at 21:20
  • \$\begingroup\$ min is a function call also. \$\endgroup\$ – Adam Speight Jun 22 '14 at 21:23
  • \$\begingroup\$ yes the core of the challenge is avoid it. \$\endgroup\$ – edc65 Jun 22 '14 at 21:26
  • \$\begingroup\$ +1 Not fast but clever. Is this {} a recent addition to VB? \$\endgroup\$ – edc65 Jun 22 '14 at 21:54
  • \$\begingroup\$ It has had someingthing akin to them since at least VS2005 release (VB8?) VB also has another alternative CHOOSE( ). \$\endgroup\$ – Adam Speight Jun 22 '14 at 22:01
1
\$\begingroup\$

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...

\$\endgroup\$
  • \$\begingroup\$ Please use some of that 30 chars for an explanation... \$\endgroup\$ – edc65 Jun 22 '14 at 21:27
  • \$\begingroup\$ @user23013 Aren't you also using Dyadic functions \$\endgroup\$ – Adam Speight Jun 22 '14 at 21:37
  • \$\begingroup\$ @AdamSpeight You are right... \$\endgroup\$ – jimmy23013 Jun 22 '14 at 21:50
  • \$\begingroup\$ But I doubt what will happen if someone say methods are not called functions in some languages. \$\endgroup\$ – jimmy23013 Jun 22 '14 at 22:16
  • \$\begingroup\$ Not using functions in a functional language is quite hard. \$\endgroup\$ – seequ Jun 23 '14 at 14:26
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ The for is OK for me, I tried to clarify again. \$\endgroup\$ – edc65 Jun 22 '14 at 22:41
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice answer. Fiddling with it I found this one, that is shorter and faster (avoidig multiply): s += ( ( (x[i]-y[i]) >>8 ) & (x[i]-y[i]) ) + y[i]; (shift more, up to 31, for bigger numbers) \$\endgroup\$ – edc65 Jun 23 '14 at 12:31
  • \$\begingroup\$ Nice find. Runtime-wise, this puts it on par with the if-version. And I learned something new. I had the wrong idea about the binary representation of signed ints, or rather the definition of the shift operator - it will preserve the sign bit. Took me a bit to figure out why your improvement works ; ) \$\endgroup\$ – blutorange Jun 23 '14 at 14:19
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I like the count down with the offset in the sum. As is, the short code is broken. But with little effort you can modify it to score no more than 47 with just shift, +, - . \$\endgroup\$ – edc65 Jun 23 '14 at 15:08
  • \$\begingroup\$ @edc65 It's working now, but I can't make it less than 49 bytes :( \$\endgroup\$ – core1024 Jun 23 '14 at 18:56
1
\$\begingroup\$

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

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?

\$\endgroup\$
  • \$\begingroup\$ While I don't want limit the challenge to imperative languages, it's difficult to apply the rules to functional languages. The problem here is the verb(s) <. that maps to either an inlined if a < b then a else b or to a library function that do the same. \$\endgroup\$ – edc65 Jun 23 '14 at 7:43
  • \$\begingroup\$ @edc65 it's more like Python's [min(c,d) for c,d in zip(a,b)]. One could argue that min = lambda a,b: a if a < b else b, and that it also should be excluded, but that's also used in other answers. TL;DR: I'm not sure. \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Jun 23 '14 at 7:49
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Can you add some explanation? I'm not fluent in Golfscript. \$\endgroup\$ – edc65 Jun 23 '14 at 22:44

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.