School Awards

November 3, 2015

This problem is magical, with a brilliant explanation by Brian Scott at math.stackexchange.com/questions/1279610/. Considering the input as a string containing n characters L, A or O, one per day, Scott begins by counting the strings that contain no Ls, and finds there are 1, 2, 4, 7, 13, 24, 44, 81, 149, … of them; these are the tribonacci numbers (A000073) offset by 2. Then the desired number of awards for n days is the nth tribonacci number S[n] plus the product of S[i] and S[ni−1] for i < n:

(define (award days)
  (if (= days 1) 3
    (let loop ((xs (list 4 2 1)) (days days))
      (if (< 2 days)
          (loop (cons (+ (car xs) (cadr xs) (caddr xs)) xs) (- days 1))
          (+ (car xs) (sum (map * (cdr xs) (reverse (cdr xs)))))))))

The loop builds up the tribonacci numbers in xs, then computes the result in the final line. Special handling is required when days is 1, because the initial list of tribonacci numbers is too long. Here are the first few members of the sequence:

> (do ((n 1 (+ n 1))) ((< 20 n))
    (display n) (display #\tab)
    (display (award n)) (newline))
1       3
2       8
3       19
4       43
5       94
6       200
7       418
8       861
9       1753
10      3536
11      7077
12      14071
13      27820
14      54736
15      107236
16      209305
17      407167
18      789720
19      1527607
20      2947811

I’m surprised not to find that sequence in OEIS. If you’re not as good a mathematician as Scott, you can build up the answer using dynamic programming, although I’ll confess I never got that to work. The basic idea is that (award l a n) is (award l a (- n 1)) if the student is on-time the first day, (award (- l 1) a (- n 1)) if the student is late the first day, and (award l (- a 1) (- n 1)) if the student is absent the first day, with the recursion the sum of the three.

You can run the program at http://ideone.com/heFCdS.

Advertisements

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: