Becoming the greatest tower builder

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

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

StackExchange Code Review Q#74206, answer score: 4