import math
import os
import random
import sys

MAX_CELLS = 500

STATIC_CASES = [
'''
#######
#a.S.A#
#######
''','''
###
#S#
###
''','''
########
#..AB..#
#..##..#
#Sb##a.#
########
'''
    ]

CASE = 0
DEST = os.path.join(os.getcwd(), '../data/secret')

def next_file(sub_case=None, short_desc=None, long_desc=None):
    global CASE
    if not sub_case:
        CASE += 1
    basename = os.path.join(DEST, '%02d' % CASE)
    if sub_case is not None:
        basename += chr(ord('a')+sub_case)
    if short_desc is not None:
        basename += '-' + short_desc
    if long_desc is not None:
        with open(basename+'.desc', 'w') as desc_out:
            desc_out.write(long_desc)
    return open(basename+'.in', 'w')

def flip(grid):
    h = len(grid)
    w = len(grid[0])
    return [[grid[r][c] for r in range(h)] for c in range(w)]

def rotate(grid):
    h = len(grid)
    w = len(grid[0])
    return [[grid[h-1-r][c] for r in range(h)] for c in range(w)]
    

def save_case(grid, sub_cases=8, short_desc=None, long_desc=None, shuffle_adj_list=True):
    h = len(grid)
    w = len(grid[0])
    sys.stderr.write('save case %d %d\n' % (h, w))
    for subcase in range(sub_cases):
        h = len(grid)
        w = len(grid[0])
        f = next_file(subcase if sub_cases > 1 else None, short_desc, long_desc)
        f.write('%d %d\n' % (h, w))
        for row in grid:
            f.write('%s\n' % ''.join(row))
        f.close()
        if subcase == 3:
            grid = flip(grid)
        else:
            grid = rotate(grid)


def check_case(maze):
    special_pos = {}
    H = len(maze)
    W = len(maze[0])
    
    for r in range(H):
        for c in range(W):
            x = maze[r][c]
            if x not in '#.SAaBb':
                return False
            if x in 'SAaBb' and x in special_pos:
                return False
            special_pos[x] = (r, c)

    if 'S' not in special_pos: return False
    if ('A' in special_pos) != ('a' in special_pos): return False
    if ('B' in special_pos) != ('b' in special_pos): return False

    # Check for wall boundary
    for i in range(H):
        if maze[i][0] != '#': return False
        if maze[i][W-1] != '#': return False
    for i in range(W):
        if maze[0][i] != '#': return False
        if maze[H-1][i] != '#': return False

    def reach_all(start, traps):
        (sr, sc) = start
        Q = [(sr, sc)]
        seen = set(Q)
        while Q:
            (r, c) = Q.pop()
            for (nr, nc) in [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]:
                if maze[nr][nc] == '#': continue
                if (nr, nc) in traps:
                    seen.add((nr, nc))
                    (nr, nc) = traps[(nr, nc)]
                if (nr, nc) not in seen:
                    seen.add((nr, nc))
                    Q.append((nr, nc))
        for r in range(H):
            for c in range(W):
                if maze[r][c] != '#' and (r, c) not in seen:
                    return False
        return len(seen) <= MAX_CELLS
    
    traps = {}
    if 'A' in special_pos:
        traps[special_pos['A']] = special_pos['a']
    if 'B' in special_pos:
        traps[special_pos['B']] = special_pos['b']

    # Reach everything from starting point?
    if not reach_all(special_pos['S'], traps): return False

    # Reach everything from endpoint of trap a?
    if 'a' in special_pos:
        if not reach_all(special_pos['a'], traps): return False

    # Reach everything from endpoint of trap b?
    if 'b' in special_pos:
        if not reach_all(special_pos['b'], traps): return False

    # Reach everything from starting point if traps are removed?
    if not reach_all(special_pos['S'], {}): return False

    return True


def random_grid(w, h, wall_prob, traps=2, MAX_TRIES=1000):
    tries = 0
    print 'gen random %dx%d (wall-prob %f, %d traps)' % (h, w, wall_prob, traps)
    while tries < MAX_TRIES:
        tries += 1
        grid = [['#']*w for _ in range(h)]
        for r in range(1,h-1):
            for c in range(1,w-1):
                grid[r][c] = '.#'[random.random() < wall_prob]

        grid[random.randint(1, h-2)][random.randint(1, w-2)] = 'S'
        for i in range(traps):
            grid[random.randint(1, h-2)][random.randint(1, w-2)] = chr(ord('A')+i)
            grid[random.randint(1, h-2)][random.randint(1, w-2)] = chr(ord('a')+i)
        if check_case(grid):
            save_case(grid, sub_cases=1, short_desc='random')
            return True
    return False

def line(L, traps):
    w = L+2
    h = 3
    while True:
        grid = [['#']*w for _ in range(h)]
        for i in range(1, h-1):
            for j in range(1, w-1):
                grid[i][j] = '.'
        grid[random.randint(1, h-2)][random.randint(1, w-2)] = 'S'
        for i in range(traps):
            grid[random.randint(1, h-2)][random.randint(1, w-2)] = chr(ord('A')+i)
            grid[random.randint(1, h-2)][random.randint(1, w-2)] = chr(ord('a')+i)
        if check_case(grid):
            save_case(grid, sub_cases=2, short_desc='line')
            break
    
def plus(cells, traps):
    L = (cells-1)/4
    h = 2*L+3
    w = 2*L+3
    grid = [['#']*w for _ in range(h)]

    mr = 1 + L
    mc = 1 + L
    grid[mr][mc] = 'S'
    for i in range(L):
        grid[mr-1-i][mc] = '.'
        grid[mr+1+i][mc] = '.'
        grid[mr][mc-1-i] = '.'
        grid[mr][mc+1+i] = '.'

    for (i, ((sr, sc, dr, dc))) in enumerate(traps):
        grid[mr+L*sr][mc+L*sc] = chr(ord('A')+i)
        grid[mr+L*dr][mc+L*dc] = chr(ord('a')+i)

    save_case(grid, sub_cases=4 if traps else 1, short_desc='plus')

def spiral(cells, direction=1):
    used = 1
    nxt = 1
    (r, c) = (0, 0)
    (dr, dc) = (1, 0)
    min_r = min_c = max_r = max_c = 0
    while used < cells:
        steps = min(cells-used, nxt)
        nxt += 1
        used += steps
        r += steps*dr
        c += steps*dc
        min_r = min(min_r, r)
        max_r = max(max_r, r)
        min_c = min(min_c, c)
        max_c = max(max_c, c)
        (dr, dc) = (direction*dc, -direction*dr)

    h = max_r-min_r + 3
    w = max_c-min_c + 3
    grid = [['#']*w for _ in range(h)]

    r = -min_r+1
    c = -min_c+1
    (dr, dc) = (1, 0)
    used = 1
    nxt = 1
    grid[r][c] = 'A'
    while used < cells:
        steps = min(cells-used, nxt)
        nxt += 1
        used += steps
        for _ in range(steps):
            r += dr
            c += dc
            grid[r][c] = '.'
        (dr, dc) = (direction*dc, -direction*dr)
    grid[r][c] = 'a'

    while True:
        r = random.randint(1, h-2)
        c = random.randint(1, w-2)
        if grid[r][c] == '.':
            grid[r][c] = 'S'
            break

    save_case(grid, sub_cases=4, short_desc='spiral')
    
    
def same_surroundings1(cells):
    rh = int(math.sqrt((cells-2)/2.0))
    rw = rh
    while 2*rh*(rw+1)+2 <= cells: rw += 1

    # outer shell
    h = rh + 2 
    w = 2*rw + 2 + 2
    
    grid = [['#']*w for _ in range(h)]

    for r in range(rh):
        for c in range(rw):
            grid[r+1][c+1] = '.'
            grid[r+1][w-2-c] = '.'
    grid[1+rh/2][1+rw/2] = 'b'
    grid[1+rh/2][w-2-rw/2] = 'a'

    tr = random.choice([1, rh])
    grid[tr][1+rw] = 'A'
    grid[tr][2+rw] = 'B'

    grid[1+rh/2+1][random.choice([1+rw/2, w-2-rw/2])] = 'S'

    save_case(grid, short_desc='same_surroundings')

    
def main():
    random.seed(13)

    for case in STATIC_CASES:
        save_case(case.split(), sub_cases=1)

    line(8, 2)
    plus(9, [(-1, 0, 1, 0), (0, -1, 0, 1)])
    
    line(MAX_CELLS, 0)
    line(MAX_CELLS, 2)
    plus(MAX_CELLS, [])
    plus(MAX_CELLS, [(-1, 0, 1, 0), (0, -1, 0, 1)])
    plus(MAX_CELLS, [(-1, 0, 0, -1), (1, 0, 0, 1)])
    plus(MAX_CELLS, [(-1, 0, 0, -1), (0, 1, 1, 0)])

    spiral(50, 1)
    spiral(MAX_CELLS, 1)
    spiral(MAX_CELLS, -1)
        
    same_surroundings1(52)
    same_surroundings1(MAX_CELLS)

    traps = [0, 0, 1, 1, 1, 2, 2, 2, 2, 2]
    for i in range(10):
        while True:
            w = random.randint(3, 100)
            h = random.randint(3, 100)
            p = random.uniform(0, 0.5)
            if (1-p)*(w-2)*(h-2) > MAX_CELLS: continue
            t = traps[i]
            if random_grid(w, h, p, t): break


            
if __name__=='__main__':
    main()