Good grief.
| Part 1 | Part 2 | Total | |
|---|---|---|---|
| Time | 33:30 | 1:28:15 | 2:01:45 |
Proud of my Part 1 time, and coming up with the valid adjacency matrix. I also got to use my Matrix class for the first time this year! Helpers for getting neighbors.
I'll be honest, when working on the problem, I didn't have the code for figuring out what S is supposed to be until after. I just looked at it and replaced it manually.
Oh then I saw TJThePiGuy from our NJIT ACM group had completed it in 20:50!! Yeah, it's not too bad of a problem, but it took me so long to type it out!
from helpers.datagetter import aocd_data_in
from helpers.matrix import Matrix
din, aocd_submit = aocd_data_in(split=True, numbers=False)
matrix = Matrix([len(din), len(din[0])], " ")
start = []
for i in range(len(din)):
for j in range(len(din[i])):
c = din[i][j]
if c not in "-|F7JLS":
continue
if c == "S":
start = [i, j]
matrix.set([i, j], c)
connections = {
"-": ["", "-J7", "", "-LF"],
"|": ["|F7", "", "|LJ", ""],
"F": ["", "-J7", "|LJ", ""],
"J": ["|F7", "", "", "-LF"],
"7": ["", "", "|LJ", "-LF"],
"L": ["|F7", "-J7", "", ""]
}
for check in connections.keys():
match = 0
for neighbor, pos in matrix.neighbors(start):
i = pos[0] - start[0]
j = pos[1] - start[1]
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
if neighbor in connections[check][dirs.index([i, j])]:
match += 1
if match == 2:
matrix.set(start, check)
break
visit = [start]
visited = []
while visit:
check = visit.pop(0)
current = matrix.get(check)
visited.append(check)
for neighbor, pos in matrix.neighbors(check):
if pos in visited:
continue
i = pos[0] - check[0]
j = pos[1] - check[1]
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
if neighbor in connections[current][dirs.index([i, j])]:
visit.append(pos)
ans = len(visited) // 2
aocd_submit(ans)I knew what to do here right from the start. Google tells me my strategy is called the Jordan Curve Theorem. The tricky part was figuring out what counted as crossing the line.
I started out by checking each non-path space and moving to the right to see how many times it crossed. The issue is that sometimes that "ray" is tangential to the side of the shape. For example, passing through F---7 is not an intersection but F---J is. After much troubleshooting, I ended up doing it the way I should have from the start and just wrote out all the options.
The way that code looks is, uh, disgusting. I wish I had time for a Part Three tonight for some refactoring, but I don't. Maybe some other time.
Oh, also I know that I don't need to compute the intersections for each non-path element. I could just start at the beginning of a line and mark in-or-out spots as I go, scanning and finding odd-and-even numbers of intersections. But I didn't do that, and it ran in 20 seconds, so I was not complaining at the time.
from helpers.datagetter import aocd_data_in
from helpers.matrix import Matrix
din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0
matrix = Matrix([len(din), len(din[0])], " ")
start = []
for i in range(len(din)):
for j in range(len(din[i])):
c = din[i][j]
if c not in "-|F7JLS":
continue
if c == "S":
start = [i, j]
matrix.set([i, j], c)
connections = {
"-": ["", "-J7", "", "-LF"],
"|": ["|F7", "", "|LJ", ""],
"F": ["", "-J7", "|LJ", ""],
"J": ["|F7", "", "", "-LF"],
"7": ["", "", "|LJ", "-LF"],
"L": ["|F7", "-J7", "", ""]
}
for check in connections.keys():
match = 0
for neighbor, pos in matrix.neighbors(start):
i = pos[0] - start[0]
j = pos[1] - start[1]
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
if neighbor in connections[check][dirs.index([i, j])]:
match += 1
if match == 2:
matrix.set(start, check)
break
visit = [start]
visited = []
while visit:
check = visit.pop(0)
current = matrix.get(check)
visited.append(check)
for neighbor, pos in matrix.neighbors(check):
if pos in visited:
continue
i = pos[0] - check[0]
j = pos[1] - check[1]
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
if neighbor in connections[current][dirs.index([i, j])]:
visit.append(pos)
for i in range(len(din)):
for j in range(len(din[i])):
count = 0
if [i, j] not in visited:
pipes = []
for k in range(j + 1, len(din[0])):
if [i, k] in visited and matrix.get([i, k]) != "-":
pipes.append(matrix.get([i, k]))
k = 0
while k < len(pipes):
if pipes[k] == "|":
k += 1
count += 1
elif pipes[k] == "F" and pipes[k+1] == "7":
k += 2
elif pipes[k] == "L" and pipes[k+1] == "J":
k += 2
elif pipes[k] == "F" and pipes[k + 1] == "J":
count += 1
k += 2
elif pipes[k] == "L" and pipes[k + 1] == "7":
count += 1
k += 2
else:
count += 1
k += 1
if count % 2 == 1:
matrix.set([i, j], "I")
ans += 1
aocd_submit(ans)Optimized version, checking inside vs. outside per line instead of per non-line point. Runs about 10x faster. The delay now seems to be mostly in the path following stage, and I don't know why that takes so long - I think my Matrix helper is slow.
from helpers.datagetter import aocd_data_in
from helpers.matrix import Matrix
din, aocd_submit = aocd_data_in(split=True, numbers=False)
ans = 0
matrix = Matrix([len(din), len(din[0])], " ")
start = []
for i in range(len(din)):
for j in range(len(din[i])):
c = din[i][j]
if c not in "-|F7JLS":
continue
if c == "S":
start = [i, j]
matrix.set([i, j], c)
connections = {
"-": ["", "-J7", "", "-LF"],
"|": ["|F7", "", "|LJ", ""],
"F": ["", "-J7", "|LJ", ""],
"J": ["|F7", "", "", "-LF"],
"7": ["", "", "|LJ", "-LF"],
"L": ["|F7", "-J7", "", ""]
}
for check in connections.keys():
match = 0
for neighbor, pos in matrix.neighbors(start):
i = pos[0] - start[0]
j = pos[1] - start[1]
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
if neighbor in connections[check][dirs.index([i, j])]:
match += 1
if match == 2:
matrix.set(start, check)
break
visit = [start]
visited = []
while visit:
check = visit.pop(0)
current = matrix.get(check)
visited.append(check)
for neighbor, pos in matrix.neighbors(check):
if pos in visited:
continue
i = pos[0] - check[0]
j = pos[1] - check[1]
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
if neighbor in connections[current][dirs.index([i, j])]:
visit.append(pos)
for i in range(len(din)):
last = ""
count = 0
for j in range(len(din[i])):
if [i, j] not in visited:
if count % 2 == 1:
ans += 1
else:
pipe = matrix.get([i, j])
if pipe == "|":
count += 1
elif pipe == "7" and last == "L":
count += 1
elif pipe == "J" and last == "F":
count += 1
if pipe != "-":
last = pipe
aocd_submit(ans)