from hashlib import md5
from collections import deque
salt = bytearray(b"mmsxrhfx")
openvalues = "bcdef"

def opendoors(s):
    x = s.count("R") - s.count("L")
    y = s.count("D") - s.count("U")
    if y == 3 and x == 3:
        return None, True
    h = md5(salt + str.encode(s)).hexdigest()[:4]
    opendoors = []
    if y != 0 and h[0] in openvalues:
        opendoors.append("U")
    if y != 3 and h[1] in openvalues:
        opendoors.append("D")
    if x != 0 and h[2] in openvalues:
        opendoors.append("L")
    if x != 3 and h[3] in openvalues:
        opendoors.append("R")
    return opendoors, False

queue = deque([""])
while queue:
    path = queue.pop()
    doors, foundVault = opendoors(path)
    if foundVault:
        print(len(path), path)
    if not doors:
        continue
    for door in doors:
        queue.appendleft(path+door)

import numpy as np
import matplotlib.pyplot as plt

# Vectorizing allows us to operate on NumPy arrays
is_wall = np.vectorize(lambda y, x: bin(x*x + 3*x +2*x*y + y + y*y + 1362).count("1") % 2 == 1)

max_pos = 70
Y, X = np.mgrid[0:max_pos, 0:max_pos]
wall = np.ones((max_pos+2, max_pos+2), dtype=bool)
wall[1:-1, 1:-1] = is_wall(Y, X)

from scipy.sparse import lil_matrix

# Map from coordinate to index in graph matrix
def getnode(y, x):
    return wall.shape[1]*y + x

# Map from index in graph matrix to coordinate
def getpos(node):
    return divmod(node, wall.shape[1])

graph = lil_matrix(((max_pos+2)**2, (max_pos+2)**2))
for x in range(1, max_pos+1):
    for y in range(1, max_pos+1):
        if wall[y,x]:
            continue
        if not wall[y+1,x]:
            graph[getnode(y,x), getnode(y+1,x)] = 1
        if not wall[y-1,x]:
            graph[getnode(y,x), getnode(y-1,x)] = 1
        if not wall[y,x+1]:
            graph[getnode(y,x), getnode(y,x+1)] = 1
        if not wall[y,x-1]:
            graph[getnode(y,x), getnode(y,x-1)] = 1
graph = graph.tocsr()

import scipy.sparse.csgraph
targetx = 32
targety = 40
path_length, predecessor = scipy.sparse.csgraph.shortest_path(graph, return_predecessors=True)
print(path_length[getnode(2,2), getnode(targety,targetx)])

dist = scipy.sparse.csgraph.floyd_warshall(graph)
nodes = np.where(dist[getnode(2,2),:] <= 50)[0]
print("Can reach", len(nodes), "distinct nodes")