Day 3’s problem was an interesting one. We are given two wires and have to find the point where the two wires intersect that’s closest to the origin. As usual, we’ll approach this problem in two steps. First we’ll parse the input. Then’ll we’ll solve the actual problem.
Before we can get to writing our parsing logic, we’ll need to define two types. These are the types we’ll use to represent the parsed input. We’ll have a wire type that represents a full wire. We’ll also have a wireSegment type that represents an individual segment of the wire:
|
1 2 3 4 5 6 7 8 |
type wire struct { segments []*wireSegment } type wireSegment struct { dir byte length int } |
We’ll also define a readInput function that reads the input file and parses the two wires. This is pretty similar to previous readInput functions we’ve written that have parsed a list of numbers. This time, instead of using strconv.Atoi to parse a number, we’ll write our own parseWire function that will take a line and return the wire on it:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
func readInput() (*wire, *wire, error) { fileContents, err := ioutil.ReadFile("input.txt") if err != nil { return nil, nil, errors.WithStack(err) } trimmedContents := strings.Trim(string(fileContents), "\n") wires := []*wire{} for _, line := range strings.Split(trimmedContents, "\n") { w, err := parseWire(line) if err != nil { return nil, nil, err } wires = append(wires, w) } return wires[0], wires[1], nil } |
The parseWire function is pretty similar. Split the line by comma to get the string representation of each segment. Then for each segment, pull out the direction (the first character) and the length of the segment (everything but the first character):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
func parseWire(line string) (*wire, error) { segments := []*wireSegment{} for _, part := range strings.Split(line, ",") { dir := part[0] length, err := strconv.Atoi(part[1:]) if err != nil { return nil, errors.WithStack(err) } segment := &wireSegment{dir, length} segments = append(segments, segment) } return &wire{segments}, nil } |
With our parseInput function complete, we can move onto our main function. Again, our main function will have a similar structure to the other main functions we’ve written so far for the AoC:
|
1 2 3 4 5 6 7 8 9 |
func main() { wire1, wire2, err := readInput() if err != nil { fmt.Printf("got error: %+v", err) return } fmt.Println(solve(wire1, wire2)) } |
Ok. Now that we’ve got our parsing complete, we can start thinking about how to solve the problem. We need to find the intersection point of the two wires that’s closest to the origin. Thinking for a bit, if we had a list of points where the two wires intersected, we could easily determine which point is closest to the origin. Unfortunately, there doesn’t appear to be an easy way to determine the intersection points with the wires represented as a list of segments.
Although, what we can do is convert the wires into a format that’s better for calculating the intersection. We can convert each wire into the set of points the wire goes through. With the two point sets, we can easily intersect the two sets and find the point closest to the origin. Let’s try to implement this strategy!
The first thing we need to do is write a function that converts a wire to a set. To do so, we can start at the origin and trace the path made by each line segment. For a given line segment, we take segment.length steps in the direction segment.dir. We do this for each segment. For every point we hit along the way, we add it to a set of points. The end result looks something like:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
type point struct { row int col int } func wireToSet(w *wire) map[point]bool { result := map[point]bool{} row, col := 0, 0 for _, segment := range w.segments { for i := 0; i < segment.length; i++ { if segment.dir == 'R' { col += 1 } else if segment.dir == 'L' { col -= 1 } else if segment.dir == 'U' { row += 1 } else if segment.dir == 'D' { row -= 1 } result[point{row, col}] = true } } return result } |
With wireToSet we can now write our solve function. We first need to convert our wires into sets of points. Then we can iterate through one of the sets and check if it’s in the other set to see if there’s an intersection at that point. If there is an intersection, we can check if that intersection point is closer than any intersection point we’ve seen before. That way we can find the closest intersection point! We can implement this strategy with just a few lines of code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
func solve(wire1 *wire, wire2 *wire) int { set1 := wireToSet(wire1) set2 := wireToSet(wire2) minDist := math.MaxInt32 for p := range set1 { if _, ok := set2[p]; ok { dist := abs(p.row) + abs(p.col) if dist < minDist { minDist = dist } } } return minDist } func abs(x int) int { if x < 0 { return -x } return x } |
And that’s it for part 1!
For part 2 we have a similar, but slightly different problem. Instead of needing to find the intersection point closest to the origin, we need to find the intersection point that occurs closest to the start of the wires, measured by the sum of the distance to the point from the start of each wire.
The first idea that came to my mind was to iterate through the points in such a way that as soon as we find a point on both wires, we know that that intersection is the intersection closest to the start of the wires. I’m not exactly sure how this idea would work and it doesn’t sound easy to implement so I started to look for other strategies.
It seems kind of necessary to implement some way to iterate through each wire so we can find how far along each wire each point is. Thinking some more, I realized we don’t need to iterate through the wires in any fancy way, the only value we care about is how far each point is along the wire. That gives us an idea of how we can solve this problem.
What we can do is iterate through each wire. This time, instead of constructing a set of points the wire goes through, we construct a map that tells us for each point, how far along the wire that point is. We can construct these maps for each wire, intersect them, and find the point with the lowest sum distance! This requires only a few modifications to our existing code. We can change our wireToSet function to wireToMap. We add a few bits of code to keep track of our current distance along the wire.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
func wireToMap(w *wire) map[point]int { result := map[point]int{} // Also create the dist variable. row, col, dist := 0, 0, 0 for _, segment := range w.segments { for i := 0; i < segment.length; i++ { if segment.dir == 'R' { col += 1 } else if segment.dir == 'L' { col -= 1 } else if segment.dir == 'U' { row += 1 } else if segment.dir == 'D' { row -= 1 } // New code. dist++ if _, ok := result[point{row, col}]; !ok { result[point{row, col}] = dist } } } return result } |
Now that we’re tracking the distance from the start of each wire to each point, we can use the same solve function as before, but now we change our distance function to be the sum of the distance to each point:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
func solve(wire1 *wire, wire2 *wire) int { // wireToSet -> wireToMap. map1 := wireToMap(wire1) map2 := wireToMap(wire2) minDist := math.MaxInt32 for p := range map1 { if _, ok := map2[p]; ok { // changed from dist := abs(p.row) + abs(p.col) dist := map1[p] + map2[p] if dist < minDist { minDist = dist } } } return minDist } |
And that gives us our solution to part 2! I thought this was another great Advent of Code problem. If you want to view the full source code for my solutions, you can find my code on my GitHub.
|
1 |