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.
Programming Praxis 
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 :)
import heapq scores = [ ('student1', 1), ('student1', 2), ('student1', 3), ('student1', 4), ('student1', 5), ('student1', 6), ('student2', 1), ('student2', 3), ('student2', 3), ('student2', 3), ('student2', 3), ('student2', 4), ('student3', 3), ('student3', 4) ] studentheaps = {} for student, score in scores: if student not in studentheaps: studentheaps[student] = [] if len(studentheaps[student]) < 5: heapq.heappush(studentheaps[student], score) else: heapq.heappushpop(studentheaps[student], score) for student in studentheaps: l = studentheaps[student] print(student, sum(l) / float(len(l))) # output # student1 4.0 # student2 3.2 # student3 3.5Here is solution that I believe is asymptotically optimal O(nlog(k)),
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(nlog(n)) and output sorted by names if needed.
(import (scheme base) (scheme write) (srfi 69) (slib priority-queue)) (define scores '((Bob 78) (Sue 75) (Bill 83) (Jill 88) (Joe 58) (Bob 93) (Sue 84) (Bill 81) (Jill 91) (Joe 75) (Bob 62) (Sue 93) (Bill 91) (Jill 99) (Joe 62) (Bob 92) (Sue 88) (Bill 88) (Jill 76) (Joe 61) (Bob 87) (Sue 92) (Bill 87) (Jill 85) (Joe 69) (Bob 85) (Sue 87) (Bill 93) (Jill 96) (Joe 65) (Bob 72) (Sue 88) (Bill 85) (Jill 83) (Joe 71))) (define (heap-extract-max-k heap k) (let loop ((i 0) (top-i '())) (if (or (>= i k) (zero? (heap-length heap))) top-i (loop (+ i 1) (cons (heap-extract-max! heap) top-i))))) (define (top-k-by-name k name-item-duos name=? name-hasher item>?) (let ((ht (make-hash-table name=? name-hasher))) (for-each (lambda (name-item) (hash-table-update!/default ht (car name-item) (lambda (heap) (heap-insert! heap (cadr name-item)) (when (> (heap-length heap) k) (heap-extract-max! heap)) heap) (make-heap item>?))) name-item-duos) (hash-table-fold ht (lambda (name heap ans) (cons (list name (heap-extract-max-k heap k)) ans)) '()))) (define (list-mean nums) (let ((n (length nums))) (and (positive? n) (/ (apply + nums) n)))) (display (map (lambda (duo) (list (car duo) (inexact (list-mean (cadr duo))))) (top-k-by-name 5 scores symbol=? hash >))) (newline)Klong version l::[["Bob" 78] ["Sue" 75] ["Bill" 83] ["Jill" 88] ["Joe" 58] ["Bob" 93] ["Sue" 84] ["Bill" 81] ["Jill" 91] ["Joe" 75] ["Bob" 62] ["Sue" 93] ["Bill" 91] ["Jill" 99] ["Joe" 62] ["Bob" 92] ["Sue" 88] ["Bill" 88] ["Jill" 76] ["Joe" 61] ["Bob" 87] ["Sue" 92] ["Bill" 87] ["Jill" 85] ["Joe" 69] ["Bob" 85] ["Sue" 87] ["Bill" 93] ["Jill" 96] ["Joe" 65] ["Bob" 72] ["Sue" 88] ["Bill" 85] ["Jill" 83] ["Joe" 71]] build::{:[:_d?x; d,x,y; {d,x,,((d?x),,y)}(x; y)]} d:::{}; {build(x@0; x@1)}'l; "Building person-indexed dictionary" gs::{[s l]; s::0; l::x; {s::s+l@x}'!5; s%5} {.p((x@0)," = ",gs(l@>l::x@1))}'d;"end" steve@steve-VirtualBox:~/klong/lib$ rlwrap ../kg -l scores.kg [Bill = 88.8] [Sue = 89.6] [Bob = 87.0] [Jill = 91.8] [Joe = 68.4] Klong 20180213Mumps version vista@steve-VirtualBox:~/EHR/r$ cat scores.m scores(list) ; get average of top 5 scores for each student ; n arr,glo,i,j,n,s,t ; f i=1:1:$l(list,"|") d . s n=$p(list,"|",i),s=$p(n,",",2),n=$p(n,",") . s arr(n,-s,$i(arr(n,-s)))="" ; Allow for duplicate scores ; w !,"Average of top 5 scores per student" s n="" f s n=$o(arr(n)) q:n="" d . s glo="arr("""_n_""")",(i,t)=0 . f s glo=$q(@glo) q:glo=""!($qs(glo,1)'=n) i $ql(glo)=3 s s=$qs(glo,2),t=t+s q:$i(i)=5 ; Allow for duplicate scores . w !,n,": ",-t/5.0 q vista@steve-VirtualBox:~/EHR/r$ gtm GTM>s list="Bob,78|Sue,75|Bill,83|Jill,88|Joe,58|Bob,93|Sue,84|Bill,81|Jill,91|Joe,75|Bob,62|Sue,93|Bill,91|Jill,99|Joe,62|Bob,92|Sue,88|Bill,88|Jill,76|Joe,61|Bob,87|Sue,92|Bill,87|Jill,85|Joe,69|Bob,85|Sue,87|Bill,93|Jill,96|Joe,65|Bob,72|Sue,88|Bill,85|Jill,83|Joe,71" GTM>d ^scores(list) Average of top 5 scores per student Bill: 88.8 Bob: 87 Jill: 91.8 Joe: 68.4 Sue: 89.6 GTM>@programmingpraxis: In Scheme, numbers should be compared with eqv?, not eq?.
Here’s a solution in C++11.
#include <algorithm> #include <cstdlib> #include <iomanip> #include <ios> #include <iostream> #include <numeric> #include <string> #include <unordered_map> #include <utility> #include <vector> using namespace std; void average_top_scores( const unsigned num_top_scores, const vector<pair<string,int>>& data, unordered_map<string,float>* averages) { unordered_map<string,vector<int>> top_scores_lookup; for (pair<string,int> item : data) { string name = item.first; int score = item.second; vector<int>& scores = top_scores_lookup[name]; if (scores.size() == num_top_scores && scores[0] < score) { pop_heap(scores.begin(), scores.end(), greater<int>()); scores.pop_back(); } if (scores.size() < num_top_scores) { scores.push_back(score); push_heap(scores.begin(), scores.end(), greater<int>()); } } for (pair<string,vector<int>> item : top_scores_lookup) { vector<int>& scores = item.second; float average = accumulate(scores.begin(), scores.end(), 0.0) / scores.size(); (*averages)[item.first] = average; } } int main(void) { vector<pair<string,int>> data = { {"Bob", 78}, {"Sue", 75}, {"Bill", 83}, {"Jill", 88}, {"Joe", 58}, {"Bob", 93}, {"Sue", 84}, {"Bill", 81}, {"Jill", 91}, {"Joe", 75}, {"Bob", 62}, {"Sue", 93}, {"Bill", 91}, {"Jill", 99}, {"Joe", 62}, {"Bob", 92}, {"Sue", 88}, {"Bill", 88}, {"Jill", 76}, {"Joe", 61}, {"Bob", 87}, {"Sue", 92}, {"Bill", 87}, {"Jill", 85}, {"Joe", 69}, {"Bob", 85}, {"Sue", 87}, {"Bill", 93}, {"Jill", 96}, {"Joe", 65}, {"Bob", 72}, {"Sue", 88}, {"Bill", 85}, {"Jill", 83}, {"Joe", 71} }; unordered_map<string,float> averages; average_top_scores(5, data, &averages); for (pair<string,float> item : averages) { cout << item.first << ": " << fixed << setprecision(1) << item.second << endl; } return EXIT_SUCCESS; }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.
use strict; use warnings; my @input = ( ['Bob', 78], ['Sue', 75], ['Bill', 83], ['Jill', 88], ['Joe', 58], ['Bob', 93], ['Sue', 84], ['Bill', 81], ['Jill', 91], ['Joe', 75], ['Bob', 62], ['Sue', 93], ['Bill', 91], ['Jill', 99], ['Joe', 62], ['Bob', 92], ['Sue', 88], ['Bill', 88], ['Jill', 76], ['Joe', 61], ['Bob', 87], ['Sue', 92], ['Bill', 87], ['Jill', 85], ['Joe', 69], ['Bob', 85], ['Sue', 87], ['Bill', 93], ['Jill', 96], ['Joe', 65], ['Bob', 72], ['Sue', 88], ['Bill', 85], ['Jill', 83], ['Joe', 71] ); my ($N,$t) = (5 - 1,0); my %scores; foreach( @input ) { my($name,$v) = @{$_}; foreach(0..$N) { next if $_ < @{$scores{$name}||[]} && $v < $scores{$name}[$_]; splice @{$scores{$name}},$_,0,$v; ## Put in correct place splice @{$scores{$name}},$N+1; ## Trim if longer than 5 last; } } foreach my $name ( sort keys %scores ) { $t = 0; $t += $_ foreach @{$scores{$name}}; printf "%7.3f\t%s\n", $t/@{$scores{$name}}, $name; }I think I prefer to sort by score descending – so we will have one sort here!
foreach my $name ( sort keys %scores ) { $t = 0; $t += $_ foreach @{$scores{$name}}; $scores{$name} = $t/@{$scores{$name}}; } foreach my $name ( reverse sort { $scores{$a} <=> $scores{$b} } keys %scores ) { printf "%7.3f\t%s\n", $scores{$name}, $name; }A Haskell version.
import Control.Foldl (fold, mean) import Data.Function (on) import Data.List (groupBy, sortBy) import Data.Monoid ((<>)) import Data.Ord (comparing) import Text.Printf type Score = (String, Double) scores :: [Score] scores = [ ("Bob", 78), ("Sue", 75), ("Bill", 83), ("Jill", 88), ("Joe", 58) , ("Bob", 93), ("Sue", 84), ("Bill", 81), ("Jill", 91), ("Joe", 75) , ("Bob", 62), ("Sue", 93), ("Bill", 91), ("Jill", 99), ("Joe", 62) , ("Bob", 92), ("Sue", 88), ("Bill", 88), ("Jill", 76), ("Joe", 61) , ("Bob", 87), ("Sue", 92), ("Bill", 87), ("Jill", 85), ("Joe", 69) , ("Bob", 85), ("Sue", 87), ("Bill", 93), ("Jill", 96), ("Joe", 65) , ("Bob", 72), ("Sue", 88), ("Bill", 85), ("Jill", 83), ("Joe", 71)] -- Given a list of scores for students, return the final score for each student, -- based on their top n scores. We assume n > 0. finalScores :: Int -> [Score] -> [Score] finalScores n = map (finalScore . take n) . groupBy ((==) `on` fst) . sortBy cmp where cmp ts1 ts2 = comparing fst ts1 ts2 <> comparing snd ts2 ts1 -- Given a non-empty list of scores for one student, return their final score. finalScore :: [Score] -> Score finalScore tss@((name, _) : _) = (name, fold mean $ map snd tss) main :: IO () main = mapM_ (uncurry $ printf "%-4s %5.1f\n") $ finalScores 5 scores