aoc

Advent of Code Solutions
git clone git://git.alexkarle.com.com/aoc
Log | Files | Refs | README | LICENSE

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)