gistfile1

#!/usr/bin/python
# Brute force solution to the Facebull problem

import cProfile
import sys, os, re, operator
import dijkstra
from graph import cross

def verify(kset, combos):
    
    pairs = combos.copy()
    graph = {}
    for (n,s,d,c) in kset:
        if s in graph:
            graph[s][d] = c
        else:
            graph[s] = { d : c }

    for s in graph:
        try:
            dist, prev = dijkstra.Dijkstra(graph,s)
        except KeyError:
            return False
        for d in dist:
            pairs.discard((s,d))

    if len(pairs) > 0:
        return False
    else:
        return True

def zcombinations(n, r):
    if r > n:
        return
    val = None
    p = 0
    while n >= r:
        indices = range(r)

        while True:
            val = (yield tuple(indices))
            if val is None:
                x = r
            else:
                indices = list(val)
                x = p

            for i in reversed(range(x)):
                if indices[i] != i + n - r:
                    p = i
                    break
            else:
                break

            indices[p] += 1
            for j in range(p+1, r):
                indices[j] = indices[j-1] + 1

        r += 1

class FaceBull:

    def __init__(self, f):
        self.cost = None
        self.solution = None
        self.machines = list()
        self.compounds = set()
        self.pairs = set()

        for line in file(f).readlines():
            (name, src, dst, cost) = line.rstrip().split()
            name = int(name.replace('M',''))
            src = int(src.replace('C',''))
            dst = int(dst.replace('C',''))
            cost = int(cost)
            self.compounds.add(src)
            self.compounds.add(dst)
            self.machines.append(tuple([name,src,dst,cost]))

        self.machines = sorted(self.machines, key=operator.itemgetter(3))
        self.pairs = cross(self.compounds,self.compounds)

    def solve(self):
        self.solution = range(len(self.machines))
        self.cost = sum([ m[3] for m in self.machines ])
        combos = zcombinations(len(self.machines), len(self.compounds))
        shift = False
        while True:
            try:
                if not shift:
                    indices = combos.next()
                else:
                    indices = combos.send(indices)
                    shift = False
            except StopIteration:
                break
            cost = sum([ self.machines[j][3] for j in indices ])
            if self.cost <= cost:
                shift = True
                continue
            kset = tuple( self.machines[j] for j in indices )
            if not verify(kset, self.pairs):
                continue
            self.solution = indices
            self.cost = cost
            shift = True

    def out(self):
        if self.solution is None:
            print "No solution"
            return
        output = str(self.cost) + "\n"
        solution = sorted([ self.machines[i][0] for i in self.solution ])
        solution = ' '.join([ str(x) for x in solution ])
        output += solution
        return output

def main(argv=None):
    
    if argv is None:
        argv = sys.argv

    if len(argv) != 2:
        return -1

    if os.path.isfile(sys.argv[1]):
        f = FaceBull(sys.argv[1])
        f.solve()
        print f.out()
    else:
        return -1

    return 0

if __name__ == "__main__":
    #sys.exit(main())

    import time
    timer = time.time

    infile = re.compile(r".*\.in$")
    for f in os.listdir(sys.argv[1]):
        if not infile.match(f):
            continue
        fb = FaceBull(sys.argv[1] + os.sep + f)
        t1 = timer()
        fb.solve()
        t2 = timer()
        ans = fb.out()
        (outfile, ext) = f.split('.')
        check = file(sys.argv[1] + os.sep + outfile + ".out").read()
        check = check.strip()
        if ans != check:
            print "failure on %s %.2f" % (f, t2-t1)
        else:
            print "success on %s %.2f" % (f, t2-t1)