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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: