dirs = [[-2, 0, 2], [0, 2, 3], [2, 0, 0], [0, -2, 1]]
def arrayMath(a, op, b):
    o = []
    if op == '+':
        op = lambda x, y: x + y
    elif op == '-':
        op = lambda x, y: x - y
    elif op == '/':
        op = lambda x, y: x / y
    elif op == '*':
        op = lambda x, y: x * y
    if len(a) > len(b):
        for i in range(0, len(b)):
            o.append(op(a[i], b[i]))
    else:
        for i in range(0, len(a)):
            o.append(op(a[i], b[i]))
    return o
def getSpace(pos, m):
    pos = [int(pos[0]), int(pos[1])]
    if 0 > pos[0] or pos[0] >= len(m) or 0 > pos[1] or pos[1] >= len(m[0]):
        return '?'
    return m[pos[0]][pos[1]]
def setSpace(pos, c, m):
    m[int(pos[0])][int(pos[1])] = c
def display(m):
    for row in m:
        for cel in row:
            print(cel, end='')
        print()
def getoption(pos, m):
    for d in dirs:
        if getSpace(arrayMath(pos, lambda x, y: x + (y / 2), d), m) == ' ' and getSpace(arrayMath(pos, '+', d), m) == ' ':
            #print('option', d)
            return d
def solveMaze(maze):
    m = []
    a = 0
    path = []
    for r in maze.split('\n'):
        m.append([])
        b = 0
        for c in r:
            if c == 'S':
                m[a].append('S')
                pos = [a, b]
                start = [a, b]
            elif c == 'E':
                m[a].append(' ')
                end = [a, b]
            elif c == ' ':
                m[a].append(c)
            else:
                m[a].append('#')
            b += 1
        a += 1
    while pos != end:
        #print('pos', pos, 'end', end, 'path', path)
        #display(m)
        d = getoption(pos, m)
        if d:
            path.append(arrayMath(pos, lambda x, y: x + (y / 2), d))
            pos = arrayMath(pos, '+', d)
            path.append(pos)
            setSpace(pos, d[2], m)
        else:
            #print('backtracking...')
            path.pop()
            path.pop()
            pos = arrayMath(pos, '+', dirs[getSpace(pos, m)])
    s = ''
    a = 0
    for row in m:
        b = 0
        for c in row:
            if [a, b] == start:
                s = s + 'S'
            elif [a, b] == end:
                s = s + 'E'
            elif [a, b] in path:
                s = s + 'o'
            elif c in ['#', ' ']:
                s = s + c
            else:
                s = s + ' '
            b += 1
        s = s + '\n'
        a += 1
    return s
###########TEST##########
if __name__ == '__main__':
    import maze_maker as mm
    import time
    print('Creating Maze...')
    a = time.time()
    maze = mm.makeMaze(20, 60)
    b = time.time()
    print(maze)
    print('Solving Maze...')
    c = time.time()
    solved = solveMaze(maze)
    d = time.time()
    print(solved)
    print('Createing the maze took', b-a, 'sec. Solving the maze took', d-c, 'sec.')