# 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.