import sys
sys.path.append("../common")
import aoc
from copy import deepcopy

data = list(aoc.data)

def get_map(p):
    return vmap[p[1] + spos[1]][p[0] + spos[0]]

def set_map(p, c):
    global vmap, spos
    vmap[p[1] + spos[1]][p[0] + spos[0]] = c

def new_pos(p, c):
    p = p[:]
    if c == "N":
        p[1] -= 2
    elif c == "S":
        p[1] += 2
    elif c == "W":
        p[0] -= 2
    elif c == "E":
        p[0] += 2
    return p

def calc_pos(stack):
    p = [0,0]
    for c in stack:
        p = new_pos(p, c)
    return p

xmin = 0
xmax = 0
ymin = 0
ymax = 0

def check_size(stack):
    global xmin, xmax, ymin, ymax

    p = calc_pos(stack)
    if p[0] < xmin:
        xmin = p[0]
    if p[0] > xmax:
        xmax = p[0]
    if p[1] < ymin:
        ymin = p[1]
    if p[1] > ymax:
        ymax = p[1]

def draw_route(stack):
    p = calc_pos(stack)
    set_map(p, ".")
    np = new_pos(p, stack[-1])
    cp = [0,0]
    cp[0] = p[0] + int((p[0] - np[0])/2)
    cp[1] = p[1] + int((p[1] - np[1])/2)
    set_map(cp, "+")

def iter_regex(func):
    stacklens = [0]
    stack = []
    for i in range(1, len(data)-1):
        c = data[i]
        if c == "(":
            stacklens.append(0)
        elif c == "|":
            for i in range(stacklens[-1]):
                stack.pop()
            stacklens[-1] = 0
        elif c == ")":
            for i in range(stacklens[-1]):
                stack.pop()
            stacklens.pop()
        else:
            stack.append(c)
            stacklens[-1] += 1
            func(stack)

def fwriteMap():
    f = open("output", "w+")
    for y in range(len(vmap)):
        f.write("".join([str(v) for v in vmap[y]]) + "\n")
    f.close()

mshape = None
spos = None
vmap = None

def genMap():
    global vmap, mshape, spos

    iter_regex(check_size)
    xdif = xmax - xmin + 2
    ydif = ymax - ymin + 2

    spos = (-xmin+1, -ymin+1)
    mshape = (xdif, ydif)

    vmap = [["#" for x in range(xdif+1)] for y in range(ydif+1)]
    vmap[spos[1]][spos[0]] = "X"

    iter_regex(draw_route)


adjacent = ((-1, 0), (0, -1), (1, 0), (0, 1))

def gen_countmap(sp):
    countmap = dict()
    next = dict()
    next[(sp[0], sp[1])] = 0
    counter = 0
    steps = list()
    while len(next) > 0 and len(steps) == 0: # first steps available will be shortest
        countmap = {**countmap, **next} # merge dictionaries
        counter += 1
        temp = dict()
        for n in next:
            for dir in adjacent:
                nx = n[0]+dir[0]
                ny = n[1]+dir[1]
                if get_map((nx, ny)) != "#" and (nx, ny) not in countmap and (nx, ny) not in temp:
                    temp[(nx,ny)] = counter
        next = temp
    return countmap

def next_step(cmap, p):
    # adjacent squares
    npos = [[p[0] + dir[0], p[1] + dir[1]] for dir in adjacent]

    # steps and dist
    steps = [[np[0], np[1], cmap[np[0], np[1]]] for np in npos if (np[0], np[1]) in cmap]

    if len(steps) == 0:
        return None
    else:
        return sorted(steps, key = lambda x: x[2])[0] #closest

genMap()

def solve1(args):
    cmap = gen_countmap((0,0))
    ipos = sorted(cmap, key = lambda x : cmap[x])[-1]
    return int(cmap[ipos]/2)

def solve2(args):
    cmap = gen_countmap((0,0))
    count = len([v for v in cmap if int(cmap[v]/2) >= 1000 and get_map(v) == "."])
    return count

aoc.run(solve1, solve2, sols=[4121, 8636])