#!/usr/bin/env python2

# I'm going to stick this in a class at some point because passing all the shit between the functions is fugly
# Also: IT FUCKING WORKS!

"""original_matrix = [
    [17, 20, 13, 10],
    [ 6, 18,  7, 17],
    [11,  3,  2, 10],
    [ 4,  5, 11, 17]
]"""

"""original_matrix = [
    [17, 10, 12],
    [ 9,  8, 10],
    [14,  4,  7]
]"""

"""original_matrix = [
    [25,  4, 15,  7],
    [ 6,  3,  8, 18],
    [13,  2,  2,  4],
    [ 1,  1,  2,  1]
]"""

original_matrix = [
    [10,5,18,11],
    [3,2,4,5],
    [18,9,17,15],
    [11,6,19,10]
]

matrix = [l[:] for l in original_matrix]

def reduction(matrix):
    # Rows
    for key, row in enumerate(matrix):
        row_min = min(row)
        if row_min == 0:
            continue
        matrix[key] = [n - row_min for n in row]

    # Columns
    for i in range(len(matrix[0])):
        col = []
        for j in range(len(matrix)):
            col.append(matrix[j][i])
        col_min = min(col)
        if col_min == 0:
            continue
        for j in range(len(matrix)):
            matrix[j][i] -= col_min
    return matrix

def path_decision(matrix, assignments_overlay, total_assignments, assigned_cols, assigned_rows):
    # Given a bipartite graph matrix and a partial matching consisting only of necessary pairs, find a maximal matching.
    for j in range(len(matrix)):
        if j in assigned_rows:
            continue
        for i in range(len(matrix[0])):
            if i in assigned_cols:
                continue
            if matrix[j][i] == 0:
                my_overlay = [row[:] for row in assignments_overlay]
                my_overlay[j][i] = 1
                new_overlay, my_total_assignments, my_assigned_cols, my_assigned_rows = path_decision(matrix, my_overlay, total_assignments + 1, assigned_cols + [i], assigned_rows + [j])
                if not my_total_assignments == len(matrix):
                    continue
                assignments_overlay = new_overlay
                total_assignments = my_total_assignments
                assigned_cols = my_assigned_cols
                assigned_rows = my_assigned_rows
    return assignments_overlay, total_assignments, assigned_cols, assigned_rows

def assignments(matrix):
    assignments_overlay = [[0 for n in row] for row in matrix]
    total_assignments = 0
    assigned_cols = []
    assigned_rows = []
    keep_going = True
    while keep_going:
        keep_going = False
        # Rows
        for key, row in enumerate(matrix):
            if key in assigned_rows:
                continue
            temp_row = row[:]
            for col in assigned_cols:
                temp_row[col] = -1
            if temp_row.count(0) == 1:
                zeroindex = temp_row.index(0)
                assignments_overlay[key][zeroindex] = 1
                assigned_cols.append(zeroindex)
                assigned_rows.append(key)
                keep_going = True
                total_assignments += 1
        # Cols
        for i in range(len(matrix[0])):
            if i in assigned_cols:
                continue
            zeroes = 0
            for j in range(len(matrix)):
                if j in assigned_rows:
                    continue
                if matrix[j][i] == 0:
                    zeroes += 1
                    if zeroes > 1:
                        break
                    zero_index = j
            if not zeroes == 1:
                continue
            assignments_overlay[zero_index][i] = 1
            assigned_cols.append(i)
            assigned_rows.append(zero_index)
            keep_going = True
            total_assignments += 1
        if not keep_going and total_assignments < len(matrix):
            # We must decide which path to take. MAN THE HARPOONS!
            assignments_overlay, total_assignments, assigned_cols, assigned_rows = path_decision(matrix, assignments_overlay, total_assignments, assigned_cols, assigned_rows)
    return assignments_overlay, total_assignments, assigned_cols, assigned_rows

def ohgodtheresmore(matrix, assignments_overlay, total_assignments, assigned_cols, assigned_rows):
    marked_rows = []
    marked_cols = []
    for key, row in enumerate(matrix):
        if not key in assigned_rows:
            marked_rows.append(key)
    marked = True
    while marked:
        marked = False
        for row_key in marked_rows:
            for col_key, n in enumerate(matrix[row_key]):
                if col_key in marked_cols:
                    continue
                if n == 0:
                    marked_cols.append(col_key)
                    marked = True
        for i in marked_cols:
            for j in range(len(matrix)):
                if j in marked_rows:
                    continue
                if assignments_overlay[j][i] == 1:
                    marked_rows.append(j)
                    marked = True
    remaining_elements = []
    for i in range(len(matrix[0])):
        for j in range(len(matrix)):
            if (not i in marked_cols) and (j in marked_rows):
                remaining_elements.append(matrix[j][i])
    min_remaining = min(remaining_elements)
    for i in range(len(matrix[0])):
        for j in range(len(matrix)):
            if (i in marked_cols) and (not j in marked_rows):
                matrix[j][i] += min_remaining
            elif (not i in marked_cols) and (j in marked_rows):
                matrix[j][i] -= min_remaining
    assignments_overlay, total_assignments, assigned_cols, assigned_rows = assignments(matrix)
    return matrix, assignments_overlay, total_assignments, assigned_cols, assigned_rows

matrix = reduction(matrix)
assignments_overlay, total_assignments, assigned_cols, assigned_rows = assignments(matrix)

while total_assignments < len(matrix):
    matrix, assignments_overlay, total_assignments, assigned_cols, assigned_rows = ohgodtheresmore(matrix, assignments_overlay, total_assignments, assigned_cols, assigned_rows)

print assignments_overlay
print matrix
print original_matrix