The gravity assist was successful, and you’re well on your way to the Venus refuelling station. During the rush back on Earth, the fuel management system wasn’t completely installed, so that’s next on the priority list.
Opening the front panel reveals a jumble of wires. Specifically, two wires are connected to a central port and extend outward on a grid. You trace the path each wire takes as it leaves the central port, one wire per line of text (your puzzle input).
The wires twist and turn, but the two wires occasionally cross paths. To fix the circuit, you need to find the intersection point closest to the central port. Because the wires are on a grid, use the Manhattan distance for this measurement. While the wires do technically cross right at the central port where they both start, this point does not count, nor does a wire count as crossing with itself.
For example, if the first wire’s path is R8,U5,L5,D3, then starting from the central port (o), it goes right 8, up 5, left 5, and finally down 3:
# ...........
# ...........
# ...........
# ....+----+.
# ....|....|.
# ....|....|.
# ....|....|.
# .........|.
# .o-------+.
# ...........Then, if the second wire’s path is U7,R6,D4,L4, it goes up 7, right 6, down 4, and left 4:
# ...........
# .+-----+...
# .|.....|...
# .|..+--X-+.
# .|..|..|.|.
# .|.-X--+.|.
# .|..|....|.
# .|.......|.
# .o-------+.
# ...........These wires cross at two locations (marked X), but the lower-left one is closer to the central port: its distance is 3 + 3 = 6.
Here are a few more examples:
U62,R66,U55,R34,D71,R55,D58,R83 = distance 159
U98,R91,D20,R16,D67,R40,U7,R15,U6,R7 = distance 135
What is the Manhattan distance from the central port to the closest intersection?
maps <- read_lines("input3.txt") So, the big idea is that we’re going to create two matrices that will each have 1s along the path of the wires in their respective grids. We’ll add the two matrices together, and as a result, wire crossings will be represented by 2s in the summed matrix.
So, the next thing to do is build a matrix. To build that matrix, we’ll need to know how much memory to allocate for rows and columns, e.g. the max distance up, right, down, and left that is being traveled.
We’ll build a function that will record the max and min values of the x and y grid coordinates after every instruction.
track_motion <- function(location, inst) {
direction <- inst[1]
travel <- inst[2] %>% as.integer()
#add add travel to location
if (direction == "R") {
location[1] <- location[1] + travel
} else if (direction == "L") {
location[1] <- location[1] - travel
} else if (direction == "U") {
location[2] <- location[2] + travel
} else if (direction == "D") {
location[2] <- location[2] - travel
} else {
stop(
str_c("ValueError: ",
direction,
"is not a suitable travel direction.")
)
}
location
}instruction <- function(inst) {
direction <- substr(inst, 0, 1) #look at first letter
travel <- substr(inst, 2, 100) %>% as.integer() #look at remaining letters
c(direction, travel)
}Here we track all the corners that are turned.
coord_tracker <- function(d_list){
#make a table of positions to where the wires go
spacer <- rep(NA, length(d_list))
pos <- tibble(
x = spacer,
y = spacer
)
#initialize the first wire
pos[1, ] <- c(0, 0)
#grow the wire according to the instructions
for (i in 1:(length(d_list)-1)) {
inst <- instruction(d_list[i])
pos[i+1, ] <- track_motion(pos[i, ], inst)
}
instructions_df <- tibble(instruction = d_list)
instructions_df <- instructions_df %>%
mutate(
direction = substr(instruction, 0, 1), #look at first letter
travel = substr(instruction, 2, 100) %>% as.integer() #look at remaining letters
)
pos <- cbind(pos, instructions_df) %>% as_tibble()
}Now we’ll recursively follow directions to figure add 1s where there are wires, with this program.
make_new_wire <- function(wire_loc, start, direction, distance) {
x_change <- 0
y_change <- 0
new_wire_location <- rep(NA, distance)
if (direction == "U") {
y_change <- 1
} else if (direction == "D") {
y_change <- -1
} else if (direction == "R") {
x_change <- 1
} else if (direction == "L") {
x_change <- -1
}
for (i in 1:distance) {
new_wire_location[[i]] <- str_c(
start[1] + x_change * i,
", ",
start[2] + y_change * i
)
}
c(wire_loc, new_wire_location)
}Use the above function until all the wires are made
make_wire_grid_matrix <- function(df) {
wire_loc <- str_c(0, ", ", 0)
for (i in 1:nrow(df)) {
wire_loc <- make_new_wire(
wire_loc,
c(df$x[i], df$y[i]),
df$direction[i],
df$travel[i]
)
}
wire_loc
}Some helper functions
return_x_coords <- function(coords, i){
str_split(coords, pattern = ", ") %>%
flatten() %>%
as.numeric() %>%
.[1]
}
return_y_coords <- function(coords, i){
str_split(coords, pattern = ", ") %>%
flatten() %>%
as.numeric() %>%
.[2]
}And combining into one program, we have the following:
find_min_dist <- function(text1, text2){
map1 <- text1 %>% str_split(pattern = ",") %>% .[[1]]
map2 <- text2 %>% str_split(pattern = ",") %>% .[[1]]
pos1 <- coord_tracker(map1)
pos2 <- coord_tracker(map2)
set1 <- make_wire_grid_matrix(pos1)
set2 <- make_wire_grid_matrix(pos2)
intersection_points <- intersect(set1, set2)
distances <- tibble(IPs = intersection_points)
distances$x <- sapply(distances$IPs, return_x_coords)
distances$y <- sapply(distances$IPs, return_y_coords)
distances <- distances %>%
mutate(dist_to_origin = abs(x) + abs(y))
distances <- distances[-1, ]
distances
distances$dist_to_origin %>% min
}a <- "R8,U5,L5,D3"
b <- "U7,R6,D4,L4"
find_min_dist(a,b)## [1] 6c <- "R75,D30,R83,U83,L12,D49,R71,U7,L72"
d <- "U62,R66,U55,R34,D71,R55,D58,R83"
find_min_dist(c,d)## [1] 159find_min_dist(maps[[1]], maps[[2]])## [1] 258It turns out that this circuit is very timing-sensitive; you actually need to minimize the signal delay.
To do this, calculate the number of steps each wire takes to reach each intersection; choose the intersection where the sum of both wires’ steps is lowest. If a wire visits a position on the grid multiple times, use the steps value from the first time it visits that position when calculating the total value of a specific intersection.
The number of steps a wire takes is the total number of grid squares the wire has entered to get to that location, including the intersection being considered. Again consider the example from above:
# ...........
# .+-----+...
# .|.....|...
# .|..+--X-+.
# .|..|..|.|.
# .|.-X--+.|.
# .|..|....|.
# .|.......|.
# .o-------+.
# ...........In the above example, the intersection closest to the central port is reached after 8+5+5+2 = 20 steps by the first wire and 7+6+4+3 = 20 steps by the second wire for a total of 20+20 = 40 steps.
However, the top-right intersection is better: the first wire takes only 8+5+2 = 15 and the second wire takes only 7+6+2 = 15, a total of 15+15 = 30 steps.
Here are the best steps for the extra examples from above:
U62,R66,U55,R34,D71,R55,D58,R83 = 610 steps
U98,R91,D20,R16,D67,R40,U7,R15,U6,R7 = 410 steps
What is the fewest combined steps the wires must take to reach an intersection?
minimum_intersection_distance <- function(text1, text2){
#convert text
map1 <- text1 %>% str_split(pattern = ",") %>% .[[1]]
map2 <- text2 %>% str_split(pattern = ",") %>% .[[1]]
#get corner positions
pos1 <- coord_tracker(map1)
pos2 <- coord_tracker(map2)
#map wire grid
set1 <- make_wire_grid_matrix(pos1)
set2 <- make_wire_grid_matrix(pos2)
#find intersection points
IPs <- intersect(set1, set2) %>% .[-1]
### NEW Work ###
#find connection lengths
min_conn_length_1 <- rep(NA, length(IPs))
min_conn_length_2 <- rep(NA, length(IPs))
for (i in 1:length(IPs)) { #we subtract 1 because the point 0,0 is included in each wire
min_conn_length_1[i] <- min(which(set1 == IPs[i]) ) - 1
min_conn_length_2[i] <- min(which(set2 == IPs[i]) ) - 1
}
IP_df <- cbind(IPs, min_conn_length_1, min_conn_length_2) %>%
as_tibble()
#find total connection lengths
IP_df[, -1] %<>% sapply(as.numeric)
IP_df <- IP_df %>%
mutate(total_wire_length = min_conn_length_1 + min_conn_length_2)
IP_df$total_wire_length %>% min()
}minimum_intersection_distance(a,b)## [1] 30minimum_intersection_distance(c,d)## [1] 610minimum_intersection_distance(maps[[1]], maps[[2]])## [1] 12304Seeing to the setting of the timing in this circuit, we are soon to see Santa safely underway.