Monday, December 22, 2014

ContestScore

Problem:

TopCoder Problem Statement - ContestScore

Overview:

Rank contestants based on scores given by a panel of judges.

Java Source:
001: import java.util.ArrayList;
002: import java.util.Collections;
003: import java.util.Comparator;
004: import java.util.List;
005: 
006: public class ContestScore {
007: 
008:     /*
009:     * A class to hold the data related to a single contestant.
010:     */
011:     private class Contestant {
012: 
013:         final String name;
014:         final int[] scores;
015:         final int[] ranks;
016: 
017:         Contestant(String data) {
018: 
019:             // Get the contestant's name
020:             String[] elements = data.split(" ");
021:             this.name = elements[0];
022: 
023:             // Copy the remainder of data into scores.
024:             scores = new int[elements.length - 1];
025: 
026:             for (int i = 1; i < elements.length; i++) {
027: 
028:     /*
029:     * For now, we'll remove the decimal place from the score.
030:     * This won't change the rankings at all.  We'll put the
031:     * decimal back in when displaying the results.
032:     */
033:                 int score = Integer.parseInt(elements[i].replace(".", ""));
034:                 scores[i - 1] = score;
035:             }
036: 
037:             // Ranks is empty for now.
038:             this.ranks = new int[scores.length];
039: 
040:         }
041: 
042:         // Returns the sum of all elements in rank
043:         int getTotalRank() {
044:             int totalRank = 0;
045:             for (int i = 0; i < ranks.length; i++) {
046:                 totalRank += ranks[i];
047:             }
048:             return totalRank;
049:         }
050: 
051:         // Returns the sum of all elements in score
052:         int getTotalScore() {
053:             int totalScore = 0;
054:             for (int i = 0; i < scores.length; i++) {
055:                 totalScore += scores[i];
056:             }
057:             return totalScore;
058:         }
059: 
060:         public String toString() {
061: 
062:             int totalRank = getTotalRank();
063:             int totalScore = getTotalScore();
064: 
065:    /*
066:    * score1 is the integer portion of the score.
067:    * score2 will be the decimal portion.
068:    */
069:             int score1 = totalScore / 10;
070:             int score2 = totalScore % 10;
071: 
072:             StringBuilder sb = new StringBuilder();
073:             sb.append(name);
074:             sb.append(" ");
075:             sb.append(totalRank);
076:             sb.append(" ");
077:             sb.append(score1);
078:             sb.append(".");
079:             sb.append(score2);
080:             return sb.toString();
081:         }
082:     }
083: 
084:     /*
085:     * Compares contestants based on the given judge.
086:     */
087:     private class ContestantComparatorByJudge implements
088:             Comparator {
089: 
090:         private final int judge;
091: 
092:         ContestantComparatorByJudge(int judge) {
093:             this.judge = judge;
094:         }
095: 
096:         @Override
097:         public int compare(Contestant o1, Contestant o2) {
098: 
099:             // Sort scores highest to lowest.
100:             return -1 * Integer.compare(o1.scores[judge], o2.scores[judge]);
101:         }
102:     }
103: 
104:     /*
105:     * Compares contestants based on their ranks.  All the ranks should be
106:     * computed prior to calling.
107:     */
108:     private class ContestantComparatorOverall implements
109:             Comparator {
110: 
111:         @Override
112:         public int compare(Contestant o1, Contestant o2) {
113: 
114:             // Compare rank first
115:             if (o1.getTotalRank() != o2.getTotalRank()) {
116:                 return Integer.compare(o1.getTotalRank(), o2.getTotalRank());
117:             }
118: 
119:             // If there's a tie, compare by score, highest to lowest.
120:             if (o1.getTotalScore() != o2.getTotalScore()) {
121: 
122:                 // Multiply by -1, since we want the higher score first.
123:                 return -1 * Integer.compare(o1.getTotalScore(),
124:                         o2.getTotalScore());
125:             }
126: 
127:             // If still tied, compare by name.
128:             return o1.name.compareTo(o2.name);
129: 
130:         }
131:     }
132: 
133: 
134:     public String[] sortResults(String[] data) {
135: 
136:         if (data == null) {
137:             return null;
138:         }
139: 
140:         if (data.length == 0) {
141:             return new String[0];
142:         }
143: 
144:         List contestants = new ArrayList<>();
145: 
146:         for (int i = 0; i < data.length; i++) {
147:             contestants.add(new Contestant(data[i]));
148:         }
149: 
150:         int numJudges = data[0].split(" ").length - 1;
151: 
152:         for (int i = 0; i < numJudges; i++) {
153: 
154:             // Create a new comparator to examine current judge's scores.
155:             ContestantComparatorByJudge judgeComparator =
156:                     new ContestantComparatorByJudge(i);
157: 
158:             // Sort the contestants using the new comparator.
159:             Collections.sort(contestants, judgeComparator);
160: 
161:    /*
162:    * Assign ranks to each contestant.  Need to keep track of previous
163:    * rank and score in the event that there are ties.
164:    */
165:             int rank = 0;
166:             int lastScore = -1;
167:             int lastRank = 1;
168: 
169:             for (Contestant c : contestants) {
170:                 rank++;
171:                 if (c.scores[i] == lastScore) {
172:                     c.ranks[i] = lastRank;
173:                 } else {
174:                     c.ranks[i] = rank;
175:                     lastScore = c.scores[i];
176:                     lastRank = rank;
177:                 }
178:             }
179:         }
180: 
181:   /*
182:   * Once all the ranks are assigned.  Sort the contestants using
183:   * the ContestantComparatorOverall comparator.
184:   */
185:         ContestantComparatorOverall overallComparator =
186:                 new ContestantComparatorOverall();
187: 
188:         Collections.sort(contestants, overallComparator);
189: 
190:         // Build the result String[]
191:         String[] results = new String[data.length];
192: 
193:         int i = 0;
194:         for (Contestant c : contestants) {
195:             results[i++] = c.toString();
196:         }
197: 
198:         return results;
199: 
200:     }
201: }
Notes:

To solve this, we first need to assign ranks based on each judge's score, and then sort the contestants based on their rankings. To make things easy, a Contestant class is used to store all the data related to a single contestant, and two Comparator classes help out with the sorting.

The constructor for the Contestant class handles reading in a string and parsing out the name and the scores. The name is the first element, and the remainder of the String is chopped up into ints and copied to the scores array. Note that at this point I strip out the decimal place. I'll add that back in when displaying the results. But for now, it'll be easier to effectively just multiply all scores by 10. Finally, the constructor initializes an array to hold the rankings, but this cannot be filled in yet.

The sortResults() method begins by first checking to ensure that the data parameter is not empty, and then creates a List to store the Contestants. Then, for each judge, we'll create a new ContestantComparatorByJudge comparator to help sort the contestants by the current judge. The ContestantComparatorByJudge class takes a int in it's constructor, and uses that to compare the scores in the Contestan's score array. Note that the compare() method multiplies the result of Integer.compare() by -1 because we want the contestants in order from highest to lowest. Once the contestants are sorted by a given judge's score, we can assign a rank to each contestant for that judge. Here, we need to be careful in case there is a tie in the score.

Once all the ranks are assigned, a different comparator, ContestantComparatorOverall, is used to sort the contestants one last time. ContestantComparatorOverall first compares by the sum of all ranks (lowest to highest), then if there is a tie, by total score (highest to lowest). If there is still a tie, it compares their names.

After the contestans are sorted in their final order, just loop through them, using their toString() method to build the String[] result.

All in all, this was not too hard for a 1000 point problem. Just a few key points:

  1. If possible, convert decimals to integers to keep things easy.
  2. Use Collections.sort to do all the sorting. Just implement the custom comparators.
  3. Be careful with how you handle ties.

If you can handle that, there's really not much to this problem.

No comments:

Post a Comment