Friday's Coding Challenge
-
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), whereSis the function that does just that.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;}
-
What's the smallest code you can come up with to find the n smallest numbers in a random sample of m numbers where n < m. Any language, speed is not an issue.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
If our list is the_list in Python we have new_list = sorted(the_list)[:n]
-
SELECT TOP n FROM Sample ORDER BY ValueEdit: How should we handle duplicates? -
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;}
And as said in my next post (have a look into the future), passing argument
nis unessential, useminstead and spare 6 characters. -
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;}
You can also get rid of variable
iby 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.
-
What's the smallest code you can come up with to find the n smallest numbers in a random sample of m numbers where n < m. Any language, speed is not an issue.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
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 (mandp), - a swap variable is required (s), - a key comparison is required, - three assignments are required for the swaps, wherever they take place. -
And as said in my next post (have a look into the future), passing argument
nis unessential, useminstead and spare 6 characters.Good point, once you're doing a sort like this, you might as well just sort the whole array.
-
Good point, once you're doing a sort like this, you might as well just sort the whole array.
Yep, they say running time is for free...
-
Good point, once you're doing a sort like this, you might as well just sort the whole array.
And by the way, I have explored an approach where the high values in the array are allowed to be destroyed. Just passing parameter
nspoils this effort ! -
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 (mandp), - a swap variable is required (s), - a key comparison is required, - three assignments are required for the swaps, wherever they take place.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.
-
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.
Nice trick !
-
What's the smallest code you can come up with to find the n smallest numbers in a random sample of m numbers where n < m. Any language, speed is not an issue.
cheers, Chris Maunder The Code Project | Co-founder Microsoft C++ MVP
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.