Possible Test Scores
Walter Roberson, frequent contributor to the MATLAB newsgroup, posed the following question to me to use as the starter idea of a blog.
Q: Suppose there is a multiple-choice quiz, and for each question, one of the responses scores 0 points, one scores 3 points, one scores 5 points, one scores 8 points, and one scores 10 points. If the quiz has 4 questions, and assuming that each taker answers all of the questions, then which totals per taker are not possible? For example, it would not be possible to finish the quiz with a total score of 2.
If the quiz had 7 questions?
Can you generalize the code so that the number of questions can be varied by varying a single assignment?
Contents
Initialize Test Parameters
Instead of Walter's numbers, I am choosing four scores and seven test questions for this demonstration.
N = 7; Points = [0 3 5 8];
Walter's Solution
Walter also gave me an elegant solution to show. He places the point values into a cell array, and then replicates that cell by the number of test questions.
GridVals = repmat({Points},N,1);
Next Walter grids the Points in N-dimensions, taking advantage of comma-separated lists for function arguments.
[Grid{1:N}] = ndgrid(GridVals{:});
Spread out the cell array along the N+1-dimension and sum the values along that dimension to get all possible PointTotals.
PointTotals = sum(cat(N+1,Grid{:}),N+1);
Finally, bin the PointTotals and remove bins that don't contain zeros. These remaining bins correspond to scores that are impossible to attain.
PointHist = hist(PointTotals(:),max(Points)*N+1); ImpossibleScores = find(~PointHist)-1;
The correct answer is
ImpossibleScores
ImpossibleScores = 1 2 4 7 49 52 54 55
Loren's Solution
My first solution takes advantage of nchoosek to calculate all possible combinations. After summing each one, I look for the unique values, and then remove those from the list of all possible scores.
allvals = repmat(Points,1,N); C = nchoosek(allvals,N); scores = unique(sum(C,2)); nonScores1 = 1:(max(Points)*N); nonScores1(scores(2:end)) = [];
Loren's Modified Solution
nchoosek can be slow when the number of elements in each combination is large, and I have definitely run out of memory using nchoosek as well sometimes. To offset that, I modified my solution to select unique combinations when possible to reduce the extra computation time (and memory). I won't recompute the first two lines of the algorithm here.
allvals = repmat(Points,1,N); C = nchoosek(allvals,N);
Next, winnow out the duplicate rows before proceeding.
lCpre = length(C);
C = unique(C,'rows');
lCpost = length(C);
I reduced the number of cases from lCpre to lcPost, a substantial savings in this case.
[lCpre lCpost]
ans = 1184040 16384
Make scores unique as well.
scores = sum(C,2); scores = unique(scores);
Finally, get rid of the valid scores.
nonScores2 = 1:(max(Points)*N); nonScores2(scores(2:end)) = [];
Bobby's Solution
Bobby Cheng came up with a very different solution which works only if the minimum score is zero. Otherwise, the algorithm would need to be modified.
f = @(a)unique(bsxfun(@plus,a(:),Points)); allPossibleScores = Points; % with only one question for i = 2:N allPossibleScores = f(allPossibleScores); end nonScores3 = setdiff(N*min(Points):N*max(Points),allPossibleScores);
Lucio's First Solution
Lucio Cetto came along next and contributed two solutions. The first one is similar to Bobby's, but Lucio propogates logical values instead of doubles (with integer values).
Initialize the outputs so the possible test scores are set to true for the initial point values for the first question.
a = false(max(Points),1); a(nonzeros(Points)) = true;
Iterate over the number of questions remaining, and augment the score array.
for i = 1:N-1 a(bsxfun(@plus,find(a),Points)) = true; end
The locations of the false values in a are the test scores that no test achieves.
nonScores4 = find(~a)';
Lucio's Second Solution
I will leave this one as an exercise for you to figure out. It is very dense, but works quite well.
maxscorep1 = N*max(Points)+1; A = toeplitz(sparse(1,1,1,1,maxscorep1),sparse(1,Points+1,1,1,maxscorep1)); A = A^N; nonScores5 = find(A(1,:)==0)-1;
Compare Answers
Let's now compare all the methods to be sure they get the same answer.
allequal = ... isequal(ImpossibleScores, nonScores1, nonScores2, ... nonScores3, nonScores4, nonScores5)
allequal = 1
Other Methods?
I didn't time the various methods, but trust me, the ones I contributed are the slowest and the most memory-intensive. Walter's is fully vectorized as well as mine, but can be a bit intensive in memory (but still nothing like mine, as far as I can tell!). Bobby's and Lucio's are the most efficient memory-wise, since they iterate over test questions, and toss out impossible combinations as they go. Do you have other techniques to share? Please do so here.
- Category:
- Efficiency,
- Memory,
- New Feature,
- Robustness
Comments
To leave a comment, please click here to sign in to your MathWorks Account or create a new one.