Over the holidays I got busy with a lot of things (like getting ready to get out the Army) that I didn’t spend the time I wanted to to write about the other days that I solved with Advent of Code. So, here is day 3.
— Day 3: Crossed Wires —
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:
- 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
Part 1
What is the Manhattan distance from the central port to the closest intersection?
So pondered how to tackle this problem for a little while. When I looked at the input that I got, we were talking about some very large numbers (900+). I decided to go ahead and start easy using the example directions that were given for my development work.
I eventually decided that really the only way to do this was going to be through the use of a grid that would track both wires as the wound their way through the course. My basic idea became this:
- Build a grid that was big enough to hold the entire flow of both wires. I decided to do this using a list of lists. During the initial build testing, this was easy (all of the numbers were less than 100) but once it came to do it for real this was a lot more of a challenge then I though (more to follow).
- Start in the center of the grid and just put an arbitrary value in it to mark it as the start (I picked the value 99)
- Load the first instruction and decode it into first what direction we needed to move, and then the number of steps.
- Cycle across the grid each and every strep
- As I cycled through each step, I would check and see if there was a value already in that box, check it. If it had the number for the current wire, then just ignore it. If it had the value of another wire, change the value to 100 (to indicate an intersection). If there was no value, put in the number of the wire.
- Once all of the wires were mapped out, cycle through the entire grid again, and calculate the manhattan distance for each spot where there was a value of 100 and find the lowest.
rows, cols = (11000, 10000)
startrow = 3100
startcolumn = 2700
wirecount = 1
def getNewCellValue (currentValue, wirecount):
if currentValue == 0:
return wirecount
elif currentValue == wirecount:
return wirecount
elif currentValue == 99:
return 99
else:
return 100
#Intialize Array
arr = [[0 for i in range(cols)] for j in range(rows)]
#Set Start
arr[startrow][startcolumn] = 99
input = open("directions.txt", "r")
wire = input.readline()
while wire:
# print(wire)
steps = wire.split(",")
#Reset to beginning
r = startrow
c = startcolumn
for step in steps:
print(step)
direction = step[0]
count = int(step[1:])
if direction == "R":
for column in range (c+1, c+count+1, 1):
arr[r][column] = getNewCellValue(arr[r][column] ,wirecount)
c = column
print("row: " + str(r) + " col: " + str(c))
elif direction == "L":
for column in range (c-1, c-count-1, -1):
arr[r][column] = getNewCellValue(arr[r][column] ,wirecount)
c = column
print("row: " + str(r) + " col: " + str(c))
elif direction == "U":
for row in range (r-1, r-count-1, -1):
arr[row][c] = getNewCellValue(arr[row][c] ,wirecount)
r = row
print("row: " + str(r) + " col: " + str(c))
else:
for row in range (r+1, r+count+1, 1):
arr[row][c] = getNewCellValue(arr[row][c] ,wirecount)
r = row
print("row: " + str(r) + " col: " + str(c))
wirecount += 1
wire = input.readline()
currentDistance = 1000000000
for r in range (0, rows):
for c in range (0, cols):
if arr[r][c] == 100:
distance = abs(startrow - r) + abs(startcolumn - c)
if distance < currentDistance:
currentDistance = distance
print(currentDistance)
Above is the code that I ended up going with. I had a very hard time finding a grid that was big enough to hold everything. I started out with 1000 x 1000 but I ran out of room. I went through several more iterations and eventually went to like 100,000 x 100,000 and then started to deal with memory problems. So if you notice on line 33, the line where it prints the “step”, I had it print out each instruction as it went through so when it ran out of room on the grid, I knew what the current instruction was so that I could increase the grid size appropriately. It took a few trials but I eventually settled on 11,000 x 10,000.
Part 2
What is the fewest combined steps the wires must take to reach an intersection?
OK, so I thought that this would be a relatively easy change. Boy was I wrong. My original plan had been to modify the grid. Now within each cell in my list of lists, I was going to add in two more lists (one for each wire) and within the list, record the wire number and the step count. This was going to be a pretty minor modification.
When I made the change and ran it, I very quickly ran into memory problems. I eventually started to do some research to see just how much memory a list took. I eventually found this post in the python documentation. It says (among a lot of other great information) that an empty list is 72 bytes. So doing some rough beer math, I start off with 1 big list with 10,000 sublists within it to build the initial grid. But then each item within all of those lists has two more lists giving me an equation of 72 bytes * 10,000 * ( 2 * 11,000) = 15,840,000,000 bytes or about 15 GB. That was without adding any data to the lists. Obviously that wasn’t going to work.
So because I couldn’t do this the way I wanted to, I went back to what had already worked with my single grid. I thought for a very long time about how to do this, and eventually came up with a solution that I hate (because it doesn’t scale) but at this point (this was a day later) I was willing to settle for something that worked. Here’s the plan:
- Build the grid as before
- Start in the center and decode as before
- Now if we are on the first wire, instead of recording the wire number, record the step count.
- If it was the second wire and the field was empty, record a super huge number (1,000,000,000) just to make it out of play. If there is a value the already, take that value, and add the step count to give the current distance.
- If the new value is smaller than the current smallest value, record it.
rows, cols = (11000, 10000)
startrow = 3100
startcolumn = 2700
wirecount = 1
def getNewCellValue (currentValue, wirecount, stepCount):
if wirecount == 1:
if currentValue == 0:
return stepCount
elif currentValue == -1:
return -1
else:
return currentValue
else:
if currentValue > 0:
return currentValue + stepCount
else:
return 1000000000
#Intialize Array
arr = [[0 for i in range(cols)] for j in range(rows)]
#Set Start
arr[startrow][startcolumn] = -1
input = open("directions.txt", "r")
wire = input.readline()
currentDistance = 1000000000
while wire:
# print(wire)
steps = wire.split(",")
#Reset to beginning
r = startrow
c = startcolumn
stepCount = 1
for step in steps:
print(step)
direction = step[0]
count = int(step[1:])
if direction == "R":
for column in range (c+1, c+count+1, 1):
value = getNewCellValue(arr[r][column] ,wirecount, stepCount)
if wirecount == 1:
arr[r][column] = value
else:
if value < currentDistance:
currentDistance = value
stepCount += 1
c = column
print("row: " + str(r) + " col: " + str(c))
elif direction == "L":
for column in range (c-1, c-count-1, -1):
value = getNewCellValue(arr[r][column] ,wirecount, stepCount)
if wirecount == 1:
arr[r][column] = value
else:
if value < currentDistance:
currentDistance = value
stepCount += 1
c = column
print("row: " + str(r) + " col: " + str(c))
elif direction == "U":
for row in range (r-1, r-count-1, -1):
value = getNewCellValue(arr[row][c] ,wirecount, stepCount)
if wirecount == 1:
arr[row][c] = value
else:
if value < currentDistance:
currentDistance = value
stepCount += 1
r = row
print("row: " + str(r) + " col: " + str(c))
else:
for row in range (r+1, r+count+1, 1):
value = getNewCellValue(arr[row][c] ,wirecount, stepCount)
if wirecount == 1:
arr[row][c] = value
else:
if value < currentDistance:
currentDistance = value
stepCount += 1
r = row
print("row: " + str(r) + " col: " + str(c))
wirecount += 1
wire = input.readline()
print(currentDistance)