Weather Report

"The goal is to use an encoding that minimizes the expected number of transmitted bits." If you read that, had taken CS201 at duke, and DIDN'T think "huffman coding" shame on you.

We can't explicitly calculate the huffman tree, however, since 4^20 is too big. So what extra structure do we have (one of my favorite questions!)? Well since there are only 4 probabilities, there are going to be a ton of repeats. All we care about are the unique ones. The number of unique probabilities is just the number of different counts of weather days we can have over an n day range, without respect to order (since order won't affect the probability). This is just the integer partitions of n, which for 20 is relatively small (1 partition of size 1, 10 of 2, 33 of 3 and 64 of size 4). We then have to multiply those by the ways we can assign those to the different weathers...so 1 * 4 + 10 * (4 choose 2) * 2! + 33 * (4 choose 3) * 3! + 64 * 4! = 4 + 120 + 792 + 1536 = 2452 unique probabilities...max.

Anyway, we iterate through all of them (using modified next_combination), and store the probability and the number of ways you can get that probability. Sort the nodes by probability, and like huffman, start with the smallest ones. If P is your smallest probability and you can do it N ways, then you add N/2 nodes with probability 2P back into your queue and note that it takes 1 bit to encode....JUST LIKE HUFFMAN! It's really just 1 node in the queue, but we have to remember there are N/2 of them.

Now when you combine those combo nodes, you have to calculate the expected bits...which is just a regular expected value calculation...value of left * probability of left + value of right * probability of right.

Take care to handle the situation where you have an odd N, so have to pull one from the next highest P.