from __future__ import nested_scopes, print_function

import bisect
import numpy

from collections import namedtuple
from itertools import combinations

Num = namedtuple("Num", ["value", "i"])

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

def partition(nums):
    nums = sorted(Num(num, i) for i, num in enumerate(nums))

    N = len(nums)
    connections = [[] for _ in range(N)]

    while len(nums) > 1:
        bigger  = nums.pop()
        smaller = nums.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(nums, 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, not c)

    color(0, 0)

    # Partition the indices by their colors.
    subsets = [[], []]

    for i, color in enumerate(index2color):
        subsets[color].append(i)

    return subsets

def two_sort_optimal(bricks):
    indexes_1, indexes_2 = partition(bricks)

    tower_1 = [bricks[x] for x in indexes_1]
    tower_2 = [bricks[x] for x in indexes_2]

    return tower_1, tower_2

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

def tower_build(bricks, n_tower):
    if n_tower == 2:
        return two_sort_optimal(bricks)

    towers = tower_greed(bricks, n_tower)

    heights = [sum(i) for i in towers]
    print("First pass stdev:", numpy.std(heights))

    def reshuffle(tower_1, tower_2):
        old_diff = abs(sum(tower_1) - sum(tower_2))

        new_tower_1, new_tower_2 = two_sort_optimal(tower_1 + tower_2)

        new_diff = abs(sum(new_tower_1) - sum(new_tower_2))

        if old_diff <= new_diff:
            return False

        tower_1[:] = new_tower_1
        tower_2[:] = new_tower_2

        return True

    while True:
        towers.sort(key=sum)

        shuffles = [reshuffle(t1, t2) for t1, t2 in combinations(towers, 2)]

        if not any(shuffles):
            break

    return towers

if __name__ == "__main__":
    with open('buildingSite3.txt') as f:
        numberTowers = 23
        bricks = [int(line.strip()) for line in f]

        towers = tower_build(bricks,numberTowers)

        heights = [sum(i) for i in towers]
        print("Final stdev:", numpy.std(heights))
        print(towers)
        print(*map(sum, towers))