Project Euler 107

http://projecteuler.net/index.php?section=problems&id=107

点と辺から成る数学対象をグラフといいます。辺に重みがついているとネットワークと呼びます。辺を一つでも取り除くと複数の繋がっていない部分に分かれてしまうグラフを木といいます。木はループを含みません。逆にまだ取り除ける辺がある場合、ループがあることになります。そこでループを探します。そしてそのループの中の一つの辺を取り除きます。もちろん取り除くのは最も重みの大きい辺です。これをループがなくなるまで繰り返します。

from itertools import *

def regist(line):
    return dict((k, int(e)) for e, k in
                izip(line.split(','), count()) if e[0] != "-")

def remove_edge(g):
    def find_loop(path, prev, v):
        for nei in ifilter(lambda nei: nei != prev, g[v]):
            try:
                p = path.index(nei)
                return path[p:] + [ nei ]
            except:
                loop = find_loop(path + [ nei ], v, nei)
                if len(loop) > 0:
                    return loop
        return []
    
    loop = find_loop([], -1, 0)
    if len(loop) > 0:
        def max_weight(x, y):
            return max(x, y, key = lambda k: g[loop[k]][loop[k+1]])
        k = reduce(max_weight, xrange(len(loop) - 1))
        v1, v2 = loop[k], loop[k+1]
        w = g[v1][v2]
        del g[v1][v2]
        del g[v2][v1]
        return w
    else:
        return 0

file = open("network.txt")
g = map(regist, file.readlines())
file.close()
print sum(takewhile(lambda w: w > 0, (remove_edge(g) for k in count())))