Advertisement
Guest User

Untitled

a guest
Dec 24th, 2024
338
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.70 KB | Source Code | 0 0
  1. # each wire = [value, op, list(inputs), list(outputs), in_ready]
  2. VALUE = 0
  3. OP = 1
  4. INPUTS = 2
  5. OUTPUTS = 3
  6. IN_READY = 4
  7. wires = dict()
  8. for l in sys.stdin:
  9.     l = l.strip()
  10.     if not l:
  11.         continue
  12.     if ":" in l:
  13.         name, val = l.split(":")
  14.         val = int(val)
  15.         wires[name] = [val, None, [], [], 0]
  16.     else:
  17.         in1, op, in2, arrow, outw = l.split(" ")
  18.         for w in (in1, in2, outw):
  19.             if w not in wires:
  20.                 wires[w] = [None, None, [], [], 0]
  21.         wires[outw][INPUTS] = [in1, in2]
  22.         wires[outw][OP] = op
  23.         wires[in1][OUTPUTS].append(outw)
  24.         wires[in2][OUTPUTS].append(outw)
  25.  
  26. def findgates(wires, xwires, ywires, zwires, adder):
  27.     xw = xwires[adder]
  28.     yw = ywires[adder]
  29.     zw = zwires[adder]
  30.     HAS = None # Half adder sum
  31.     HAC = None # Half adder carry
  32.     CO = None # Carry out
  33.     CI = None # Carry in
  34.     CI0 = None # Carry intermediate
  35.     OUT = None # Full adder output
  36.     for w in wires[xw][OUTPUTS]:
  37.         if set(wires[w][INPUTS]) == {xw, yw}:
  38.             if wires[w][OP] == "XOR":
  39.                 HAS = w
  40.             elif wires[w][OP] == "AND":
  41.                 HAC = w
  42.     # Both HAS and HAC must exist, because we swap only outputs.
  43.     for w in wires[HAS][OUTPUTS]:
  44.         if wires[w][OP] == "XOR":
  45.             OUT = w
  46.             CI = list(set(wires[w][INPUTS]) - {HAS})[0]
  47.     for w in wires[HAC][OUTPUTS]:
  48.         if wires[w][OP] == "OR":
  49.             CO = w
  50.             CI0 = list(set(wires[w][INPUTS]) - {HAC})[0]
  51.     # Promote the half-adder outputs
  52.     if adder == 0 and not CO and not OUT:
  53.         OUT = HAS
  54.         CO = HAC
  55.    
  56.     return { "CI" : CI, "HAS" : HAS, "HAC" : HAC, "CI0": CI0, "OUT": OUT, "CO": CO}
  57.  
  58. def wswap(wires, s1, s2):
  59.     swapped = set()
  60.     for wo in itertools.chain(wires[s1][INPUTS], wires[s2][INPUTS]):
  61.         if wo in swapped:
  62.             continue
  63.         no = []
  64.         for wi in wires[wo][OUTPUTS]:
  65.             if wi == s1:
  66.                 no.append(s2)
  67.             elif wi == s2:
  68.                 no.append(s1)
  69.             else:
  70.                 no.append(wi)
  71.         wires[wo][OUTPUTS] = no
  72.         swapped.add(wo)
  73.     wires[s1][OUTPUTS], wires[s2][OUTPUTS] = wires[s2][OUTPUTS], wires[s1][OUTPUTS]
  74.     wires[s1], wires[s2] = wires[s2], wires[s1]
  75.  
  76. xwires = list(filter(lambda x: x.startswith("x"), wires))
  77. xwires.sort()
  78. ywires = list(filter(lambda x: x.startswith("y"), wires))
  79. ywires.sort()
  80. zwires = list(filter(lambda x: x.startswith("z"), wires))
  81. zwires.sort()
  82. lastCO = None
  83. okwires = set()
  84. goodgates = set()
  85.  
  86. def isgatebad(wires, lastCO, xwires, ywires, zwires, i):
  87.     gates = findgates(wires, xwires, ywires, zwires, i)
  88.     bad = zwires[i] != gates["OUT"]
  89.     bad = bad or (lastCO is not None and gates["CI"] != lastCO)
  90.     if i:
  91.         bad = bad or not gates["CI"]
  92.     bad = bad or not gates["CO"] or (i > 0 and not gates["CI0"])
  93.     lastCO = gates["CO"]
  94.     return (bad, lastCO, gates)
  95.  
  96. for i in range(0, len(xwires)):
  97.     (bad, lastCO, gates) = isgatebad(wires, lastCO, xwires, ywires, zwires, i)
  98.     # Some gates may be good but the previous gate is bad.
  99.     if not bad:
  100.         okwires = okwires.union(filter(lambda x: x is not None, gates.values()))
  101.         goodgates.add(i)
  102. okwires = okwires.union(xwires)
  103. okwires = okwires.union(ywires)
  104. badwires = set(wires) - okwires
  105. #print(badwires)
  106. mustinclude = []
  107. for w in badwires:
  108.     if w in zwires and wires[w][OP] != "XOR":
  109.         mustinclude.append(w)
  110. #print(mustinclude)
  111. otherbadwires = badwires.difference(mustinclude)
  112. xorwires = set()
  113. for w in otherbadwires:
  114.     if wires[w][OP] == "XOR":
  115.         xorwires.add(w)
  116. comb = []
  117. for xors in itertools.permutations(xorwires, len(mustinclude)):
  118.     remains = otherbadwires.difference(xors)
  119.     for rems in itertools.permutations(remains, 8 - len(xors) * 2):
  120.         perm = xors + rems;
  121.         swap = []
  122.         for i, mi in enumerate(mustinclude):
  123.             swap.append((mi, perm[i]))
  124.         for i in range(len(mustinclude), len(perm), 2):
  125.             swap.append((perm[i], perm[i+1]))
  126.         comb.append(tuple(swap))
  127.        
  128. #print(len(comb))
  129. for swi, tryswaps in enumerate(comb):
  130.     lastCO = None
  131.     bad = False
  132.     for sw in tryswaps:
  133.         wswap(wires, sw[0], sw[1])
  134.     for i in range(0, len(xwires)):
  135.         (bad, lastCO, gates) = isgatebad(wires, lastCO, xwires, ywires, zwires, i)
  136.         if bad:
  137.             break
  138.     for sw in reversed(tryswaps):
  139.         wswap(wires, sw[0], sw[1])
  140.     #if (swi % 10000) == 0:
  141.         #print(swi, len(comb), (swi * 100)/len(comb))
  142.     if not bad:
  143.         ans = list(itertools.chain.from_iterable(tryswaps))
  144.         ans.sort()
  145.         print(",".join(ans))
  146.         break;
  147.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement