Project Euler 219: Skewcost coding
Problem Description
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 prefixfree 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 prefixfree 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 prefixfree 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(10^{9}) ?
Project Euler 219 Solution
Runs < 0.001 seconds in Python 2.7.Use this link to get the Project Euler 219 Solution Python 2.7 source.
Answer
Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.Afterthoughts

No afterthoughts yet.
Discussion
No comments yet.