Movement

brute.py

import sys
import itertools

def read(filename):
    graph = {}
    f = open(filename)
    n = int(f.readline())
    for i in range(n-1):
        line = f.readline()
        numbers = map(int, line.split())
        dept1 = numbers[0]
        for j in range(2, len(numbers), 2):
            dept2 = numbers[j]
            weight = numbers[j+1]
            graph[dept1, dept2] = weight
    return n, graph

def report(permutation, movement):
    print >>sys.stderr, '[%d] %s' % (movement, ' '.join(map(str, permutation)))

def solve(n, graph):
    depts = range(1, n+1)
    min_permutation = None
    min_movement = None
    for permutation in itertools.permutations(depts):
        movement = 0
        position = {}
        for i in range(n):
            position[permutation[i]] = depts[i]
        for i, j in graph:
            weight = graph[i, j]
            distance = abs(position[i] - position[j])
            movement += distance * weight
        if min_permutation is None or movement < min_movement:
            min_permutation = permutation
            min_movement = movement
            report(min_permutation, min_movement)
    return min_permutation

if __name__ == '__main__':
    filename = sys.argv[1]
    n, graph = read(filename)
    permutation = solve(n, graph)
    print ' '.join(map(str, permutation))

level.py

import sys
import itertools
import operator

def read(filename):
    graph = {}
    f = open(filename)
    n = int(f.readline())
    for i in range(n-1):
        line = f.readline()
        numbers = map(int, line.split())
        dept1 = numbers[0]
        for j in range(2, len(numbers), 2):
            dept2 = numbers[j]
            weight = numbers[j+1]
            graph[dept1, dept2] = weight
    return n, graph

def adjlist(matrix):
    graph = {}
    for i, j in matrix:
        weight = matrix[i, j]
        if i not in graph:
            graph[i] = {}
        if j not in graph:
            graph[j] = {}
        graph[i][j] = weight
        graph[j][i] = weight
    return graph

def get_cost(graph):
    result = {}
    for i in graph:
        s = 0
        for j in graph[i]:
            s += graph[i][j]
        result[i] = s
    return result

def evaluate(n, graph, permutation):
    movement = 0
    position = {}
    for i in range(n):
        position[permutation[i]] = i+1
    for i, j in graph:
        weight = graph[i, j]
        distance = abs(position[i] - position[j])
        movement += distance * weight
    return movement

def level(graph, root):
    cost = get_cost(graph)
    queue = [root]
    visited = set([root])
    result = [root]
    while queue:
        i = queue.pop(0)
        for j in sorted(graph[i], key=lambda j: cost[j]):
            if j not in visited:
                queue.append(j)
                visited.add(j)
                result.append(j)
    return result

def solve(n, graph):
    adjgraph = adjlist(graph)
    depts = range(1, n+1)
    min_permutation = None
    min_movement = None
    for dept in depts:
        permutation = level(adjgraph, dept)
        movement = evaluate(n, graph, permutation)
        if min_permutation is None or movement < min_movement:
            min_permutation = permutation
            min_movement = movement
            print >>sys.stderr, min_movement,
    print >>sys.stderr
    return min_permutation

if __name__ == '__main__':
    filename = sys.argv[1]
    n, graph = read(filename)
    permutation = solve(n, graph)
    print ' '.join(map(str, permutation))