Challenge 13

Challenge 13.1



In [114]:

    
myinput = 1350



In [115]:

    
bits = lambda a: a % 2 + bits(a // 2) if a > 0 else 0
wall = lambda x, y, k: bits(x*x + 3*x + 2*x*y + y + y*y + k) % 2



In [116]:

    
from operator import add

directions = [(0,1), (0,-1), (1,0), (-1,0)]

def minsteps(k, start, final):
    queue = [(0, start)]
    wallist = set()
    visited = set()
    while len(queue) > 0:
        depth, state = queue.pop(0)
        visited.add(state)
        if state == final:
            return depth
        else:
            for arrow in directions:
                new_pos = tuple(map(add, state, arrow))
                if (new_pos[0] >= 0) and (new_pos[1] >= 0):
                    if (wall(new_pos[0], new_pos[1], k) == 0) and new_pos not in wallist:
                        if new_pos not in visited:
                            queue.append((depth + 1, new_pos))
                    else:
                        wallist.add(new_pos)



In [117]:

    
minsteps(myinput, (1,1), (31,39))









    Out[117]:





92

Challenge 13.2

Let's tune a bit the previous code...



In [118]:

    
def visited(k, start, steps):
    queue = [(0, start)]
    wallist = set()
    visited = set()
    while len(queue) > 0:
        depth, state = queue.pop(0)
        visited.add(state)
        if depth > steps:
            return len(visited)-1
        else:
            for arrow in directions:
                new_pos = tuple(map(add, state, arrow))
                if (new_pos[0] >= 0) and (new_pos[1] >= 0):
                    if (wall(new_pos[0], new_pos[1], k) == 0) and new_pos not in wallist:
                        if new_pos not in visited:
                            queue.append((depth + 1, new_pos))
                    else:
                        wallist.add(new_pos)



In [119]:

    
visited(myinput, (1,1), 50)









    Out[119]:





124