-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgamato_03.py
133 lines (96 loc) · 4.81 KB
/
gamato_03.py
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
"""
### Day 3: Crossed Wires ###
--- Part One ---
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 Manhattandistance
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, but the lower-left one is closer to the central port: its distance is 3 + 3 = 6.
Here are a few more examples:
R75,D30,R83,U83,L12,D49,R71,U7,L72
U62,R66,U55,R34,D71,R55,D58,R83 = distance 159
R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
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?
--- Part Two ---
It 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:
R75,D30,R83,U83,L12,D49,R71,U7,L72
U62,R66,U55,R34,D71,R55,D58,R83 = 610 steps
R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
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?
"""
from collections import defaultdict
DIRECTION = {'U': 1, 'D': -1, 'L': -1j, 'R': 1j}
def trace_wires(input_data):
# Build a grid as a dictionary
grid = defaultdict(dict)
# Iterate through each wire
for index, wire in enumerate(input_data):
phase = 0
location = 0j
# Take each instruction an generate direction and length of the movement
for movement in wire.split(','):
direction = DIRECTION[movement[0]] # Split the string to get the key in DIRECTION mapping
length = int(movement[1:]) # Split the string to get the length of the movement
# Iterate over the length to store each position it passes through
for _ in range(length):
phase += 1 # Increment the phase, or step
location += direction # Add the direction to the current location
# Store the position and rewrite if it exists already; we only need the point once in the wire.
grid[location].setdefault(index, phase)
return grid
if __name__ == "__main__":
# Generate the grid data
wire_grid = trace_wires(open("input2.txt", 'r').read().splitlines())
closest_distance = min(abs(point.real) + abs(point.imag) for point, vector in wire_grid.items() if len(vector) == 2)
fewest_steps = min(sum(vector.values()) for vector in wire_grid.values() if len(vector) == 2)
print("Part One:", closest_distance, "Part Two:", fewest_steps)