Challenge 17

In [71]:

    

passcode = 'pvhmgsws'


    

In [72]:

    

opencodes = 'bcdef'
sorted_steps = ['U', 'D', 'L', 'R']
dirs = {'U' : 'D', 'D': 'U', 'L': 'R', 'R': 'L'}
vectors = {'U': (0,-1), 'D': (0,1), 'L': (-1,0), 'R': (1,0)}
print(vectors)


    

    




{'R': (1, 0), 'L': (-1, 0), 'U': (0, -1), 'D': (0, 1)}

In [87]:

    

import hashlib

class Node(object):
    
    def __init__(self, pos, path, traps):
        self.pos = pos
        self.path = path
        self.traps = traps
        self.parent = None
        self.children = []
    
    def add_child(self, node):
        self.children.append(node)
    
    def add_parent(self, node):
        self.parent = node

        
def interpret_hash(passcode, path):
    mystr = passcode + path
    hsh = hashlib.md5(mystr.encode('utf-8')).hexdigest()
    opens = {item[1]: (hsh[item[0]] in opencodes) for item in enumerate(sorted_steps)}
    return opens


def pathsearch(pos, goal, passcode, shortest=True):
    node = Node(pos, '', [])
    pending = []
    pending.append(node)
    results = []
    while len(pending) > 0:
        node = pending.pop()
        if node.pos == goal:
            results.append(node.path)
        else:
            open_doors = interpret_hash(passcode, node.path)
            trap = True
            for step in vectors:
                if step not in node.traps:
                    if open_doors[step]:
                        new_pos = (node.pos[0] + vectors[step][0], node.pos[1] + vectors[step][1]) 
                        if (0 <= new_pos[0] <= 3) and (0 <= new_pos[1] <= 3):
                            trap = False
                            child = Node(new_pos, node.path + step, [])
                            child.add_parent(node)
                            pending.append(child)
    if len(results) > 0:
        results = sorted(results, key=lambda x: len(x), reverse=shortest)
        return results.pop()


    

In [88]:

    

pathsearch((0,0), (1,0), 'hijkl')


    

    
Out[88]:





'DUR'

In [89]:

    

pathsearch((0,0), (3,3), 'ihgpwlah')


    

    
Out[89]:





'DDRRRD'

In [82]:

    

pathsearch((0,0), (3,3), 'kglvqrro')


    

    
Out[82]:





'DDUDRLRRUDRD'

In [91]:

    

pathsearch((0,0), (3,3), 'ulqzkmiv')


    

    
Out[91]:





'DRURDRUDDLLDLUURRDULRLDUUDDDRR'

In [92]:

    

p = pathsearch((0,0), (3,3), passcode)
print(p)
len(p)


    

    




DRRDRLDURD






    
Out[92]:





10

In [93]:

    

p = pathsearch((0,0), (3,3), passcode, shortest=False)
print(p)
len(p)


    

    




DRRDRLDURLLRURLDDULDULDURUUDRLRLRDULLRDUURDULDUDDURLRLLRLDRUULRLRLRDRULLRDUDDDUULURDRRLDDLLUDRURLRUURLDDUDLURDUULRDUDURDDLRLLUDURRLUDRULDRUDDLLLRLRUDRLRRUULRLLDURDLLRLRDUDLURURLDRURDLUDRDLUULDRDDLRUULRDUULRDLDLDRLUUURRRLDDULDLUURLRLRLDRDRLULURDDRUDURUDULLRLRDRUDDLRLLDLRURLDRLURDUUDLUDDLRUULRRULDLURRRLDRLUDLDLRLRLRDUUDDLRLUURDDRUDLURRLRULRDLLLRUURRDLDDULUURDLRLDDURUDURLDULUDLDUDUUDRUDRUDULRDDLLRURRLRDLLDULRURLDRURLUDULRLDRULDDLRDRURUDLRUULRDDLRLUDRLUDDUULRDUDLDUUDRULDRUDURLULRDDRULDLLRUDDUUDDURLULDURRDRLDULUDLRLDURULRRDRLLLDUUDURRDDLRULDUUDUURDDLRDUDUULDUDDUURLRURDLULDRDDUDUUDLUDLRUDDUULDRRLUUDDRRULDDURUDULURDDD






    
Out[93]:





618