Friday's Coding Challenge

[Gary Wheeler]

You win the "We Can't Judge Your Submission Because It's Incomprehensible" award.

Software Zen: delete this;

[parths]

void find_n_in_m(int *mData, int *nData, unsigned int m, unsigned int n)
{
unsigned int ctr, ctr2 = 0;
for(unsigned int i = 0; i < n; i++)
nData[i] = mData[i];
m--;
while (((ctr = m) && (m >= n))
&& ((mData[ctr] >= nData[ctr2]) ?
((++ctr2 < n) || (ctr2 = 0) || m--) :
(((mData[ctr] ^= nData[ctr2]) && (nData[ctr2] ^= mData[ctr]) && (mData[ctr] ^= nData[ctr2]) && (ctr2 = 0)) || 1)
));
}

- Doesn't give a sorted list - Modifies the input array (nothing mentioned against that in the specification but that can be avoided by adding an input argument for an temp / scratch buffer of the same size as the source buffer) - Tried it on VS2008 Express Ed and with a few basic data so I don't know if it's correct for all inputs. - What it does is fill the destination with the first n elements then goes about trying to see if it can place the elements from n to m into the new array. Thought I'd post it while I'm trying to improve ( :~ ) it.

"It was when I found out I could make mistakes that I knew I was on to something." -Ornette Coleman "Philosophy is a study that lets us be unhappy more intelligently." -Anon.

[Single Step Debugger]

void Test()
{
int arr[] = {1, 4, 6, 8, 9};
int nNumToGet = 3;

int \*arr2 = ReturnLowerN(arr, sizeof(arr)/sizeof(int), nNumToGet);

}

int* ReturnLowerN(int *arr, int arrSize, int nNum)
{
std::sort(arr, arr + 5, std::greater<int>());

return(arr + arrSize - nNum);

}

Of course if you want to use qsort instead, here is an article from someone you may know. :-D Using qsort on arrays of sequential data[^]

There is only one Vera Farmiga and Salma Hayek is her prophet! Advertise here – minimum three posts per day are guaranteed.

[Daniel Grunwald]

BobJanova wrote:

Well, if not, it is obviously possible to invent a language where one symbol does this operation

Why one symbol? If you're inventing a new language, you might as well invent one where the empty program solves this challenge.

[Roger Wright]

I wasn't aware that the Betty Ford Clinic has a hamster wing. How very nice. I hope they enjoy the rest. :-D

Will Rogers never met me.

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