2

I am creating a somewhat simple game, and I need to keep track of what players have what score. 25 people will be playing this game at one time, these players will be put into an array:

public static int[] allPlayers = new int[25];

Depending on a correct answer, the current player will earn 100 points, let's say. So, if player 1 were up, the code would be something similar to the following:

allPlayers[0] += 100;

If player 3 were up, the code on a correct answer would be:

allPlayers[2] += 100;

At the end of the game, I want to determine which player has the accumulated the most amount of points. Please note that I cannot simply sort this array because I need the order of the array to remain intact. If the order is not left intact, I will not be able to tell which player had which points to his/her name.

I'm interested to hear what you all have to say and I look forward to your responses.

Thank you very much,

Evan

Improve this question

8 Answers 8

Reset to default
5

No need to sort, just iterate through the array, keeping track of the largest value seen so far and the index of that value.

  var largest = -1;
  var player = -1;
  for (var i = 0; i < allPlayers.Length; ++i)
  {
       if (allPlayers[i] > largest)
       {
           player = i;
           largest = allPlayers[i];
       }
  }

  Console.WriteLine( "Player {0} wins, with score {1}", player, largest );

Handling ties is left as an exercise.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I really like this approach! Thank you for this.
How can I do the same for n largest elements without sorting?
3

Using Linq as an alternative if you wanted a ranking of possibly more than one player (a simple loop with keeping the index of the winning player is much more effective for the base case):

var player = allPlayers.Select((x, i) => new { Score = x, Player = i })
                       .OrderByDescending(x => x.Score)
                       .First();

Console.WriteLine("Player {0} wins with a score of {1}", player.Player, player.Score);
Improve this answer

5 Comments

Is this sorting the array in any way as OrderByDescending suggests?
@Evan: No the array itself remains unchanged, the ordering is done on a separate enumeration
I know that I am being an absolute pain, and I have done some reading on the matter but I would be so grateful if you, or perhaps someone else who sees this comment could explain exactly what purpose the lambda operator is in this scenario? I would love to learn how to use this guy!
@Evan: You can read it as "goes to" - its basically an anonymous function that takes the input on the left and maps it to the output on the right. Also see msdn.microsoft.com/en-us/library/bb397687.aspx
a lamba "function" is (in this specific instance) a shorthand delegate.
3

I'd like to be a LINQ purist and say that if you are using OrderByDescending, you're doing an O(NlogN) sort. Since max is an O(N) algorithm, we should be able to do better with LINQ. Here is my O(N) proposal for LINQ:

  var player=allPlayers.Select((x, i) => new {Score=x, Player=i})
    .Aggregate((self, next) => self.Score>=next.Score ? self : next);

  Console.WriteLine("Player {0} wins with a score of {1}", player.Player, player.Score);
Improve this answer

Comments

1

Use 

int max = maxplayers.Max()//linq extension method of [] int

see this post

Improve this answer

Comments

0

If you are unable to sort or keep a parallel data structure that can do the sorting or keep a a reference to the largest value, you are going to have an O(n) algorithm.

Easiest way would be to keep a reference to the highest value inserted into the array.

Improve this answer

Comments

0

Using Linq:

int max = allPlayers
     .Select((x, i) = > new { Player = i, Score = x })
     .OrderByDescending(x => x.Score)
     .First();

Without Linq:

int score;
int player;

for(var i = 0; i < allPlayers.Length; i++)
{
    if(allPlayers[i] > score)
    {
        score = allPlayers[i];
        player = i;
    }
}
Improve this answer

Comments

0

You can keep a tracking wich player has the max value in all the process, in each increase you can review if the new value is bigger than the old value, so in this way you can to know wich player has the max value in any moment at the game.

private int maxPlayer = 0;
private int value = 0;

public void setIncrement(int player, int amount)
{
    allPlayer[player] += amount; 
    if(allPlayer[player] > value) 
    { 
        maxPlayer = player; 
        value =  allPlayer[player];
    }
}

public int getMaxPlayer()
{
return maxPlayer;
}
Improve this answer

Comments

-1

Just iterate throught it once as others have suggested. That's unavoidable,

UNLESS

You wrap your players array into an array and encapsulate the way to set player score. Then you can make the comparison when adding stuff to your list.

Improve this answer

Comments