Friday's Coding Challenge

[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 !

[Trajan McGill]

Actually, we can do away with one of the loops if we make use of some evaluation short circuiting trickery to make one loop act like two. Thus this:

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

becomes this:

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

which saves us one whole character. :) It might be possible to figure out a way to cut off a couple more, I'm not sure. I've considered, but not had enough time to exhaust, possibilities like going forward vs. backward on either one or both of the iterators, using a pointer rather than an index into the array, whether sorting in reverse order (putting the smallest elements at the end of the array rather than the beginning) might help, and the possibility of somehow using the array itself for swapping to eliminate a variable, but probably most of these are going to add code rather than reduce it. There's also the possibility of a recursive solution, but I haven't really tried that at all. I have to go do some real work, unfortunately, but this C solution is getting surprisingly close in length to some of the solutions using languages with handy built-in functions to do this sort of thing.

[YvesDaoust]

Nice trick !

[Member 8085210]

Let x be such a sample. Then x[rank(x)<=n] is such a subsample, in R. If there are elements in the sample that are repeated and you want the first n different numbers, it is a bit more complicated, since you have to check first that there are at least n different elements in your sample, using ux<-unique(x), for instance.