W dzień wigilijny miałem nadzieję że zadanie będzie prosteze gdyż chciałem spędzić go z rodziną, dostaliśmy zadanie którego część 2 była lekkim wyzwaniem ale całkiem szybko zrozumiałem co trzeba w niej zrobić.

Zadanie

Na wejściu otrzymujemy listę bramek logicznych które mają po dwa wejścia i jedno wyjście, dostajemy też wartości na wejściach to pewnej części bramek. Naszym zadaniem jest zasymulować działanie tych bramek i zwrócić wartości na wyjściach zaczynających się na literę z

Przykład:

xxxyyyxxx000000000012012012::::::AXO111010NORDRyyy000201zzz000201

Uznałem że najlepszym sposobem będzie przedstawienie tych bramek jako grafu i zastosowanie topologicznego sortowania aby uzyskać kolejność w której powinniśmy obliczać wyniki kolejnych bramek (wszystkie inputy powinny być obliczone zanim przejdziemy do liczenia outputu)

Do tego celu użyjemy wbudowaną w bibliotekę standardową Pythona klasę TopologicalSorter

import sys
from graphlib import TopologicalSorter

a, b = sys.stdin.read().strip().split("\n\n")

# Wartości na danych wierzchołkach
values = {}
for line in a.split("\n"):
    k, v = line.split(": ")
    values[k] = int(v)

# Zbierzmy bramki w słownik by ułatwić ich przetwarzanie
gates = {}
for line in b.split("\n"):
    a, b = line.split(" -> ")
    gates[b] = a

# Stwórzmy graf z bramek
graph = {}
for out, gate in gates.items():
    s = gate.split()
    graph[out] = {s[0], s[2]}

ts = TopologicalSorter(graph)

# Obliczmy wartości na wyjściach dla każdej bramki
for node in ts.static_order():
    if node in values:
        continue
    gate = gates[node]
    d1, op, d2 = gate.split()
    if op == "AND":
        values[node] = values[d1] & values[d2]
    elif op == "OR":
        values[node] = values[d1] | values[d2]
    else:
        values[node] = values[d1] ^ values[d2]

# Zbierzmy jako wynik wartości na wyjściach zaczynających się na z
result = ""
for node, val in sorted(values.items(), reverse=True):
    if node.startswith("z"):
        result += str(val)

# Konwersja binarnej liczby na dziesiętną
print(int(result, 2))

W ten sposób otrzymujemy poprawną odpowiedź na pierwsze zadanie.

Część 2

Okazuje się że nasz obwód jest obwodem obliczającym sumę dwóch liczb, poszczególne bity liczb wejściowch x i y są wrzucane do rejestrów x00, x01, ..., x44 i y00, y01, ..., y44, z kolei wyjście jest zapisywane w rejestrach z00, z01, ..., z45.

Niestety w obwodzie występują błędy i musimy je znaleźć. Błędy polegają na tym że wyjścia 8 bramek zostały zamienione ze sobą. Jako output mamy wypisać nazwy tych 8 wyjść posortowane alfabetycznie.

Jako pierwsze zwizualizowałem sobie obwód za pomocą biblioteki graphviz, żeby zrozumieć lepiej co się w nim dzieje.

import sys

import graphviz

a, b = sys.stdin.read().strip().split("\n\n")

values = {}
for line in a.split("\n"):
    k, v = line.split(": ")
    values[k] = int(v)

gates = {}
for line in b.split("\n"):
    a, b = line.split(" -> ")
    gates[b] = a

dot = graphviz.Digraph()
for out, gate in sorted(gates.items()):
    s = gate.split()
    dot.node(out, label=f"{s[1]} ({out})")
    dot.edge(s[0], out)
    dot.edge(s[2], out)
dot.render("circuit", format="png", cleanup=True)

Polecam uruchomić ten kod i zobaczyć jak wygląda graf, ale od razu można zobaczyć strukturę która się tworzy. Jest to najbardziej podstawowa implementacja addera, w której możemy zaobserwować komponent dla każdego bitu. Każdy komponent na wejściu otrzymuje bity wejściowe z x i y oraz carry z poprzedniego bitu i zwraca wartość z oraz carry do następnego komponentu. Warto jeszcze zaznaczyć że:

  • pierwszy komponent nie bierze carry (ma tylko dwa wejścia).
  • w ostatnim komponencie carry jest zwracane jako najbardziej znacząca cyfra z

Uznałem że na tym etapie nie wiem jak na szybko sprawdzić co jest okej a co nie, ale mogę wygenerować adder taki jak powinien on być:

correct_circuit = ""

# pierwszy komponent nie ma wejścia od carry
correct_circuit += "x00 AND y00 -> carry00\n"
correct_circuit += "x00 XOR y00 -> z00\n"

# każdy kolejny komponent
for i in range(1, 44):
    z = f"z{i-1:02}"
    x, y = f"x{i:02}", f"y{i:02}"
    prev_carry = f"carry{i-1:02}"
    carry = f"carry{i:02}"
    aand = f"and{i:02}"
    xor = f"xor{i:02}"
    cand = f"cand{i:02}"

    correct_circuit += f"{x} AND {y} -> {aand}\n"
    correct_circuit += f"{x} XOR {y} -> {xor}\n"
    correct_circuit += f"{xor} XOR {prev_carry} -> {z}\n"
    correct_circuit += f"{xor} AND {prev_carry} -> {cand}\n"
    correct_circuit += f"{cand} OR {aand} -> {carry}\n"

W ten sposób generujemy sobie string który byłby poprawnym obwodem.

Jako że błędów jest dość mało uznałem że najprostszym sposobem będzie napisanie algorytmu który znajdzie błędy, a następnie błędy poprawię ręcznie.

Parsujemy nasze grafy w ten sposób:

def parse(string):
    graph = {}
    for line in string.split("\n"):
        a, op, b, _, dest = line.split()
        # sortujemy argumenty do bramek by nie było problemów
        # z wyszukiwaniem ich jeśli podamy inną kolejność
        if a > b:
            a, b = b, a
        graph[f"{a} {op} {b}"] = dest
    return graph

correct = parse(correct_circuit.strip())
given = parse(sys.stdin.read().strip().split("\n\n")[1])

Jako że wyjścia w grafie danym mają dosyć enigmatyczne nazwy (w odróżnieniu od moich nazw, typu carry, aand…), stworzę mapping który będzie mapował moje nazwy na te z grafu danego, za każdym razem gdy w grafie danym nie będzie jakiegoś połączenia którego spodziewa się graf poprawny wyrzucę błąd i dokonam ręcznej inspekcji w danym miejscu w grafie wygenerowanym przez graphviz:

mflmfaoaaoprsprptpiixmmmigaisimn,aaa=na,fefagipppgtapnypppf[eomrsp=,iii"l,paacepbirnnnza,p,harrn{azggg{sdprieg}n[[[4tebib=cna[g=xyz4]snhtkde]]]:t=g=f(e(f0=["nfs4"===2igab{o"t4x}lna],mtM]){xyz"atai:isce>apis=:to.pns0rsmiig2rpangni}elpgigv"cip[v:e,ttiaen.(n]n{[fi)g}:ss"t[eeyeb{aa{m]orris:pcc:(}hh0)}]2:{}m("a{,pap}fi"n{zgo{[pib}:]0}{2"b}}")")

Po uruchomieniu tego kodu wywalamy się na pierwszym błędzie, w moim przypadku był to błąd w bramce ‘z05’, po spojrzeniu na graf zauważyłem dokładnie co było nie tak, poprawiłem ten błąd hardkodując go w ten sposób, przed sprawdzaniem poprawności

swaps = {
    "z05": "tst",
    "tst": "z05",
}

for k, v in given.items():
    if v in swaps:
        given[k] = swaps[v]

print(",".join(sorted(swaps.keys())))

# ...
# mapping = {}
# for i in range(44):

Przy kolejnym uruchomieniu kodu, znajdujemy kolejny błąd w dalszej bramce. Powtarzamy ten proces aż znajdziemy wszystkie błędy. Print który napisałem w poprzednim snippecie zwraca nam odpowiedź na część 2.

Podsumowanie

Zadanie było według mnie bardzo ciekawe, przypomniałem sobie dzięki niej zajęcia z bramek logicznych które miałem na pierwszym semestrze studiów. Rozwiązanie ręczne nie jest najlepszym rozwiązaniem, ale na pewno najprostszym i nie miałem ochoty dzisiaj za bardzo zagłębiać się w to zadanie i poświęcać na nie duzo czasu. Jutro ostatnie zadanie jestem bardzo ciekaw co autorzy przygotowali na zakończenie.