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

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.

As you say, turning the recursion into a dynamic programming solution is tricky, but this seems to work:

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:

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: