School Awards
November 3, 2015
This counting problem appears from time to time:
There is a school that awards students who, during a given period, are never late more than once and who are never absent for three or more consecutive days. How many permutations of on-time, late and absent, with repetition, are possible for a given timeframe that will result in an award being given to a particular student. For instance, for a three-day timeframe there are 19 ways in which a student can win an award.
Your task is to solve the counting problem given 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 
Here’s a nice recursive solution, combos(n,l,a) returns number of ways of being late no more than l times, with at most a absences.
int combos(int n, int l, int a) { if (a < 0 || l < 0) return 0; else if (n == 0) return 1; else return combos(n-1,l,2) + combos(n-1,l,a-1) + combos(n-1,l-1,2); }As you say, turning the recursion into a dynamic programming solution is tricky, but this seems to work:
int index(int n, int l, int a) { return 6*n + 3*l + a; } int dynamic(int n) { std::vector<int> s((n+1)*3*2); for (int i = 0; i < 6; i++) s[i] = 1; for (int i = 0; i < n; i++) { for (int l = 0; l < 2; l++) { for (int a = 0; a < 2; a++) { s[index(i+1,l,a+1)] += s[index(i,l,a)]; } int value = s[index(i,l,2)]; for (int a = 0; a < 3; a++) { s[index(i+1,l,a)] += value; if (l == 0) s[index(i+1,1,a)] += value; } } } return s[index(n,1,2)]; }Tribonacci solution is nice, but it’s not clear to me how to generalize it to other values of a and l.
@Matthew: I wrote exactly the same combos function you did; mine didn’t work, and neither does yours. Your dynamic function looks correct.
Are you sure? Both functions give the same result for n = 0 to 20 (and they agree with your numbers above).
@Matthew: I don’t have a C++ compiler on my computer at work, so I quickly translated to Python:
Did I do something wrong somewhere?
Something went wrong with the formatting there for sure.
If you want some Scheme, this seems to work:
(define (award l a n) (cond ((< l 0) 0) ((< a 0) 0) ((= n 0) 1) (else (+ (award l 2 (- n 1)) (award (- l 1) 2 (- n 1)) (award l (- a 1) (- n 1))))))I’ll try that again:
Ah, actually, I see the problem, the top level call needs to be “combos(n,1,2)”, not “combos(n,1,3)”
That works. Thank you.
After a little more thought, here’s a generalization of the recurrence in the Tribonacci solution. For a change, this one is is Javascript:
#!/usr/bin/node "use strict" function combos0(N,L,A) { function aux(n,l,a) { if (a < 0 || l < 0) return 0; else if (n === 0) return 1; else return aux(n-1,l,A) + aux(n-1,l,a-1) + aux(n-1,l-1,A); } return aux(N,L,A); } function sumrange(n,m,f) { var total = 0; for (var i = n; i <= m; i++) { total += f(i); } return total; } function combos1(N,L,A) { // 0 late days, up to a consecutive absences at end. function aux0(n,a) { if (a < 0) return 0; else if (n === 0) return 1; else return aux0(n-1,A) + aux0(n-1,a-1); } // Exactly l late days, up to A consecutive absences at end. // Each n-combination with l > 0 late days is uniquely composed // of an m-combination of l-1 late days, followed by a late day, // followed by a n-m-1 combination with 0 late days. function aux1(n, l) { if (l === 0) return aux0(n,A); else return sumrange(0,n-1, function(i) { return aux1(i,l-1)*aux0(n-1-i,A); }); } return sumrange(0,L, function(l) { return aux1(N,l); }); } var N = parseInt(process.argv[2]) || 20; var l = parseInt(process.argv[3]) || 1; var a = parseInt(process.argv[4]) || 2; console.log("L = " + l + ", A = " + a); for (var n = 0; n <= N; n++) { console.log(n + ": " + combos0(n,l,a) + " " + combos1(n,l,a)); }