You’ve landed at the Universal Orbit Map facility on Mercury. Because navigation in space often involves transferring between orbits, the orbit maps here are useful for finding efficient routes between, for example, you and Santa. You download a map of the local orbits (your puzzle input).
Except for the universal Center of Mass (COM), every object in space is in orbit around exactly one other object. An orbit looks roughly like this:
# \
# \
# |
# |
# AAA--> o o <--BBB
# |
# |
# /
# /In this diagram, the object BBB is in orbit around AAA. The path that BBB takes around AAA (drawn with lines) is only partly shown. In the map data, this orbital relationship is written AAA)BBB, which means “BBB is in orbit around AAA”.
Before you use your map data to plot a course, you need to make sure it wasn’t corrupted during the download. To verify maps, the Universal Orbit Map facility uses orbit count checksums - the total number of direct orbits (like the one shown above) and indirect orbits.
Whenever A orbits B and B orbits C, then A indirectly orbits C. This chain can be any number of objects long: if A orbits B, B orbits C, and C orbits D, then A indirectly orbits D.
For example, suppose you have the following map:
COM)B B)C C)D D)E E)F B)G G)H D)I E)J J)K K)L Visually, the above map of orbits looks like this:
# G - H J - K - L
# / /
# COM - B - C - D - E - F
# \
# IIn this visual representation, when two objects are connected by a line, the one on the right directly orbits the one on the left.s
Here, we can count the total number of orbits as follows:
D directly orbits C and indirectly orbits B and COM, a total of 3 orbits. L directly orbits K and indirectly orbits J, E, D, C, B, and COM, a total of 7 orbits. COM orbits nothing. The total number of direct and indirect orbits in this example is 42.
What is the total number of direct and indirect orbits in your map data?
input_text <- read_lines("input6.txt") Create a helper function for reading in arbitrary input files
com_data_to_df <- function(input_text) {
read_lines(input_text) %>%
strsplit(",") %>% #strsplit leaves the resulting vector in a list
flatten() %>%
unlist()
}Show Parent / Object pairs in a df.
df <- com_data_to_df(input_text) %>%
tibble(full_orbit = .) %>%
separate(full_orbit, c("parent_object", "object"), "\\)")
df## # A tibble: 1,035 x 2
## parent_object object
## <chr> <chr>
## 1 LH2 LD6
## 2 SSV S13
## 3 G9G LNJ
## 4 XN6 BNR
## 5 D8D K4S
## 6 7ZK C14
## 7 6VH FRD
## 8 N1T DPN
## 9 2TN 43C
## 10 VQ9 YJR
## # ... with 1,025 more rowsWe’ll check how many times each object appears in the parent list.
#make every object have every grand(x n)parent as a parent_object
graph_df <- graph_from_data_frame(df, directed = TRUE)
all_children_df <- map(
V(graph_df),
~ names(
subcomponent(graph_df, .x, mode="out")
)
) %>%
map_df(~data.frame(object=.x), .id="parent_object") %>%
filter(object != parent_object) %>%
as_tibble()#count total number of great(x n)grand children
children_count <- all_children_df %>%
group_by(parent_object) %>%
summarise(indirect_children = n()) %>%
arrange(desc(indirect_children))
children_count## # A tibble: 955 x 2
## parent_object indirect_children
## <chr> <int>
## 1 COM 1035
## 2 BM7 1034
## 3 5BB 1033
## 4 2NZ 1032
## 5 GG1 1031
## 6 D1X 1030
## 7 3ZF 1029
## 8 RHY 1028
## 9 KC6 1027
## 10 1QL 1026
## # ... with 945 more rowsNow that we know how many things are orbiting each parent, we’ll sum all the children to get the total number of orbits
children_count$indirect_children %>% sum()## [1] 147223Now, you just need to figure out how many orbital transfers you (YOU) need to take to get to Santa (SAN).
You start at the object YOU are orbiting; your destination is the object SAN is orbiting. An orbital transfer lets you move from any object to an object orbiting or orbited by that object.
For example, suppose you have the following map:
COM)B B)C C)D D)E E)F B)G G)H D)I E)J J)K K)L K)YOU I)SAN Visually, the above map of orbits looks like this:
# YOU
# /
# G - H J - K - L
# / /
# COM - B - C - D - E - F
# \
# I - SANIn this example, YOU are in orbit around K, and SAN is in orbit around I. To move from K to I, a minimum of 4 orbital transfers are required:
K to J J to E E to D D to I Afterward, the map of orbits looks like this:
# G - H J - K - L
# / /
# COM - B - C - D - E - F
# \
# I - SAN
# \
# YOUWhat is the minimum number of orbital transfers required to move from the object YOU are orbiting to the object SAN is orbiting? (Between the objects they are orbiting - not between YOU and SAN.)
All I care about is orbits that contain me or santa, and more specifically I care about those orbits me AND NOT santa or santa AND NOT me. Note that technically, what I’m doing is counting all the locations where either (not both) of us are children, not the number of transfers I need to make. The number of transfers will involve one counting 1 orbit more (where santa and I share a common orbit) and one orbit fewer (because it counts the object I’m orbiting now, before my first transfer). These two miscounting effects cancel out.
The new code is implemented at the end of the next code block.
As one function, we have:
steps_away <- function(input_text, target1, target2) {
orbits <- com_data_to_df(input_text)
df <- tibble(full_orbit = orbits, stringsAsFactors = FALSE) %>%
separate(full_orbit, c("parent_object", "object"), "\\)")
#make every object have every grand(x n)parent as a parent_object
graph_df <- graph_from_data_frame(df, directed = TRUE)
all_children_df <- map(
V(graph_df),
~ names(
subcomponent(graph_df, .x, mode="out")
)
) %>%
map_df(~data.frame(object=.x), .id="parent_object") %>%
filter(object != parent_object) %>%
as_tibble()
#count total number of great(x n)grand children
children_count <- all_children_df %>%
group_by(parent_object) %>%
summarise(indirect_children = n()) %>%
arrange(desc(indirect_children))
#find orbits that contain target1
target1_df <- all_children_df %>%
filter(object == target1) %>%
select(parent_object, object)
#find orbits that contain targets2
target2_df <- all_children_df %>%
filter(object == target2) %>%
select(parent_object, object)
#find orbits that contain targets 1 and 2
t1_and_t2_df <- inner_join(target1_df, target2_df, by = "parent_object")
#find orbits that contain target1 xor target2
target1_xor_target2_df <- target1_df %>%
bind_rows(target2_df) %>%
anti_join(t1_and_t2_df, by = "parent_object")
target1_xor_target2_df %>% nrow()
}Testing everything out we expected 4 steps away in our test case.
steps_away("test1.txt", "YOU", "SAN")## [1] 4And our final guess is
steps_away(input_text, "YOU", "SAN")## [1] 340With this, we can navigate our way to santa in only 340 short steps!