Let A and B be bit strings (sequences of 0’s and 1’s).
If A is equal to the leftmost length(A) bits of B, then A is said to be a prefix of B.
For example, 00110 is a prefix of 001101001, but not of 00111 or 100110.
A prefix-free code of size n is a collection of n distinct bit strings such that no string is a prefix of any other. For example, this is a prefix-free code of size 6:
0000, 0001, 001, 01, 10, 11
Now suppose that it costs one penny to transmit a ‘0’ bit, but four pence to transmit a ‘1’.
Then the total cost of the prefix-free code shown above is 35 pence, which happens to be the cheapest possible for the skewed pricing scheme in question.
In short, we write Cost(6) = 35.
What is Cost(109) ?
A lot of people stumbled across this blog, searching for the solution to problem 219, which seemed like a good indication that it might be a fun problem, so I skipped ahead to try it out. Unlike the early problems that I’d been solving, the really brain-dead obvious solution didn’t work here: using Huffman coding and maintaining the entire tree is way too big. But, since we always take the lowest cost node, and add 1 and 4 to the costs, the range of node costs at any time is at most five, so the slightly less brain-dead solution of keeping track of node counts and iterating works fine.
module Problem219 = let cost (c,(n0,n1,n2,n3,n4)) = c*n0 + (c+1L)*(n1) + (c+2L)*(n2) + (c+3L)*(n3) + (c+4L)*(n4) let counts = (1L,(1L,0L,0L,1L,0L)) |> Seq.unfold(fun (c,(n0,n1,n2,n3,n4)) -> if n0 > 0L then Some((c,(n0,n1,n2,n3,n4)), (c,(n0-1L,n1+1L,n2,n3,n4+1L))) else Some((c,(n0,n1,n2,n3,n4)), (c+1L,(n1-1L,n2+1L,n3,n4,1L)))) let ans = cost (Seq.nth (1000000000-2) counts)
In retrospect, using a recursive function instead of Seq.unfold probably would have been cleaner and, of course, this could be done in log time by doing n0 steps in single iteration, but I’m trying to keep my total time spent solving problems under my time spent writing up solution, so I’ll stick with this solution. I’ll probably go back and re-write the cost function at some point, though, since it’s just plain ugly.
A conversation with Seth the other day reminded me that I should be unit testing, so I started playing with xUnit, putting the incremental tests I’d been doing in the REPL into unit tests.
[<Fact>] let Test1 = Seq.nth 3 counts|> MustEqual (3L, (0L, 2L, 1L, 1L, 1L)) [<Fact>] let Test2 = Seq.nth 5 counts|> MustEqual (4L, (0L, 3L, 1L, 1L, 2L)) [<Fact>] let Test3 = minCost 6 |> MustEqual 35L [<Fact>] let Test4 = minCost 12 |> MustEqual 96L