Zadanie
W dzisiejszym zadaniu musimy policzyć pola i obwody regionów na gridzie 2d, przykładowo:
AAAA
BBCD
BBCC
EEEC
Na powyższym gridzie mamy region A który ma pole 4 i obwód 10 (obwód liczymy jako ilość sąsiadujących pól które nie są z tego regionu), region B ma pole 4 a obwód 8. Jednym z problemów może być to że regiony mogą być też w środku innych regionów np:
AAA
AOA
AAA
Region A ma pole 8 ale obwód 16, a region O ma pole 1 i obwód 4
Na całej planszy może być kilka regionów z tą samą literką, ale jeśli nie są one połączone to traktujemy je jako osobne regiony.
Jako wynik musimy policzyć sumę pól wszystkich regionów pomnożonych przez ich obwody.
Rozwiązanie
Na pierwszy rzut oka odpowiednim algorytmem na rozwiązanie tego zadania wydaje się być DFS, będziemy rozpoczynać go od każdego pola w którym jeszcze nie byliśmy tak długo aż wyczerpiemy wszystkie pola.
Oto struktura skryptu, później zajmiemy się implementacją dfsa
import sys
data = [l.strip() for l in sys.stdin.readlines()]
to_visit = {(i, j) for i in range(len(data)) for j in range(len(data[i]))}
def dfs(i, j) ...
result = 0
while to_visit:
i, j = to_visit.pop()
area, perimeter = dfs(i, j)
result += area * perimeter
print(result)
Żeby kod był bardziej czytelny zdefiniuję sobie kilka funkcji pomocniczych:
def out_of_bound(i, j):
# sprawdza czy nasze indeksy wychodzą poza pole
return i < 0 or j < 0 or i >= len(data) or j >= len(data[0])
def neighborbood(i, j):
# iteruje po sąsiadujących polach
for di, dj in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
yield i + di, j + dj
Przechodząc do faktycznego mięsa, funkcja DFS prezentuje się tak:
def dfs(i, j):
area = 1
peri = 0
for ni, nj in neighborbood(i, j):
# kiedy natrafimy na pole z innego regionu lub poza planszą zwiększamy obwód
if out_of_bound(ni, nj) or data[ni][nj] != data[i][j]:
peri += 1
continue
# ignorujemy pola z tego samego regionu na których już byliśmy
if (ni, nj) in to_visit:
to_visit.remove((ni, nj))
narea, nperi = dfs(ni, nj)
area += narea
peri += nperi
return area, peri
Łącząc cały kod w jedną całość uzyskujemy odpowiedź do pierwszej części
Część druga
Tym razem zamiast obwodu musimy policzyć ilość boków każdego regionu. Liczenie boków w takim gridzie nie wydaje się być prostym zadaniem. Wydaje mi się że zamiast tego możemy policzyć ilość wierzchołków i będzie ona równa ilości boków.
Wierzchiłki
Liczenie wierzchołków powinno być prostsze gdyż jest bardziej lokalne niż liczenie boków, bok może się rozciągać przez wiele pól, a wierzchołki da się wykryć w pojedyńczej iteracji DFSa.
Jak znaleźć wierzchołek? Spójrzmy na przykładzie fragmentu regionu A:
.x
xA
xA
Żeby znaleźć lewy górny wierzchołek musimy sprawdzić czy pole bezpośrednio nad polem A i bezpośrednio po lewo od niego, są różnie niż on sam. Jeśli chociaż jeden z nich jest taki sam to mamy sytuację jak w dolnym A, czyli nie ma tam wierzchołka. Musimy dla każdego pola sprawdzić wszystkie pary sąsiednich boków naszego kwadracika.
Niestety po napisaniu kodu który robi to co opisałem powyżej, wyniki dla testowych danych były nieco za niskie, po chwili pomyślenia zauważyłem że zgubiłem edge case. Weźmy taki przykład:
.A
AA
Moja poprzednia metoda nie znajdzie wierzchołka w środku planszy, musimy sprawdzić trzy wartości a nie tylko dwie, jeśli góra i lewo są tego samego typu ale pole po skosie jest innego typu to też mamy wierzchołek.
Rozwiązanie
Stworzymy sobie dodatkowy iterator który pozwoli nam łatwo dostać dla każdego kwadracika, jego trójki które nas interesują:
N = [(-1, 0), (0, -1), (1, 0), (0, 1)]
def neighbor_triples(i, j):
for x in range(len(N)):
ai, aj = N[x]
a = (i + ai, j + aj)
bi, bj = N[(x + 1) % len(N)]
b = (i + bi, j + bj)
diag = (i + ai + bi, j + aj + bj)
yield a, b, diag
Później w środku dfsa wykrywanie wierzchołków będzie wyglądać tak:
for (ai, aj), (bi, bj), (di, dj) in neighbor_triples(i, j):
aother = out_of_bound(ai, aj) or data[ai][aj] != data[i][j]
bother = out_of_bound(bi, bj) or data[bi][bj] != data[i][j]
dother = out_of_bound(di, dj) or data[di][dj] != data[i][j]
if aother and bother or (not aother and not bother and dother):
vert += 1
Tłumacząc a i b to są sąsiedzi po pionowi i poziomi, a d, to nasz sąsiad, po
przekątnej. Sprawdzamy czy spełnia się jeden z dwóch scenariuszy które opisałem powyżej.
Cały kod
Jako że liczenie wierzchołków nie przeszkadza w żaden sposób pierwszemu zadaniu połączyłem obie części w jeden skrypt:
import sys
data = [l.strip() for l in sys.stdin.readlines()]
to_visit = {(i, j) for i in range(len(data)) for j in range(len(data[i]))}
def out_of_bound(i, j):
return i < 0 or j < 0 or i >= len(data) or j >= len(data[0])
N = [(-1, 0), (0, -1), (1, 0), (0, 1)]
def neighborbood(i, j):
for di, dj in N:
yield i + di, j + dj
def neighbor_triples(i, j):
for x in range(len(N)):
ai, aj = N[x]
a = (i + ai, j + aj)
bi, bj = N[(x + 1) % len(N)]
b = (i + bi, j + bj)
diag = (i + ai + bi, j + aj + bj)
yield a, b, diag
def dfs(i, j):
area = 1
peri = 0
vert = 0
for (ai, aj), (bi, bj), (di, dj) in neighbor_triples(i, j):
aother = out_of_bound(ai, aj) or data[ai][aj] != data[i][j]
bother = out_of_bound(bi, bj) or data[bi][bj] != data[i][j]
dother = out_of_bound(di, dj) or data[di][dj] != data[i][j]
if aother and bother or (not aother and not bother and dother):
vert += 1
for ni, nj in neighborbood(i, j):
if out_of_bound(ni, nj) or data[ni][nj] != data[i][j]:
peri += 1
continue
if (ni, nj) in to_visit:
to_visit.remove((ni, nj))
narea, nperi, nvert = dfs(ni, nj)
area += narea
peri += nperi
vert += nvert
return area, peri, vert
part1 = 0
part2 = 0
while to_visit:
i, j = to_visit.pop()
area, peri, vert = dfs(i, j)
part1 += area * peri
part2 += area * vert
print(part1)
print(part2)
Podsumowanie
Rozwiązanie nie wyszło najczystsze, mógłbym zrefaktorować je używając klasy complex,
tak jak to zrobiłem w dniu ósmym. Ale kod
działa i zwraca rozwiązanie w 0.12 sekundy więc zostawię go tak jak jest.