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

Pages: 1 2

### 10 Responses to “School Awards”

1. matthew said

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.

2. programmingpraxis said

@Matthew: I wrote exactly the same combos function you did; mine didn’t work, and neither does yours. Your dynamic function looks correct.

3. matthew said

Are you sure? Both functions give the same result for n = 0 to 20 (and they agree with your numbers above).

4. programmingpraxis said

@Matthew: I don’t have a C++ compiler on my computer at work, so I quickly translated to Python:

```>>> def combos(n, l, a):
...     if a < 0 or l >> for n in xrange(1,20):
...     print n, combos(n, 1, 3)
...
1 3
2 8
3 20
4 45
5 99
6 212
7 444
8 917
9 1871
10 3780
11 7576
12 15081
13 29847
14 58776
15 115240
16 225081
17 438123
18 850224
19 1645452```

Did I do something wrong somewhere?

5. matthew said

Something went wrong with the formatting there for sure.

6. matthew said

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))))))
```
7. programmingpraxis said

I’ll try that again:

```>>> def combos(n, l, a):
...     if a < 0 or l *lt; 0: return 0
...     if n == 0: return 1
...     return combos(n-1,l,2) + combos(n-1,l,a-1) + combos(n-1,l-1,2)
...
>>> for n in xrange(1,20):
...     print n, combos(n, 1, 3)
...
1 3
2 8
3 20
4 45
5 99
6 212
7 444
8 917
9 1871
10 3780
11 7576
12 15081
13 29847
14 58776
15 115240
16 225081
17 438123
18 850224
19 1645452```
8. matthew said

Ah, actually, I see the problem, the top level call needs to be “combos(n,1,2)”, not “combos(n,1,3)”

9. programmingpraxis said

That works. Thank you.

10. matthew said

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);
}
}

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) || 20;
var l = parseInt(process.argv) || 1;
var a = parseInt(process.argv) || 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));
}
```