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

Posted by programmingpraxis
Filed in Exercises
10 Comments »

10 Responses to “School Awards”

  1. matthew said
    November 3, 2015 at 11:28 AM

    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
    November 3, 2015 at 4:59 PM

    @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
    November 3, 2015 at 5:42 PM

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

  4. programmingpraxis said
    November 3, 2015 at 5:55 PM

    @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
    November 3, 2015 at 5:59 PM

    Something went wrong with the formatting there for sure.

  6. matthew said
    November 3, 2015 at 6:01 PM

    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
    November 3, 2015 at 6:01 PM

    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
    November 3, 2015 at 6:03 PM

    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
    November 3, 2015 at 6:12 PM

    That works. Thank you.

  10. matthew said
    November 5, 2015 at 8:10 PM

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

Leave a comment