// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (15 votes, average: 5.00 out of 5)

Project Euler Solutions

Project Euler 219 Solution

Project Euler 219 Solution

Project Euler 219: Skew-cost 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 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) ?

Project Euler 219 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 219 Solution Python 2.7 source.


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.


    No afterthoughts yet.
Project Euler 219 Solution last updated


No comments yet.

Post a comment