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:

x00: 1
x01: 1
x02: 1
y00: 0
y01: 1
y02: 0

x00 AND y00 -> z00
x01 XOR y01 -> z01
x02 OR y02 -> z02

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:

mapping = {}
for i in range(44):
    x, y, z = f"x{i:02}", f"y{i:02}", f"z{i:02}"
    mapping[x] = x
    mapping[y] = y
    mapping[z] = z
last = f"z{44:02}"
mapping[last] = last

for gate, dest in correct.items():
    a, op, b = gate.split()
    if mapping[a] > mapping[b]:
        a, b = b, a

    search = f"{mapping[a]} {op} {mapping[b]}"
    if search not in given:
        print(f"Missing: {search} ({a} {op} {b})")
        break
    mapping[dest] = given[search]

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.