Advent of Code 2019 - Day 6. Drzewo

1

https://adventofcode.com/2019/day/6
Jest podany przykład dla którego wynikiem jest 42:

        G - H       J - K - L
       /           /
COM - B - C - D - E - F
               \
                I

D directly orbits C and indirectly orbits B and COM, a total of 3 orbits. - 3
L directly orbits K and indirectly orbits J, E, D, C, B, and COM, a total of 7 orbits. - 7
Idąc tym tokiem mamy jeszcze:
E-F - 2
I-C-D-B - 4
H-G-B - 3
?
Ale sumując nie wychodzi 42. Skąd to 42? Na necie mnóstwo przykładów rozwiązań ale nikt nie tłumaczy jak "na sucho na kartce" to policzyć.

1

Sumujesz odległość każdego wierzchołka w drzewie od korzenia (COM):
B: [COM] = 1
C: [B, COM] = 2
G: [B, COM] = 2
H: [G, B, COM] = 3
D: [C, B, COM] = 3
I: [D, C, B, COM] = 4
E: [D, C, B, COM] = 4
F: [E, D, C, B, COM] = 5
J: [E, D, C, B, COM] = 5
K: [J, E, D, C, B, COM] = 6
L: [K, J, E, D, C, B, COM] = 7
SUM= 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 7 = 42

0

Nie wiem skad wziąłeś te swoje wyliczenia, ale przecież masz tu zwykłą rekursje -> I orbituje D i wszystko co orbituje D, czyli C, B i COM
Podobnie F orbituje E i wszystko dla E, czyli D, C, B, COM w sumie 5
Poza tym nie rozumiem co znaczy mamy jeszcze skoro masz to policzyc dla wszystkich wierzchołków drzewa.

def orbits(graph, v):
    if v == 'COM':
        return 1
    else:
        return 1 + orbits(graph, graph[v])

Jeśli założymy że graph to mapa która pokazuje kto orbituje kogo (czyli np. graph['B'] == 'COM') i nie wywołujemy tej funkcji dla samego 'COM'

0

"directly" to jest po prostu liczba ciał nie licząc COM, bo każde ciało z wyjątkiem COM krąży wokół czegoś. czyli 11.
"indirectly" liczymy dla każdego ciała z wyjątkiem COM jego odległość od COM (liczbę kresek) minus jeden (bo ten jeden to jest "directly")
i tak mamy:

B - 0 bo jedna kreska od COM
C - 1 bo dwie kreski od COM
D - 2 bo trzy kreski od COM
E - 3
F - 4
G - 1
H - 2
I - 3
J - 4
K - 5
L - 6

razem 31.

11 + 31 = 42

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0