Becoming the greatest tower builder

Question

I am trying to learn how to write proper code in python, and stumbled upon the following problem.

Bob is given a set of building blocks b, and a number n of towers to build. Since we are in communist land the towers should have as equal of an height as possible. The catch is that you are only given a maximum of 300 seconds to build the towers. The goal is to minimize the std of the tower height.

Say you are given the following vector

bricks = [8     8     8     6     6     4     4     4     4     3     3     2]

and asked to build 5 towers. One output to the problem can be

 8     4     0
 8     4     0
 8     4     0
 6     4     2
 6     3     3

Which has an std of std = ([12-12]^2+[12-12]^2+...+[12-12]^2)^1/2=0. for 3 towers the output should be

 8     4     4     4
 8     6     3     3
 8     6     4     2

Which again is optimal. Note however I am not asking for an optimal solution.. So this is similar to the knapsack problem. But here the goal is not to fill each knapsack to the brim, but rather to have each knapsack have as close weight as possible.

I came up with two possible codes

def TowerGreed(bricks,nTower):

    bricks.sort(reverse=True)
    lengthBricks = len(bricks)

    if lengthBricks > nTower:
        Tower = [[] for i in range(0,nTower)]
        for i in range(0,lengthBricks):
            if i < nTower:
                Tower[i].append(bricks[i])
            elif i == nTower:
                Height = bricks[0:nTower]
                Tower[i-1].append(bricks[i])
                Height[nTower-1] = bricks[i] + Height[nTower-1]
            else:
                lowest = Height.index(min(Height))
                Tower[lowest].append(bricks[i])
                Height[lowest] = bricks[i] + Height[lowest]

    return Tower

This is a standard Greed algorithm. It first sort the elements, then it adds one element to each tower. Then it starts checking which tower is the smallest. The smallest tower is given the next piece.

A modified version of the code above, is given below

def towerGreedImproved(bricks,numberTowers):

    # First we sort the number of bricks from greatest to smallest
    bricks.sort(reverse = True) 

    # Only runs the algorithm if we have more bricks than towers to build
    if len(bricks) >= numberTowers:
        Towers = [[] for i in range(0,numberTowers)] #Empty vector [[],[],...]
        Height = [0] * numberTowers # Zero vector [0,0,...]
        avgHeight = sum(bricks)/numberTowers

        """ Loops through each tower, adds elements until that tower is just
            bellow the average tower height """
        for j in range(0,numberTowers):
            while Height[0] + bricks[0] < avgHeight:
                Towers[j].append(bricks[0])
                Height[j] = bricks[0] + Height[j]
                del bricks[0]; #Deletes used bricks

        for n in bricks:
            lowest = Height.index(min(Height))
            Towers[lowest].append(n)
            Height[lowest] = n + Height[lowest]

    print(Towers)        
    return Towers

Here we also start by sorting the bricks, but the difference is we build one tower at a time. We stop building before we reach the average towerheight. This average is given as the sum of the bricks divided by the number of towers being built.

and third option was to randomize the input. The code above is somewhat slow for large vectors. To test my code, I tried the following three vectors. 2 towers, 3 towers, and finnaly 23 towers. Being more familiar with MATLAB i wrote the following code snippet. However I am not quite sure how to impliment it into python, nor if it provides any improvement.

Being a beginner in writing proper code, I have a couple of questions

• Which improvements can I make to my coding style?
• People talked about dynamic solutions to this problem. Are there better algorithms for this problem?
• How can I determine which algorithm is best suited for a given dataset?

Answer 1

Perhaps:

def towerGreedImproved(bricks, numberTowers):
    # First we sort the number of bricks from greatest to smallest
    obricks = list(bricks)
    obricks.sort(reverse = True) 

    # Only runs the algorithm if we have more bricks than towers to build
    if len(obricks) < numberTowers:
        return obricks

    towers = tuple([] for i in range(numberTowers))  # Empty vector ([],[],...)
    height = [0] * numberTowers  # Zero vector [0,0,...]
    avgHeight = sum(obricks)/numberTowers

    """ Loops through each tower, adds elements until that tower is just
        below the average tower height """
    for j in range(numberTowers):
        while height[0] + obricks[0] < avgHeight:
            # Deletes used bricks
            brick = obricks.pop(0)
            towers[j].append(brick)
            height[j] += brick

    for n in obricks:
        lowest = min(enumerate(height), key = lambda kv: kv[1])[0]
        towers[lowest].append(n)
        height[lowest] += n

    return towers

bricks = (8, 8, 8, 6, 6, 4, 4, 4, 4, 3, 3, 2)
print(towerGreedImproved(bricks, 5))

Of note:

• Python variable names should be lowercase
• It's not playing nice to chew up someone's input list - make a copy
• towers can be a tuple because we don't expect the contents to change
• you should do something more reasonable on brick shortage, like return the brick list
• range doesn't need a first argument of 0
• use pop() to both get and delete an element
• use += for addition and assignment
• use enumerate with min so that you can get the min's index in one shot
• don't automatically print the result on the inside of the function; let the user decide

Answer 2

Whereas my previous answer was mostly a Python clean-up, I believe this one is also an algorithmic improvement. Note that it requires a (common) third-party library, blist, that you can acquire through pip.

from blist import sortedlist

def tower_greed_sort(bricks, tower_count):
    ''' Return a list of tower_count lists, each [height, [blocks]]
    '''

    # A copy of bricks, sorted from shortest to tallest
    obricks = list(bricks)
    obricks.sort()

    # The towers: [[height, [block, block, ...]], ...]
    # Take the last (tallest) tower_count bricks
    towers = sortedlist([b, [b]] for b in obricks[-tower_count:])

    # Only runs the algorithm if we have more bricks than towers to build
    if len(obricks) > tower_count:
        # Iterate through the rest of the bricks
        for brick in obricks[:-tower_count]:
            # Here we know that the first tower is the shortest. Remove it for now.
            shortest = towers.pop(0)
            shortest[0] += brick
            shortest[1].append(brick)
            ''' Instead of doing an O(n) min search through the heights, or even an
                O(nlogn) full sort of the towers by height, we do a blist sorted
                insert of the modified tower: O(log**2 n).
                See http://stutzbachenterprises.com/blist/sortedlist.html
            '''
            towers.add(shortest)
    return towers


bricks = (8, 8, 8, 6, 6, 4, 4, 4, 4, 3, 3, 2)
print(tower_greed_sort(bricks, 5))

Answer 3

Consider the first method, TowerGreed. The first thing to do is to change capitalization to its cannonical form and even up spacing a bit. Also

• replace range(0, x) with range(x)
• replace arr[0:x] with arr[:x]
• replace a = b + a with a += b for commutative operations
• rename tower→towers, height→heights, length_bricks→number_bricks
• invert the if
• split the for loop into its three sections, removing the ifs

This gives:

def tower_greed(bricks, n_tower):
    bricks.sort(reverse=True)
    number_bricks = len(bricks)

    if number_bricks <= n_tower:
        return towers

    towers = [[] for i in range(n_tower)]

    for i in range(n_tower):
        towers[i].append(bricks[i])

    heights = bricks[:n_tower]
    towers[n_tower-1].append(bricks[n_tower])
    heights[n_tower-1] += bricks[n_tower]

    for i in range(n_tower + 1, number_bricks):
        lowest = heights.index(min(heights))
        towers[lowest].append(bricks[i])
        heights[lowest] += bricks[i]

    return towers

Then remove

    towers[n_tower-1].append(bricks[n_tower])
    heights[n_tower-1] += bricks[n_tower]

and shift down the start of the last part to accomadate:

    ...
    heights = bricks[:n_tower]

    for i in range(n_tower, number_bricks):
        lowest = heights.index(min(heights))
        towers[lowest].append(bricks[i])
        heights[lowest] += bricks[i]

    return towers

Change

    towers = [[] for i in range(n_tower)]

    for i in range(n_tower):
        towers[i].append(bricks[i])

to

    towers = [[bricks[i]] for i in range(n_tower)]

Consider

    if number_bricks <= n_tower:
        return towers

This will error since towers has not been defined. No error actually needs to be raised at all, so an appropriate message would instead be

        return NotImplementedError("number_bricks <= n_tower")

and the inequality should be a strong one since the code is fine with number_bricks == n_tower:

    if number_bricks < n_tower:
        return NotImplementedError("number_bricks < n_tower")

I would personally remove number_bricks:

def tower_greed(bricks, n_tower):
    bricks.sort(reverse=True)

    if len(bricks) < n_tower:
        return NotImplementedError("len(bricks) < n_tower")

    towers = [[bricks[i]] for i in range(n_tower)]
    heights = bricks[:n_tower]

    for i in range(n_tower, len(bricks)):
        lowest = heights.index(min(heights))
        towers[lowest].append(bricks[i])
        heights[lowest] += bricks[i]

    return towers

Then replace the for loops with loops over the bricks:

    towers = [[brick] for brick in bricks[:n_tower]]
    heights = bricks[:n_tower]

    for brick in bricks[n_tower:]:
        lowest = heights.index(min(heights))
        towers[lowest].append(brick)
        heights[lowest] += brick

Then consider simplifying the logic by initializing to 0 and looping over all the bricks:

    towers = [[] for _ in range(n_tower)]
    heights = [0] * n_tower

    for brick in bricks:
        lowest = heights.index(min(heights))
        towers[lowest].append(brick)
        heights[lowest] += brick

which allows you to remove

    if len(bricks) < n_tower:
        return NotImplementedError("len(bricks) < n_tower")

leaving you with just

def tower_greed(bricks, n_tower):
    bricks.sort(reverse=True)

    towers = [[] for _ in range(n_tower)]
    heights = [0] * n_tower

    for brick in bricks:
        lowest = heights.index(min(heights))
        towers[lowest].append(brick)
        heights[lowest] += brick

    return towers

---

Consider the second method, towerGreedImproved. It's worth noting that for somthing called Improved it seems to do worse.

The first thing to do is to change capitalization to its cannonical form and even up spacing a bit. Also

• replace range(0, x) with range(x)
• replace a = b + a with a += b for commutative operations
• rename height→heights, avg_height→mean_height
• invert the if and change it to raise NotImplementedError
• cannonicalize the comment format
• remove the stray semicolon

def tower_greed_improved(bricks, number_towers):
    # First we sort the number of bricks from greatest to smallest
    bricks.sort(reverse=True)

    # Only runs the algorithm if we have more bricks than towers to build
    if len(bricks) < number_towers:
        raise NotImplementedError("len(bricks) >= number_towers")

    # List of empty lists: [[], [], ...]
    towers = [[] for i in range(number_towers)] 

    # List of 0s: [0, 0, ...]
    heights = [0] * number_towers
    mean_height = sum(bricks) / number_towers

    # Loops through each tower, adds elements until that
    # tower is just below the average tower height
    for j in range(number_towers):
        while heights[0] + bricks[0] < mean_height:
            towers[j].append(bricks[0])
            heights[j] += bricks[0]

            # Deletes used bricks
            del bricks[0]

    for n in bricks:
        lowest = heights.index(min(heights))
        towers[lowest].append(n)
        heights[lowest] += n

    print(towers)
    return towers

Consider

    for j in range(number_towers):
        while heights[0] + bricks[0] < avg_height:
            towers[j].append(bricks[0])
            heights[j] += bricks[0]

            # Deletes used bricks
            del bricks[0]

Surely this should use

        while heights[j] + bricks[0] < avg_height:

? This, in effect, prevents this from actually doing anything past the first tower!

This should also probably sort in the other direction and delete from the end:

def tower_greed(bricks, number_towers):
    # First we sort the number of bricks from greatest to smallest
    bricks.sort()

    # Only runs the algorithm if we have more bricks than towers to build
    if len(bricks) < number_towers:
        raise NotImplementedError("len(bricks) >= number_towers")

    # List of empty lists: [[], [], ...]
    towers = [[] for i in range(number_towers)] 

    # List of 0s: [0, 0, ...]
    heights = [0] * number_towers
    mean_height = sum(bricks) / number_towers

    # Loops through each tower, adds elements until that
    # tower is just below the average tower height
    for j in range(number_towers):
        while heights[j] + bricks[-1] < mean_height:
            towers[j].append(bricks[-1])
            heights[j] += bricks[-1]

            # Deletes used bricks
            del bricks[-1]

    for n in bricks[::-1]:
        lowest = heights.index(min(heights))
        towers[lowest].append(n)
        heights[lowest] += n

    return towers

since deleting from the start is O(n) and deleting from the end is O(1). This is also better written:

        while heights[j] + bricks[-1] < mean_height:
            brick = bricks.pop()
            towers[j].append(brick)
            heights[j] += brick

I would also avoid destroying input by using a copying sort:

    bricks = sorted(bricks)

There isn't much more to do to this algorithm because it's just a worse version of the original (I'm curious as to why you thought it'd be better).

---

Answering your second bullet,

People talked about dynamic solutions to this problem. Are there better algorithms for this problem?

the paper I linked suggests that the dynamic programming solution isn't appropriate because it has a memory cost

$$ n (k-1) \cdot m^{k-1} $$

where \$k\$ is the number of partitions, \$n\$ is the number of bricks and \$m\$ is the maximum value of the numbers. For \$k = 10\$, \$m = 2000\$, \$n = 10\$ we would need...

$$ 10 \cdot 9 \cdot 2000 ^ {9} = 46080000000000000000000000000000 $$

...a lot of memory.

If you want to use this option for the special case of small \$k\$, Wikipedia has a good rundown for \$k = 2\$.

Nevertheless, there are better algorithms, though, particularly because you have 300 seconds. Implementing the full searches from the paper would be overkill, but it would make sense to incorporate some trial-and-improvement over the first greedy algorithm. I would suggest writing a 2-way differencing algorithm and differencing the smallest and largest towers with this technique. Repeat until a near solution is found.