Friday's Coding Challenge

[Luc Pattyn]

I was thinking about APL too. It has been over 30 years I touched it though. :)

Luc Pattyn [My Articles] Nil Volentibus Arduum

[YvesDaoust]

My attempt in plain C:

for (i= 0; i < m; i++)
{
int r= 0;
for (j= 0; j < m; j++)
r+= a[j] < a[i];
if (r < n)
printf("%d\n", a[i]);
}

It simply evaluates the rank of every element. Unfortunately, this method cannot meet the specs in case of equal elements. Actually, it reports all elements with rank less than n.

[YvesDaoust]

Slightly modified Straight Selection Sort will do the trick (moves n lowest elements first):

for (int i= 0; i < n; i++)
{
int k = i;
for (int j= i; j < m; j++)
{
if (a[k] > a[j])
{
k = j;
}
}

int swap= a\[i\]; a\[i\]= a\[k\]; a\[k\]= swap;

}

IMHO, allowing function calls makes the challenge nonsensical, as the solutions reduces to S(a, m, n), where S is the function that does just that.

[YvesDaoust]

If you don't care about time, sort the whole array and parameter n is virtually useless !

S(a, m); // Solution in a[0..n-1]

where S stands for some sorting algorithm on an array. Slightly shorter in Python, assuming a has length m:

S(a) # Solution in a[0..n-1]

[George Danila]

var nSmallestNumbers = numbers.OrderBy(x => x).Take(n);

[BobJanova]

Thanks but it's actually simple and the same as everyone else's:

f←{
sorted←⍵⌷⍨⍋⍵; // sorts the right argument
⍺↑sorted // first n items (n = left argument)
}

[User 8615306]

maybe in F# (doesn't check if n < X.Length): let nsmallest X n = (Array.sort X).[0..(n-1)]

[Spectre_001]

// Setup
int n = 2;
int[] m = { 3, 5, 7, 1, 8, 4, 2 };
int[] smallest = (int[])Array.CreateInstance(typeof(int), n);

// My answer
Array.Sort(m); Array.ConstrainedCopy(m, 0, smallest, 0, n);

Kevin Rucker, Application Programmer QSS Group, Inc. United States Coast Guard OSC Kevin.D.Rucker@uscg.mil "Programming is an art form that fights back." -- Chad Hower

[eltashi]

Hi there, nice challenge ! Didn't want to use language built in array sorting, since that makes the solution obvious. Ok ok, recursion is dangerous, but looks nice :)

function reduceTo(arr,n){

if (n==arr.length) return arr;
var next=Array();
	
for (i=0,max=0; i\=arr\[max\]) {
		if (max!=i) next\[next.length\]=arr\[max\];
		max=i;
	}
	else{
		next\[next.length\]=arr\[i\];
	}
}

return reduceTo(next,n);

}

[faceless5579]

in Java :-) (without dublicates handling) // given an array of ints: m // and a number n, for example n =4 // we can use a java.util.TreeSet (that is, ordered set) to do the job: TreeSet result = new TreeSet (); for (int mcnt=0; mcnt < m.length ; mcnt++) if (result.size() < n) { result.add(m[mcnt]); continue; } else { int curMax = result.last(); if (curMax > m[mcnt]) { result.remove(curMax); result.add(m[mcnt]); } }

[Trajan McGill]

A submission in C:

#include
int*f(int*s,int m,int n){int i,c,*a=(int*)malloc(n*sizeof(int));for(;n;m--,s++){for(i=1,c=0;i
Assumptions: the numbers are integers, "smaller" for negative numbers means "more negative", and the initial set of numbers is stored as an array. A different data structure would require reworking the algorithm, but the first two assumptions are easy to change with a few extra bytes-- for instance, for doubles, we can do it as:

#include
#define D double
D*f(D*s,int m,int n){int i,c;D*a=(D*)malloc(n*sizeof(D));for(;n;m--,s++){for(i=1,c=0;i
and for a "closer to zero" definition of smaller numbers, the integer version would change to:

#include
#include
int*f(int*s,int m,int n){int i,c,*a=(int*)malloc(n*sizeof(int));for(;n;m--,s++){for(i=1,c=0;i
If you test it, don't forget to free() the returned array. And for heaven's sake, don't ever write real code like this (and I don't just mean the formatting).

[Trajan McGill]

Ahh, shoot, you're right. The requirements didn't specify a non-destructive algorithm. Your method, turned into an actual function, with a few optimizations and a bit of non-essential character elimination, reduces to:

void g(int*a,int m,int n){int i=0,j,k,t;for(;ia[j])k=j;}

which beats mine by 50 characters (49 if I chop out the one removable whitespace character I missed in my solution). If we modify it further to toss out the array notation and instead do horrible things with pointers, we can even save 6 more:

void g(int*a,int m,int n){int*i=a,*j,*k,t;for(;i*j)k=j;}

[Bob Beechey]

If our list is the_list in Python we have new_list = sorted(the_list)[:n]

[KP Lee]

That won't work in sql. :) (n isn't a number and value isn't selected)

[YvesDaoust]

And as said in my next post (have a look into the future), passing argument n is unessential, use m instead and spare 6 characters.

[YvesDaoust]

You can also get rid of variable i by working backwards, and benefit from a little of C's syntaxic sugar:

void g(int a[], int m)
{
while (m)
{
int k= --m, j= m;
while (j)
k= a[k] < a[--j] ? k : j;

	int s= a\[m\]; a\[m\]= a\[k\]; a\[k\]= s;
}

}

(This code guaranteed unchecked for correctness :-)) Applying your transforms should give something shorter than ever.

[YvesDaoust]

This is a straight selection sort, processing back to front and doing immediate swaps to avoid index bookeeping.

void g(int a[], int m)
{
for (int s, p; p= --m;)
while (p--)
if (s= a[m], a[p] > s)
a[m]= a[p], a[p]= s;
}

or, said shortly,

void g(int*a,int m){for(int s,p;p=--m;)while(p--)if(s=a[m],a[p]>s)a[m]=a[p],a[p]=s;}

The requested solution lies in a[0..n-1]. I guess it will be hard to improve on this straight selection approach, given that - two nested loops are required, - two decreasing indexes are required (m and p), - a swap variable is required (s), - a key comparison is required, - three assignments are required for the swaps, wherever they take place.

[Trajan McGill]

Good point, once you're doing a sort like this, you might as well just sort the whole array.

[YvesDaoust]

Yep, they say running time is for free...

[YvesDaoust]

And by the way, I have explored an approach where the high values in the array are allowed to be destroyed. Just passing parameter n spoils this effort !