Skip to main content
GameDev.net gamedev.net
🔒 Locked

Extremely Basic but Challenging Programming Problem

Started by haro Jul 24, 2004 at 8:37 PM 40 replies 5.6k views
Original Post
haro
haro
Assume you have an array of 4 random floats. What is an elegant way to put the indices for the 3 smallest floats into a 3 integer array? You cannot change the values inside the float array. I ran into this problem during some work tonight. At first I just brute forced it, but was embarrassed at how much code there was to accomplish such a simple task. I spent about 15 minutes(!!!) coming up with a clean solution for fun. I've finally come up with what I think is the best solution, but I'm not positive. My current solution is still 6 lines of "simple" ( ie- single / unnested ) commands. It would be terribly embarrassing to get such a simple question on a programming test and not be able to instantly spit out a good answer. So what's your solution??
MoRRiS2
MoRRiS2 
float[4] randArray;float[3] smallIndices;-------------------------float max = randArray[0];unsigned int maxIndex = 0;for(unsigned int i = 1; i < 4; i++){     if(max < randArray){         max = randArray;         maxIndex = i;     }}unsigned int smallIndex = 0 for(unsigned int i = 0; i < 4; i++){     if(i != maxIndex){          smallIndices[smallIndex] = i;          smallIndex++;     }}


What do you think? that's what I came up with on the fly.
Yeah, it's messy and unclean, but it gets the job done. Probably could be cleaned up by using the standard library to find the max index instead... but this way no need to link in anything.
O(n) too.
haro
haro
It can still get quite a bit cleaner - I didn't use the STL in my solution either. That is almost exactly what my first solution looked like.
eleusive
eleusive
You could use the STL and do like so:

float array[4];float array2[3];//insert elements heresort(array,array+4);copy(array,array+3,array2);

"What are you trying to tell me? That I can write an O(N^2) recursive solution for a 2-dimensional knapsack?" "No, programmer. I'm trying to tell you that when you're ready, you won't have to." -Adapted from "The Matrix"
Beer Hunter
Beer Hunter
Do the indices need to be in any particular order?
Xai
Xai
well, the elements of the BEST possible solution depend on the answer to a question or two.

Is it preferable that the code be the most efficient possible, or that the code be the cleanest most maintainable possible.

Is it preferable that the code be written specifically for this case of 4 floats, 3 indices, etc ... or is it preferable that the code be visibly a solution of the general case (whatever that is - possibly "given a list of size n, find the indices of the m smallest objects")
haro
haro
Quote:
Original post by Beer Hunter
Do the indices need to be in any particular order?


Nope, just the three lowest.
Beer Hunter
Beer Hunter
In that case...
    float f[4] = {100.0f, 150.0f, 250.0f, 200.0f}; // or whatever    int i = std::max_element(&f[0], &f[4]) - &f[0];    int something[3] = {i<=0?1:0, i<=1?2:1, i<=2?3:2};
A little ugly, but you get the idea.
haro
haro
Quote:
Original post by Xai
well, the elements of the BEST possible solution depend on the answer to a question or two....


Right now I'm just looking for the most 'elegant' ( which probably comes down to being the fewest lines of code ) solution the problem. I'm amazed that something so relatively simple and algorithmic in nature can be so difficult to express in code.
eleusive
eleusive
Come to think of it, a better way to do this using STL would be:

float array[4], array1[3];for(int c=0, pos=0;c<4;c++)   if(c!=max_element(array,array+4))       array1[pos++]=array[c];


This is better than my previous solution because it leaves the elements of array unchanged.
"What are you trying to tell me? That I can write an O(N^2) recursive solution for a 2-dimensional knapsack?" "No, programmer. I'm trying to tell you that when you're ready, you won't have to." -Adapted from "The Matrix"
haro
haro
Quote:
Original post by Beer Hunter
In that case...*** Source Snippet Removed ***A little ugly, but you get the idea.


Neat idea using std::max_element(&f[0], &f[4]) - &f[0] to get the index of the max element!

Here is my solution:

int max = 0;for( int i = 0; i < 4; i++ )	if( distances > distances[max] )		max = i;int mins[3] = { 0,1,2 };if( max != 3 )	mins[max] = 3;
haro
haro
Quote:
Original post by eleusive
Come to think of it, a better way to do this using STL would be:

* code snipped *

This is better than my previous solution because it leaves the elements of array unchanged.


Not many lines of code but O(n^2)!
haro
haro
Can the solution get better than:

int max = std::max_element(&distances[0], &distances[4]) - &distances[0];int mins[3] = { 0,1,2 };if( max != 3 )	mins[max] = 3;
O_o
O_o 
float f[4] = {150.0f, 100.0f, 200.0f, 50.0f};int i[3] = {0, 1, 2};int max = 3;for(int x = 0; x < 3; x++)	if(f[x] > f[max]) {		i[x] = max;		max = x;	}


[Edited by - O_o on July 24, 2004 9:36:50 PM]
haro
haro
Quote:
Original post by O_o
*** Source Snippet Removed ***


Unfortunately, that only works when f[3] is the highest or 2nd highest value.
O_o
O_o
nm
JohnBolton
JohnBolton 
int indexes[3] = { 0, 1, 2 };int max = 3;for ( i = 0; i < 3; ++i ){    if ( values > values[max] )    {        indexes = max;        max = i;    }}


O_o: Yours doesn't work with { 4.0, 3.0, 2.0, 1.0 }
John BoltonLocomotive Games (THQ)Current Project: Destroy All Humans (Wii). IN STORES NOW!
JohnBolton
JohnBolton 
int i[3];i[0]=v[0]>v[3]?3:0;i[1]=v[0]>v[3]?v[1]>v[0]?0:1:v[1]>v[0]?3:1;i[2]=v[0]>v[3]?v[1]>v[0]?v[2]>v[1]?1:2:v[2]>v[0]?0:2:v[1]>v[0]?v[2]>v[1]?1:2:v[2]>v[3]?3:2;

I hope the order of evaluation is right.
John BoltonLocomotive Games (THQ)Current Project: Destroy All Humans (Wii). IN STORES NOW!
Hylo
Hylo
Let me know if it doesnt work..

float f[4] = {4.0f, 3.0f, 2.0f, 1.0f};int mins[3] = { (f[3]<=f[2]?3:2),(f[1]<f[0]?1:0), f[(f[3]>f[2]?3:2)] < f[(f[0]>f[1]?0:1)] ? (f[3]>f[2]?3:2) : (f[0]>f[1]?0:1) };
KrishnaPG
KrishnaPG
>haro
> Posted - 7/24/2004 10:17:14 PM
>Can the solution get better than:

int max = std::max_element(&distances[0], &distances[4]) - &distances[0];
int mins[3] = { 0,1,2 };
if( max != 3 )
mins[max] = 3;


Dear,

That was really an elegent solution. Congarts Haro. I liked it.
The below is same as the above but without std::max_element()

int mins[3] = {0,1,2}, nMax = 3;for(int i=0; i <=2 ; ++i)  if(distances > distances[nMax])  {       mins = nMax;       nMax = i;  }


This is better than std::max_element() because we do not scan the entire flot array atleast once (std::max_element() has to scan the arrray atleast once completely). If you observe we just do upto i<=2.

By the way, this problem of finding k-largest or k-smallest is a classical problems and almost every book on algorithms disucesses this. They propose more general approaches such as using the QuickSort with pivot checkings. (Here in our case we have fixed k value 3.)

And as for your comment that this simple problem needed so complex a solution - I hope you would agree with the following well known truth
"Complexity of problem statement has nothing to do with the complexity of solution". In other words, "the concept of Dog does'nt bark !!"
For eg. the simplest problem of "given a product of two prime numbers, find its factors" has no known solution till now !!

Thanking you,
Yours,
P.GopalaKrishna.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.