2.py (1141B) [raw]
1 #!/usr/bin/env python3 2 import sys 3 from collections import defaultdict 4 5 rules = defaultdict(set) 6 prints = [] 7 8 def findbad(pr): 9 all = set(pr) 10 seen = set() 11 for pg in pr: 12 seen.add(pg) 13 for dep in rules[pg]: 14 if dep in all and dep not in seen: 15 return (pg, dep) 16 return None 17 18 # XXX: this is not efficient or safe, but its late at night 19 # and it works OK (feels like a topographical sort would be better?) 20 def get_ordered(pr): 21 o = [x for x in pr] 22 bad_pg, bad_dep = findbad(o) 23 while bad_pg: 24 pg_i = o.index(bad_pg) 25 dp_i = o.index(bad_dep) 26 o[pg_i] = bad_dep 27 o[dp_i] = bad_pg 28 bad = findbad(o) 29 if bad: 30 bad_pg, bad_dep = bad 31 else: 32 break 33 return o 34 35 in_rules = True 36 for l in sys.stdin: 37 l = l.strip() 38 if l == "": 39 in_rules = False 40 continue 41 if in_rules: 42 (l, r) = l.split("|") 43 rules[r].add(l) 44 else: 45 prints.append(l.split(",")) 46 47 tot = 0 48 for pr in prints: 49 if findbad(pr): 50 o = get_ordered(pr) 51 tot += int(o[int(len(pr)/2)]) 52 53 print(tot)