LebGeeks

Ra8

Member

[Exercise] Boxes in boxes in boxes

You are given N blocks with different sizes and you need to buy boxes to pack them. A box of size S costs S dollars.
You can only pack 2 blocks in 1 box. example, if you have a block of size 2 and a block of size 3, you can pack them in a box of size 5.
You need to pack all the boxes 2 by 2 to get 1 box at the end. for example:
If you are given the following blocks: 1, 2 and 3

You can pack 1 and 2 and buy a box of size 3, you still have a of size 3 to pack and the original block of size 3 to pack.
You pack the 3 and 3 block into a box of size 6.
The total cost of this order of packaging is 3+6=9$

Another way to pack them is to start with the block 2 and 3 in a box of size 5.
You still have the original block of size 1 and the new one of size 5, you pack them in a box of size 6.
The total cost of this order of packaging is 5+6=11$

Given this array of N block, compute the minimal cost.
Examples:
[1,2,3] => 9
[1,5,3,6,3,5,2,5,7,9,11,23,4,1,4] => 310
[101,213,42,98,2,74,21,4] => 1341

This kind problem is very important in computer science as it is the basics of data compression algorithms. After solving the exercise read about Huffman coding.

Joe

Member

Re: [Exercise] Boxes in boxes in boxes

This code is based on the assumption that the minimal cost is reached by recursively boxing the smallest 2 blocks together until you have only one block left. It's just an assumption, I don't know how to prove if it's really the minimal or not, but it does verify the 3 examples given:

def minimal_cost(blocks):
    """Returns the minimal cost to box all blocks.
    For example:

    >>> minimal_cost([1, 2, 3])
    9

    >>> minimal_cost([1,5,3,6,3,5,2,5,7,9,11,23,4,1,4])
    310

    >>> minimal_cost([101,213,42,98,2,74,21,4])
    1341
    """
    a = blocks
    cost = 0

    while len(a) > 1:
        sorted_blocks = list(sorted(a))
        a = [sum(sorted_blocks[:2])] + sorted_blocks[2:]
        cost += a[0]

    return cost

PS: In case you're not familiar with it, you can use the examples given in the comment as tests, using the kick ass doctest module.

Ra8

Member

Re: [Exercise] Boxes in boxes in boxes

Yes that's the correct solution.
I found a set of slides that explains and proves the Huffman coding if you're interested.