Sign in to follow this  
one mind

Need help writing algorithm

Recommended Posts

Hello, I have a simple little problem that i cant seem to solve. I have a list of numbers, which are players scores. For example, a list of integers: 2 5 3 9 1 6 9 It is quite a simple algorithm to find the player with the highest score by assuming the first score is the largest then iterating the list and replacing it with one larger than it. However, i run in to a problem when 2 or more players draw. Ie They all have the same highest score like in the above example, players 4 and 8 both have the highest score of 9. Should i reiterate the list and return all players that have the high score which was found in the first iteration? How do you return more than one result?

Share this post


Link to post
Share on other sites
You didn't supply enough information, Like what language.
A function can basically return only one value, whether you need to return both players, check what was written in the assignment given to you...

Share this post


Link to post
Share on other sites
Except that the returned value may potentially (perhaps depending on the language in question; I'm not sure) itself contain multiple values... ;)

(That's not the only way around the problem either, I wouldn't say, for that matter, but is probably a good way for this application, based on what you've provided.)

Share this post


Link to post
Share on other sites
Your result is an array/vector/list and not single value. Potentially you get worst case where all players draw. Thus your interface will look something like this in semi c++ pseudocode:

void findWinners(const vector& playerResults, vector& winners)

or

vector findWinners(const vector& playerResults)

depending what language you use.


it must be true that playerResults.length >= winners.length.

Share this post


Link to post
Share on other sites
- Sort the list
- Let Highest be first element
- Iterate through list while (current element equals Highest), increment Count on each iteration


When done, Count will contain number of highest scorers (one or more).

This requires no extra storage, and no complications with return values, in case your language isn't memory managed.



Share this post


Link to post
Share on other sites
Here's a version in C#:


public class Player
{
private string playerID;
private int score;

public string PlayerID
{
get
{
return this.playerID;
}
}

public int Score
{
get
{
return this.score;
}
}

public Player(string playerID, int score)
{
this.playerID = playerID;
this.score = score;
}
}

public class Scorer
{
public Player[] GetTopScores(Player[] players)
{
List<Player> result = new List<Player>();
int maxScore = int.MinValue;

foreach (Player currentPlayer in players)
{
if (currentPlayer.Score == maxScore)
{
result.Add(currentPlayer);
}
else if (currentPlayer.Score > maxScore)
{
maxScore = currentPlayer.Score;
result.Clear();
result.Add(currentPlayer);
}
}

return result.ToArray();
}
}
public class Test
{
public void RunTest()
{
Player[] allPlayers = new Player[7]
{
new Player("P1", 2), new Player("P2", 5), new Player("P3", 3),
new Player("P4", 9), new Player("P5", 1), new Player("P6", 6),
new Player("P7", 9)
};

Scorer scorer = new Scorer();
Player[] topPlayers = scorer.GetTopScores(allPlayers);

foreach (Player currentPlayer in topPlayers)
{
Console.WriteLine(string.Format("Player: {0}, Score: {1}", currentPlayer.PlayerID, currentPlayer.Score));
}
}
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
- Sort the list
- Let Highest be first element
- Iterate through list while (current element equals Highest), increment Count on each iteration


To be nitpicking as we all love it here ;), sorting the list will take more time than finding a maximum (even if you did O(n) integer sort), so

- Find a maximum with a linear pass over the array.
- Do a second pass over the array, picking out all elements that are equal to the maximum.

If there are hundreds of players, this would be a faster method in practice. You can even merge these two passes into one, by having a list of maximum values instead of tracking just one. If you find a new maximum value, clear the list and insert that new maximum into the list. If you find a value equal to a maximum, push it to the back of the list.

Share this post


Link to post
Share on other sites
Quote:
Original post by clb
Quote:
Original post by Antheus
- Sort the list
- Let Highest be first element
- Iterate through list while (current element equals Highest), increment Count on each iteration


To be nitpicking as we all love it here ;), sorting the list will take more time than finding a maximum (even if you did O(n) integer sort), so

- Find a maximum with a linear pass over the array.
- Do a second pass over the array, picking out all elements that are equal to the maximum.

If there are hundreds of players, this would be a faster method in practice. You can even merge these two passes into one, by having a list of maximum values instead of tracking just one. If you find a new maximum value, clear the list and insert that new maximum into the list. If you find a value equal to a maximum, push it to the back of the list.


Why go through the list twice if you can do it once?

Go through the list, set the first element as current, and set counter at one.

If the next element is lower then the current, go to the next.
If the next element is equal to the current, add 1 up to the counter.
If the next element is higher then the current, current gets value of the higher value and count is set to one.

In C++:
std::vector<int> array;

// fill array

int count = 1;
int current = array[0];
for (int i = 1; i < (int) array.size(); i++)
{
if (array[i] == current)
{
count++;
}
else if (array[i] > current)
{
current = array[i];
count = 1;
}
}

std::cout << count << "highscores of value " << current << '\n';

Share this post


Link to post
Share on other sites
Quote:
Original post by clb

To be nitpicking as we all love it here ;), sorting the list will take more time than finding a maximum (even if you did O(n) integer sort), so


How exactly does "picking out" work?

Put them in new list (allocation, insertion)? Store the indices (allocation, insertion, lookup)?

Why not use quickselect variation to get O(n) with no allocations?

Performance-wise, the selection problem is solved. Everything else is just a matter of implementation detail, so what we're talking here is constant factor optimization, the algorithms for O(n) however are known.

PS: Also completely forgot about std::partial_sort...

Share this post


Link to post
Share on other sites
Quote:
Original post by Decrius
Why go through the list twice if you can do it once?


Quote:
Original post by clb
You can even merge these two passes into one, by having a list of maximum values instead of tracking just one. If you find a new maximum value, clear the list and insert that new maximum into the list. If you find a value equal to a maximum, push it to the back of the list.


Quote:
Original post by Antheus
Put them in new list (allocation, insertion)? Store the indices (allocation, insertion, lookup)?

Why not use quickselect variation to get O(n) with no allocations?

Performance-wise, the selection problem is solved. Everything else is just a matter of implementation detail, so what we're talking here is constant factor optimization, the algorithms for O(n) however are known.


The output size is anything from one element to the whole list. I don't see how you can produce the output without allocating space for the output, unless you incorporate the processing of your output inside the algorithm to avoid storing the list at all. Also, performance-wise quickselect is slower than finding the maximum (in constant factors, which we game developers naturally are interested in).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this