12.md

Day 12

	Part 1	Part 2	Total
Time	25:51	9:48	35:39

Ew, so much nesting.

Part 1

Simple breadth first search. Took me too long to figure out that's what this problem needed. The Matrix class I made came in handy! I need to make it die better for out of bounds values so I don't need to surround things in try blocks. I would also like to add a neighbors method.

Here is a visualization I created of my algorithm running:

from helpers.datagetter import data_in, submit, Matrix

ans = 0
din = data_in(split=True, numbers=False)

mat = Matrix([len(din), len(din[0])], wrap=False)
start, end = [], []

for i in range(len(din)):
    for j in range(len(din[i])):
        if din[i][j] == 'S':
            mat[i, j] = 0
            start = [i, j]
        elif din[i][j] == 'E':
            mat[i, j] = 25
            end = [i, j]
        else:
            mat[i, j] = ord(din[i][j]) - 97

print(mat)

visited = []
queue = [[start]]

while queue:
    path = queue.pop(0)
    node = path[-1]

    if node not in visited:
        for i in range(-1, 2):
            for j in range(-1, 2):
                if abs(i + j) == 1:
                    try:
                        new_path = list(path)
                        new_path.append([node[0] + i, node[1] + j])
                        if mat[node[0] + i, node[1] + j] - mat[node[0], node[1]] <= 1:
                            queue.append(new_path)

                            # Condition to check if the
                            # neighbour node is the goal
                            if [node[0] + i, node[1] + j] == end:
                                print(len(new_path)-1)
                                submit(len(new_path)-1)
                                exit()
                    except:
                        None
        visited.append(node)

Part 2

It took embarrassingly long for me to realize the easy solution for Part 2. Instead of going from S to E, go from E to any a. Some small modifications to my existing code, and we're golden! As you can see, I wrapped it in a function because, yes, I was checking every single a. I initially added an optimization such that it would only check a's that were not surrounded entirely by other a's, but alas...

from helpers.datagetter import data_in, submit, Matrix

ans = 0
din = data_in(split=True, numbers=False)

mat = Matrix([len(din), len(din[0])], wrap=False)
start, end = [], []

for i in range(len(din)):
    for j in range(len(din[i])):
        if din[i][j] == 'S':
            mat[i, j] = 0
            start = [i, j]
        elif din[i][j] == 'E':
            mat[i, j] = 25
            end = [i, j]
        else:
            mat[i, j] = ord(din[i][j]) - 97

def find_lowest_a(start):
    global end, mat
    visited = []
    queue = [[start]]

    while queue:
        path = queue.pop(0)
        node = path[-1]

        if node not in visited:
            for i in range(-1, 2):
                for j in range(-1, 2):
                    if abs(i + j) == 1:
                        try:
                            new_path = list(path)
                            new_path.append([node[0] + i, node[1] + j])
                            if mat[node[0], node[1]] - mat[node[0] + i, node[1] + j] <= 1:
                                queue.append(new_path)

                                if mat[node[0] + i, node[1] + j] == 0:
                                    return len(new_path)-1
                        except:
                            None
            visited.append(node)

ans = find_lowest_a(end)

print(ans)
submit(ans)

Bruteforce solution that skips over bad starting positions.

It only checks `if max(neighbors) != 0 and min(neighbors) <= 1`.

ans = 1000
for pos, item in mat:
    try:
        if item == 0:
            neighbors = []
            for i in range(-1, 2):
                for j in range(-1, 2):
                    if abs(i + j) == 1:
                        try:
                            neighbors.append(mat[pos[0]+i, pos[1]+j])
                        except:
                            None
            if max(neighbors) != 0 and min(neighbors) <= 1:
                ans = min(ans, find_lowest_a(pos))
                print(pos, ans)
    except:
        None

print(ans)