Dzisiaj padłem ofiarą przedwczesnych założeń, uznałem że końcowym inputem będą rządzić te same prawa co testowym, jak się okazało spowolniło mnie to mocno, ale ostatecznie zadanie i tak udało się rozwiązać.

Zadanie - część 1

Dzisiaj musimy posortować zbiór kartek (oznaczonych liczbami), w taki sposób żeby nie zaburzyć zasad kolejności drukowania, zasady zdefiniowane są w ten sposób:

47|53
97|13
97|61
...

Oznacza to że kartka 47 musi być wydrukowana przed 53, a 97 przed 13 i 61.

Następnie dostajemy kilka zbiorów kartek gdzie musimy zdecydować czy są topologicznie posortowane czy nie:

47,53,97,13,61
13,97,53
...

W tym przypadku pierwsza linia kartek jest posortowana w odpowiedniej kolejności a druga nie (13 nie powinno być przed 97). W wyniku mamy wziąć numery środkowych kartek każdego poprawnego ciągu i zsumować je.

Założenia

Całkiem szybko zauważyłem, że input wygląda tak że każda kartka ma zdefiniowane wszystkie swoje zależności, więc nie musimy bawić się w przechodniość relacji zależności.

Już tłumaczę, kolejność a, b, c, w inpucie zapisana będzie w taki sposób:

a|b
a|c
b|c

Kiedy tak na prawdę druga linijka nie jest potrzebna bo wiedząc że a|b i b|c, moglibyśmy wydedukować że a|c. Skorzystam z tej dziwności inputu. Założę też że nie będzie żadnych konfliktów w zależnościach i że da się stworzyć topologiczną kolejność.

Dla każdej kartki, stworzymy sobie zbiór jej zależności, później przeiterujemy, po wszystkich listach kartek sprawdzając czy każda następna kartka ma w swoich zależnościach poprzednią kartkę.

Rozwiązanie

Myślę że awk znowu się nada. Jako że plik na początku zawiera listę zależności późnej jedną pustą linię i listę list kartek, możemy sprytnie zapisać to w awku w taki sposób:

BEGIN { FS = "|" }  # ustawiamy separator na |
/\|/{ 
    # jeśli gdzieś w lini jest | to jesteśmy w lini z zależnością
}
/^$/ { FS = "," }   # kiedy znajdziemy pustą linię ustawiamy separator na ,
/,/ { 
    # analiza kartek
}
END {
    # wypisanie wyniku
}

Analiza zależności

Używając asocjacyjnych macierzy z awk stworzymy sobie zbiór zależności dla każdej kartki. Ustawiamy 1 (true), dla każdej zależności w każdej kartce.

/\|/{
    dependencies[$2][$1] = 1
}

Później będziemy mogli wydajnie sprawdzać czy jakaś kartka zależy od innej np.

if (page1 in dependencies[page2]) ...

Analiza kartek

Tym razem separator jest ustawiony na , i możemy łatwo iterować po kartkach w lini, sprawdzając czy kolejność jest zachowana.

Końcowo cały kod prezentuje się tak:

# part1.awk
BEGIN { FS = "|" }
/\|/{
    dependencies[$2][$1] = 1
}
/^$/ { FS = "," }
/,/ { 
    for (i = 1; i < NF; i++)
        if (!($(i) in dependencies[$(i+1)])) next
    sum += $(int((NF + 1) / 2))  # wyciągnij środkową kartkę
}
END { print sum }

Uruchomienie go przez awk -f part1.awk input.txt, pozwala nam uzyskać pierwszą gwiazdkę.

Część 2

Po przeczytaniu części drugiej uznałem że rozwiązanie nie powinno sprawić mi większego problemu, lecz wpadłem w pułapkę zastawioą przez twórcę zadania!

W tej części musimy posortować w odpowiednią kolejność linie które były błędne w pierwszej części i zsumować numery środkowych kartki z naprawionych list.

Założenia

Jeśli mamy podać liczbę z środka posortowanej listy, uznałem że na pewno w takim razie musi istnieć tylko jeden sposób na posortowanie każdej z nich, tym bardziej utwierdziło mnie to w przekonanianiu że każda kartka będzie miała zdefiniowaną każdą zależność.

Dobrze myślę prawda?

Uznałem że dobrym pomysłem będzie policzyć ilość zależności dla każdej kartki, kartki z mniejszą ilością zależności powinny być wydrukowane przed kartkami z większą ilością zależności.

/^$/ {
    for (page in dependencies) {
        for (dep in dependencies[page]) {
            dep_counts[page] += 1
        }
    }
...

Stworzymy teraz listę która będzie zawierała globalnie poprawną kolejność kartek. Kartka bez żadnych zależności powinna otrzymać index 0, kolejna kartka index 1 i tak dalej.

...
    for (page in dep_counts) {
        order[dep_counts[page]] = page
    }
...

Na do weryfikacji wypiszmy sobie poprawną kolejność kartek:

    ...
    print "Topological sort:"
    for (v in order) {
        printf("%d ", order[v])
    }
    printf "\n"
}

A w outpucie otrzymujemy…

99

Jedna kartka? Powinniśmy otrzymać listę! Gdzie jest błąd?

Okazuje się że każda kartka miała taką samą liczbę zależności: (24), więc wszystkie kolejno nadpisywały się w naszej macierzy asocjacyjnej i zamiast dostać topologicznie posortowaną listę otrzymaliśmy pojedyńczą liczbę.

Gdzie jest haczyk

Okazuje się że nasz graf zalezności jest cykliczny czyli w czystej teorii jesteśmy w stanie stworzyć listę której nie da się uporządkować topologicznie. Jednak zakładam, że takich sytuacji nie powinno być w inpucie.

Zmienimy podejście w taki sposób, że będziemy liczyć ilość zależności tylko dla kartek które są w aktualnej linii, powinno to naprawić problem.

Kod

Sprawdźmy jakie kartki są obecne w lini:

/,/ {
    for(i = 1; i <= NF; i++) {
        present[$i] = 1
    }
...

Policzmy ile zalezności obecnych w aktualnej lini ma każda kartka:

...
    for(page in present) {
        dep_count[page] = 0 # kartka bez zależności też musi być zainicjalizowana
        for(dep in dependencies[page]) {
            if(dep in present) {
                dep_count[page] += 1
            }
        }
    }
...

Stwórzmy porządek topologiczny tak jak wspominałem wcześniej

...
    for(page in dep_count) {
        order[dep_count[page]] = page
    }
...

Uznałem też że jako że możemy połączyć obie części w jedną, skoro dość mocno się ze sobą zazębiają, dlatego dodam tu sprawdzanie czy lista jest dobrze uporządkowana czy nie porównując ją do posortowanej listy.

...
    invalid = 0
    for(v in order) {
        if (order[v] != $(v+1)) {
            invalid = 1
            break
        }
    }
...

W zależności od tego czy lista była poprawna czy nie dodajemy jej środek do odpowiedniej zmiennej:

...
    mid = int(length(order) / 2)
    if (invalid) {
        part2 += order[mid]
    } else {
        part1 += order[mid]
    }
}
END {
    print "Part 1:", part1
    print "Part 2:", part2
}

Całe rozwiązanie

Końcowy kod prezentuje się tak:

BEGIN { FS = "|" }
/\|/  { dependencies[$2][$1] = 1 }
/^$/  { FS = "," } 
/,/ {
    delete present; delete dep_count; delete order

    # which pages are present in current line?
    for(i = 1; i <= NF; i++) {
        present[$i] = 1
    }

    # count dependencies
    for(page in present) {
        dep_count[page] = 0  # initialize even pages without deps
        for(dep in dependencies[page]) {
            if(dep in present) {
                dep_count[page] += 1
            }
        }
    }

    # topological sort (by page_counts)
    for(page in dep_count) {
        order[dep_count[page]] = page
    }

    # check if current set of pages is sorted correctly
    invalid = 0
    for(v in order) {
        if (order[v] != $(v+1)) {
            invalid = 1
            break
        }
    }
    mid = int(length(order) / 2)
    if (invalid) {
        part2 += order[mid]
    } else {
        part1 += order[mid]
    }
}
END {
    print "Part 1:", part1
    print "Part 2:", part2
}

Podsumowanie

Nauczka na dziś jest taka żeby nie zakładać nic o naszym inpucie dopóki tego nie sprawdzimy, chciałem pójść na skróty widząc że testowe dane są dobrze uporządkowane ale ostatecznie strzeliłem sobie w stopę.

Fajnie że udało się połączyć oba rozwiązania w jeden relatywnie zwięzły skrypt.