OptimalSort

from __future__ import nested_scopes

import bisect

class _Num:
    def __init__(self, value, index):
        self.value = value
        self.i = index

    def __lt__(self, other):
        return self.value < other.value

# This implements the Karmarkar-Karp heuristic for partitioning a set
# in two, i.e. into two disjoint subsets s.t. their sums are
# approximately equal.  It produces only one result, in O(N*log N)
# time.  A remarkable property is that it loves large sets:  in
# general, the more numbers you feed it, the better it does.

class Partition:
    def __init__(self, nums):
        self.nums = nums
        sorted = [_Num(nums[i], i) for i in range(len(nums))]
        sorted.sort()
        self.sorted = sorted

    def run(self):
        sorted = self.sorted[:]
        N = len(sorted)
        connections = [[] for i in range(N)]

        while len(sorted) > 1:
            bigger  = sorted.pop()
            smaller = sorted.pop()

            # Force these into different sets, by "drawing a
            # line" connecting them.
            i, j = bigger.i, smaller.i
            connections[i].append(j)
            connections[j].append(i)

            diff = bigger.value - smaller.value
            assert diff >= 0
            bisect.insort(sorted, _Num(diff, i))

        # Now sorted contains only 1 element x, and x.value is
        # the difference between the subsets' sums.

        # Theorem:  The connections matrix represents a spanning tree
        # on the set of index nodes, and any tree can be 2-colored.
        # 2-color this one (with "colors" 0 and 1).

        index2color = [None] * N

        def color(i, c):
            if index2color[i] is not None:
                assert index2color[i] == c
                return
            index2color[i] = c
            for j in connections[i]:
                color(j, 1-c)

        color(0, 0)

        # Partition the indices by their colors.
        subsets = [[], []]
        for i in range(N):
            subsets[index2color[i]].append(i)

        return subsets

def twoSortOptimal(bricks):

    p = Partition(bricks)

    index1, index2 = p.run()

    list1 = [bricks[x] for x in index1]
    list2 = [bricks[x] for x in index2]

    return (list1,list2)

def towerGreed(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

def towerBuild(bricks,n_tower):

    if n_tower == 2:
        return twoSortOptimal(bricks)

    towers = towerGreed(bricks,n_tower)
    heights= [sum(i) for i in towers]
    print numpy.std(heights)

    for k in range(100):
        heights = [sum(i) for i in towers]
        lowest = min(enumerate(heights), key = lambda kv: kv[1])[0]
        heighest = max(enumerate(heights), key = lambda kv: kv[1])[0]

        tempTower1=list(towers[lowest])
        tempTower1.extend(list(towers[heighest]))

        tempTower1, tempTower2 = twoSortOptimal(tempTower1)
        towers[lowest] = tempTower1
        towers[heighest] = tempTower2

    return towers

if __name__ == "__main__":
# Unindent the two nextlines if you want to load a list of bricks from file

    with open('buildingSite3.txt') as f:
        bricks = [int(line.strip()) for line in f]

        numberTowers = 23
        towers = towerBuild(bricks,numberTowers)
        heights= [sum(i) for i in towers]
        print numpy.std(heights)
        print(towers)
        print([sum(i) for i in towers])