# 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]



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)


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?
• Why do you say it's a bit slow? It's under 0.05s for me, which seems much smaller than 300s. Four orders of magnitude, in fact. – Veedrac Dec 20 '14 at 0:36
• English is not my primary language, sorry for the confusion. greedSort is fast. However I can find a more optimal solution just randomizing the input. Alas randomizing is very time consuming. So my hope in adition to getting tips on style, was to get a better method than greed, and faster than rand sort. – N3buchadnezzar Dec 20 '14 at 1:27
• If you want the nitty-gritty, this is a good paper. If you want some interesting reading, I enjoyed this. – Veedrac Dec 20 '14 at 2:13
• IMO this is better-suited to cs.stackexchange.com than codereview. – Reinderien Dec 20 '14 at 2:25
• I wrote more code! pastebin.com/A8sVnGxD This one seems to perform a lot better than my first attempt. My coding habits have improved somewhat as well. Thanks for all the advice! It is hard when you know what you want to do, but is unable to do it in a new language. – N3buchadnezzar Dec 20 '14 at 22:48

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

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

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
'''

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

• Is this faster than using heapq? – Janne Karila Dec 20 '14 at 18:23
• Using heapq how, exactly? – Reinderien Dec 25 '14 at 23:21
• I mean, instead of using blist.sortedlist, to make towers a regular list and to manipulate it with heapq functions. The advantages are O(log n) insertions and being part of the standard library. – Janne Karila Dec 27 '14 at 20:47

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 towertowers, heightheights, length_bricksnumber_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:

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]



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]



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:


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]



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



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 heightheights, avg_heightmean_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)


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



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).

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.

• This is good feedback. Take caution on the heights.index(min(heights)) you left in the first method - it does a double-scan - once to get the min, and again to get the index of the min. As I suggested, this can be circumvented using enumerate. – Reinderien Dec 22 '14 at 6:29
• For some interesting performance analysis on that topic see stackoverflow.com/questions/13300962/… - for small lists the existing solution is probably best. – Reinderien Dec 22 '14 at 6:34