## Top Five Test Scores

### July 3, 2018

We frequently base exercises on student assignments. Today we have something for the teachers:

A student’s final store is the average of the five best test scores the student achieved during the school term. Given a list of student name/score pairs, determine the final score for each student. You may assume each student has at least five scores.

Your task is to write a program to determine each student’s final score, as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

In Python, using a heapq for keeping the best 5 scores on the go. Should be more efficient than sorting the all results per student afterwards.

Also works for students with less than 5 scores (student3 example), although that might not be really fair :)

Here is solution that I believe is asymptotically optimal O(n

log(k)),log(n)) and output sorted by names if needed.with the usual hashing caveat. It uses R7RS Scheme, hash tables from

SRFI 69, and priority queues from SLIB. We could also replace the

hash table with a balanced-tree data structure to get guaranteed

O(n

@programmingpraxis: In Scheme, numbers should be compared with eqv?, not eq?.

Here’s a solution in C++11.

Output:

Probably my longest Perl ever here – we need to quickly implement an ordered queue to keep track of the top 5 scores for each candidate.

I think I prefer to sort by score descending – so we will have one sort here!

A Haskell version.