{"id":164,"date":"2008-12-02T13:32:28","date_gmt":"2008-12-02T13:32:28","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/2008\/12\/02\/possible-test-scores\/"},"modified":"2018-01-08T15:30:11","modified_gmt":"2018-01-08T20:30:11","slug":"possible-test-scores","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2008\/12\/02\/possible-test-scores\/","title":{"rendered":"Possible Test Scores"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <introduction>\r\n      <p>Walter Roberson, frequent contributor to the <a>MATLAB newsgroup<\/a>, posed the following question to me to use as the starter idea of a blog.\r\n      <\/p>\r\n      <p><i>Q: Suppose there is a multiple-choice quiz, and for each question, one of the responses scores 0 points, one scores 3 points,\r\n            one scores 5 points, one scores 8 points, and one scores 10 points. If the quiz has 4 questions, and assuming that each taker\r\n            answers all of the questions, then which totals per taker are <b>not<\/b> possible? For example, it would not be possible to finish the quiz with a total score of 2.<\/i><\/p>\r\n      <p><i>If the quiz had 7 questions?<\/i><\/p>\r\n      <p><i>Can you generalize the code so that the number of questions can be varied by varying a single assignment?<\/i><\/p>\r\n   <\/introduction>\r\n   <h3>Contents<\/h3>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"#1\">Initialize Test Parameters<\/a><\/li>\r\n         <li><a href=\"#2\">Walter's Solution<\/a><\/li>\r\n         <li><a href=\"#7\">Loren's Solution<\/a><\/li>\r\n         <li><a href=\"#8\">Loren's Modified Solution<\/a><\/li>\r\n         <li><a href=\"#13\">Bobby's Solution<\/a><\/li>\r\n         <li><a href=\"#14\">Lucio's First Solution<\/a><\/li>\r\n         <li><a href=\"#18\">Lucio's Second Solution<\/a><\/li>\r\n         <li><a href=\"#19\">Compare Answers<\/a><\/li>\r\n         <li><a href=\"#20\">Other Methods?<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>Initialize Test Parameters<a name=\"1\"><\/a><\/h3>\r\n   <p>Instead of Walter's numbers, I am choosing <a href=\"http:\/\/www.loc.gov\/exhibits\/gettysburg-address\/\">four scores and seven<\/a> test questions for this demonstration.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">N = 7;\r\nPoints = [0 3 5 8];<\/pre><h3>Walter's Solution<a name=\"2\"><\/a><\/h3>\r\n   <p>Walter also gave me an elegant solution to show.  He places the point values into a cell array, and then replicates that cell\r\n      by the number of test questions.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">GridVals = repmat({Points},N,1);<\/pre><p>Next Walter grids the <tt>Points<\/tt> in <tt>N<\/tt>-dimensions, taking advantage of comma-separated lists for function arguments.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">[Grid{1:N}] = ndgrid(GridVals{:});<\/pre><p>Spread out the cell array along the <tt>N<\/tt>+1-dimension and <a href=\"https:\/\/www.mathworks.com\/help\/releases\/R2008b\/techdoc\/ref\/sum.html\"><tt>sum<\/tt><\/a> the values along that dimension to get all possible <tt>PointTotals<\/tt>.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">PointTotals = sum(cat(N+1,Grid{:}),N+1);<\/pre><p>Finally, bin the <tt>PointTotals<\/tt> and remove bins that don't contain zeros. These remaining bins correspond to scores that are impossible to attain.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">PointHist = hist(PointTotals(:),max(Points)*N+1);\r\nImpossibleScores = find(~PointHist)-1;<\/pre><p>The correct answer is<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">ImpossibleScores<\/pre><pre style=\"font-style:oblique\">ImpossibleScores =\r\n     1     2     4     7    49    52    54    55\r\n<\/pre><h3>Loren's Solution<a name=\"7\"><\/a><\/h3>\r\n   <p>My first solution takes advantage of <a href=\"https:\/\/www.mathworks.com\/help\/releases\/R2008b\/techdoc\/ref\/nchoosek.html\"><tt>nchoosek<\/tt><\/a> to calculate all possible combinations.  After summing each one, I look for the unique values, and then remove those from\r\n      the list of all possible scores.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">allvals = repmat(Points,1,N);\r\nC = nchoosek(allvals,N);\r\nscores = unique(sum(C,2));\r\nnonScores1 = 1:(max(Points)*N);\r\nnonScores1(scores(2:end)) = [];<\/pre><h3>Loren's Modified Solution<a name=\"8\"><\/a><\/h3>\r\n   <p><tt>nchoosek<\/tt> can be slow when the number of elements in each combination is large, and I have definitely run out of memory using <tt>nchoosek<\/tt> as well sometimes.  To offset that, I modified my solution to select unique combinations when possible to reduce the extra\r\n      computation time (and memory).  I won't recompute the first two lines of the algorithm here.\r\n   <\/p><pre> allvals = repmat(Points,1,N);\r\n C = nchoosek(allvals,N);<\/pre><p>Next, winnow out the duplicate rows before proceeding.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lCpre = length(C);\r\nC = unique(C,<span style=\"color: #A020F0\">'rows'<\/span>);\r\nlCpost = length(C);<\/pre><p>I reduced the number of cases from <tt>lCpre<\/tt> to <tt>lcPost<\/tt>, a substantial savings in this case.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">[lCpre lCpost]<\/pre><pre style=\"font-style:oblique\">ans =\r\n     1184040       16384\r\n<\/pre><p>Make scores unique as well.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">scores = sum(C,2);\r\nscores = unique(scores);<\/pre><p>Finally, get rid of the valid scores.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">nonScores2 = 1:(max(Points)*N);\r\nnonScores2(scores(2:end)) = [];<\/pre><h3>Bobby's Solution<a name=\"13\"><\/a><\/h3>\r\n   <p>Bobby Cheng came up with a very different solution which works only if the minimum score is zero. Otherwise, the algorithm would need\r\n      to be modified.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">f = @(a)unique(bsxfun(@plus,a(:),Points));\r\nallPossibleScores = Points; <span style=\"color: #228B22\">% with only one question<\/span>\r\n<span style=\"color: #0000FF\">for<\/span> i = 2:N\r\n    allPossibleScores = f(allPossibleScores);\r\n<span style=\"color: #0000FF\">end<\/span>\r\nnonScores3 = setdiff(N*min(Points):N*max(Points),allPossibleScores);<\/pre><h3>Lucio's First Solution<a name=\"14\"><\/a><\/h3>\r\n   <p><a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/authors\/1858\">Lucio Cetto<\/a> came along next and contributed two solutions.  The first one is similar to Bobby's, but Lucio propogates logical values\r\n      instead of doubles (with integer values).\r\n   <\/p>\r\n   <p>Initialize the outputs so the possible test scores are set to <tt>true<\/tt> for the initial point values for the first question.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">a = false(max(Points),1);\r\na(nonzeros(Points)) = true;<\/pre><p>Iterate over the number of questions remaining, and augment the score array.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\"><span style=\"color: #0000FF\">for<\/span> i = 1:N-1\r\n    a(bsxfun(@plus,find(a),Points)) = true;\r\n<span style=\"color: #0000FF\">end<\/span><\/pre><p>The locations of the <tt>false<\/tt> values in <tt>a<\/tt> are the test scores that no test achieves.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">nonScores4 = find(~a)';<\/pre><h3>Lucio's Second Solution<a name=\"18\"><\/a><\/h3>\r\n   <p>I will leave this one as an exercise for you to figure out.  It is very dense, but works quite well.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">maxscorep1 = N*max(Points)+1;\r\nA = toeplitz(sparse(1,1,1,1,maxscorep1),sparse(1,Points+1,1,1,maxscorep1));\r\nA = A^N;\r\nnonScores5 = find(A(1,:)==0)-1;<\/pre><h3>Compare Answers<a name=\"19\"><\/a><\/h3>\r\n   <p>Let's now compare all the methods to be sure they get the same answer.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">allequal = <span style=\"color: #0000FF\">...<\/span>\r\n    isequal(ImpossibleScores, nonScores1, nonScores2, <span style=\"color: #0000FF\">...<\/span>\r\n    nonScores3, nonScores4, nonScores5)<\/pre><pre style=\"font-style:oblique\">allequal =\r\n     1\r\n<\/pre><h3>Other Methods?<a name=\"20\"><\/a><\/h3>\r\n   <p>I didn't time the various methods, but trust me, the ones I contributed are the slowest and the most memory-intensive.  Walter's\r\n      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!).\r\n      Bobby's and Lucio's are the most efficient memory-wise, since they iterate over test questions, and toss out impossible combinations\r\n      as they go.  Do you have other techniques to share? Please do so <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=164#respond\">here<\/a>.\r\n   <\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_b3f8c5627d0449549975dfa18eef2c1b() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='b3f8c5627d0449549975dfa18eef2c1b ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' b3f8c5627d0449549975dfa18eef2c1b';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        author = 'Loren Shure';\r\n        copyright = 'Copyright 2008 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add author and copyright lines at the bottom if specified.\r\n        if ((author.length > 0) || (copyright.length > 0)) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (author.length > 0) {\r\n                d.writeln('% _' + author + '_');\r\n            }\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n      \r\n      d.title = title + ' (MATLAB code)';\r\n      d.close();\r\n      }   \r\n      \r\n-->\r\n<\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_b3f8c5627d0449549975dfa18eef2c1b()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n            the MATLAB code \r\n            <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.7<br><\/p>\r\n<\/div>\r\n<!--\r\nb3f8c5627d0449549975dfa18eef2c1b ##### SOURCE BEGIN #####\r\n%% Possible Test Scores\r\n% <https:\/\/www.mathworks.com\/cgi-bin\/texis\/webinator\/search\/?db=MSS&prox=page&rorder=750&rprox=750&rdfreq=500&rwfreq=500&rlead=250&sufs=0&order=r&is_summary_on=1&ResultCount=10&query=%22walter+roberson%22&submitButtonName=Search Walter Roberson>,\r\n% frequent contributor to the <http:\/\/ MATLAB newsgroup>, \r\n% posed the following question to me to use as the starter idea of a blog.\r\n%\r\n% _Q: Suppose there is a multiple-choice quiz, and for each question, one of\r\n% the responses scores 0 points, one scores 3 points, one scores 5 points,\r\n% one scores 8 points, and one scores 10 points. If the quiz has 4\r\n% questions, and assuming that each taker answers all of the questions,\r\n% then which totals per taker are *not* possible? For example, it would not\r\n% be possible to finish the quiz with a total score of 2._\r\n% \r\n% _If the quiz had 7 questions?_\r\n% \r\n% _Can you generalize the code so that the number of\r\n% questions can be varied by varying a single assignment?_\r\n%% Initialize Test Parameters\r\n% Instead of Walter's numbers, I am choosing \r\n% <http:\/\/www.loc.gov\/exhibits\/gadd\/images\/Gettysburg-2.jpg four scores and seven>\r\n% test questions for this demonstration.\r\nN = 7;\r\nPoints = [0 3 5 8];\r\n%% Walter's Solution\r\n% Walter also gave me an elegant solution to show.  He places the point\r\n% values into a cell array, and then replicates that cell by the number of \r\n% test questions.\r\nGridVals = repmat({Points},N,1);\r\n%%\r\n% Next Walter grids the |Points| in |N|-dimensions, taking advantage of\r\n% comma-separated lists for function arguments.\r\n[Grid{1:N}] = ndgrid(GridVals{:});\r\n%%\r\n% Spread out the cell array along the |N|+1-dimension and \r\n% <https:\/\/www.mathworks.com\/help\/releases\/R2008b\/techdoc\/ref\/sum.html |sum|>\r\n% the values along that dimension to get all possible |PointTotals|.\r\nPointTotals = sum(cat(N+1,Grid{:}),N+1);\r\n%% \r\n% Finally, bin the |PointTotals| and remove bins that don't contain zeros.\r\n% These remaining bins correspond to scores that are impossible to attain.\r\nPointHist = hist(PointTotals(:),max(Points)*N+1);\r\nImpossibleScores = find(~PointHist)-1;\r\n%%\r\n% The correct answer is\r\nImpossibleScores\r\n%% Loren's Solution\r\n% My first solution takes advantage of \r\n% <https:\/\/www.mathworks.com\/help\/releases\/R2008b\/techdoc\/ref\/nchoosek.html |nchoosek|>\r\n% to calculate all possible combinations.  After summing each one, I look\r\n% for the unique values, and then remove those from the list of all\r\n% possible scores.\r\nallvals = repmat(Points,1,N);\r\nC = nchoosek(allvals,N);\r\nscores = unique(sum(C,2));\r\nnonScores1 = 1:(max(Points)*N);\r\nnonScores1(scores(2:end)) = [];\r\n%% Loren's Modified Solution\r\n% |nchoosek| can be slow when the number of elements in each combination is\r\n% large, and I have definitely run out of memory using |nchoosek| as well\r\n% sometimes.  To offset that, I modified my solution to select unique\r\n% combinations when possible to reduce the extra computation time (and\r\n% memory).  I won't recompute the first two lines of the algorithm here.\r\n%\r\n%   allvals = repmat(Points,1,N);\r\n%   C = nchoosek(allvals,N);\r\n%%\r\n% Next, winnow out the duplicate rows before proceeding.\r\nlCpre = length(C);\r\nC = unique(C,'rows');\r\nlCpost = length(C);\r\n%%\r\n% I reduced the number of cases from |lCpre| to |lcPost|, a substantial\r\n% savings in this case.\r\n[lCpre lCpost]\r\n%%\r\n% Make scores unique as well.\r\nscores = sum(C,2);\r\nscores = unique(scores);\r\n%%\r\n% Finally, get rid of the valid scores.\r\nnonScores2 = 1:(max(Points)*N);\r\nnonScores2(scores(2:end)) = [];\r\n%% Bobby's Solution\r\n% <https:\/\/www.mathworks.com\/cgi-bin\/texis\/webinator\/search\/?db=MSS&prox=page&rorder=750&rprox=750&rdfreq=500&rwfreq=500&rlead=250&sufs=0&order=r&is_summary_on=1&ResultCount=10&query=%22bobby+cheng%22&submitButtonName=Search Bobby Cheng> \r\n% came up with a very different solution which works only if the minimum\r\n% score is zero. Otherwise, the algorithm would need to be modified.\r\nf = @(a)unique(bsxfun(@plus,a(:),Points));\r\nallPossibleScores = Points; % with only one question\r\nfor i = 2:N\r\n    allPossibleScores = f(allPossibleScores);\r\nend\r\nnonScores3 = setdiff(N*min(Points):N*max(Points),allPossibleScores);\r\n\r\n%% Lucio's First Solution\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/authors\/1858 Lucio Cetto>\r\n% came along next and contributed two solutions.  The first one is similar\r\n% to Bobby's, but Lucio propogates logical values instead of doubles (with\r\n% integer values).\r\n%%\r\n% Initialize the outputs so the possible test scores are set to |true| for\r\n% the initial point values for the first question.  \r\na = false(max(Points),1);\r\na(nonzeros(Points)) = true;\r\n%%\r\n% Iterate over the number of questions remaining, and augment the score\r\n% array.\r\nfor i = 1:N-1\r\n    a(bsxfun(@plus,find(a),Points)) = true;\r\nend\r\n%%\r\n% The locations of the |false| values in |a| are the test scores that no\r\n% test achieves.\r\nnonScores4 = find(~a)';\r\n\r\n%% Lucio's Second Solution\r\n% I will leave this one as an exercise for you to figure out.  It is very\r\n% dense, but works quite well.\r\nmaxscorep1 = N*max(Points)+1;\r\nA = toeplitz(sparse(1,1,1,1,maxscorep1),sparse(1,Points+1,1,1,maxscorep1));\r\nA = A^N;\r\nnonScores5 = find(A(1,:)==0)-1;\r\n\r\n\r\n%% Compare Answers\r\n% Let's now compare all the methods to be sure they get the same answer.\r\nallequal = ...\r\n    isequal(ImpossibleScores, nonScores1, nonScores2, ...\r\n    nonScores3, nonScores4, nonScores5)\r\n%% Other Methods?\r\n% I didn't time the various methods, but trust me, the ones I contributed\r\n% are the slowest and the most memory-intensive.  Walter's is fully \r\n% vectorized as well as mine, but can be a bit intensive in memory (but\r\n% still nothing like mine, as far as I can tell!). Bobby's and\r\n% Lucio's are the most efficient memory-wise, since they iterate over test\r\n% questions, and toss out impossible combinations as they go.  Do you have\r\n% other techniques to share? Please do so\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=164#respond here>.\r\n\r\n\r\n\r\n\r\n##### SOURCE END ##### b3f8c5627d0449549975dfa18eef2c1b\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   \r\n      Walter Roberson, frequent contributor to the MATLAB newsgroup, posed the following question to me to use as the starter idea of a blog.\r\n      \r\n      Q: Suppose there is a... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2008\/12\/02\/possible-test-scores\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[10,7,6,11],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/164"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=164"}],"version-history":[{"count":4,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/164\/revisions"}],"predecessor-version":[{"id":2592,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/164\/revisions\/2592"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=164"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=164"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=164"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}