Skip to main content
added 1608 characters in body
Source Link
Doorknob
  • 72.1k
  • 20
  • 146
  • 393
n; // define sum as an integer f(x,y,a,b) // function taking two arrays and two lengths int*x,*y; // use k&r style definitions to shorten function declaration { for(n=0; // initialize sum to 0 a;) // keep looping until x (the first array) runs out // we'll decrement a/b every time we increment x/y respectively --b&& // if y has ≥1 elements left (b>1, but decrements in-place)... *x*2-*y>y[1]? // ... and x - y > [next y] - x, but rearranged for brevity... ++y: // increment y (we already decremented b earlier); (++b, // otherwise, undo the in-place decrement of b from before... --a,n+=abs(*x++-*y)) // decrement a instead, add |x-y| to n, and then increment x ;} 

Some notes:

  • Instead of indexing into the arrays, incrementing the pointers and dereferencing directly saves enough bytes for it to be worth it (*x vs x[a] and y[1] vs y[b+1]).

  • The --b&& condition checks for b>1 in a roundabout way - if b is 1, it will evaluate to zero. Since this modifies b, we don't need to change it in the first branch of the ternary (which advances y), but we do need to change it back in the second (which advances x).

  • No return statement is needed, because black magic. (I think it's because the last statement to be evaluated will always be the n+=... expression, which uses the same register as the one used for return values.)

n; // define sum as an integer f(x,y,a,b) // function taking two arrays and two lengths int*x,*y; // use k&r style definitions to shorten function declaration { for(n=0; // initialize sum to 0 a;) // keep looping until x (the first array) runs out // we'll decrement a/b every time we increment x/y respectively --b&& // if y has ≥1 elements left (b>1, but decrements in-place)... *x*2-*y>y[1]? // ... and x - y > [next y] - x, but rearranged for brevity... ++y: // increment y (we already decremented b earlier); (++b, // otherwise, undo the in-place decrement of b from before... --a,n+=abs(*x++-*y)) // decrement a instead, add |x-y| to n, and then increment x ;} 

Some notes:

  • Instead of indexing into the arrays, incrementing the pointers and dereferencing directly saves enough bytes for it to be worth it (*x vs x[a] and y[1] vs y[b+1]).

  • The --b&& condition checks for b>1 in a roundabout way - if b is 1, it will evaluate to zero. Since this modifies b, we don't need to change it in the first branch of the ternary (which advances y), but we do need to change it back in the second (which advances x).

  • No return statement is needed, because black magic. (I think it's because the last statement to be evaluated will always be the n+=... expression, which uses the same register as the one used for return values.)

Source Link
Doorknob
  • 72.1k
  • 20
  • 146
  • 393

C (gcc), 82 bytes

n;f(x,y,a,b)int*x,*y;{for(n=0;a;)--b&&*x*2-*y>y[1]?++y:(++b,--a,n+=abs(*x++-*y));} 

This takes input as two integer arrays and their lengths (since C has no way to get their length otherwise). This can be shown to run in O(a+b) because either a or b is decremented on each iteration of the loop, which terminates when a reaches 0 (and b cannot be decremented below 0).

Try it online!