import os
import md5


WIDTH = 5
HEIGHT = 5
NB_PIECES = 9
DB_PATH = 'c'


def ipc_decompress(ipc, reorientate=True):

    def decompress(ipc):
        occupied = 0
        for n in range(NB_PIECES):
            k   = ipc  % (NB_PIECES-n)
            ipc = ipc // (NB_PIECES-n)
            p   = 0
            while True:
                while occupied & (1 << p):
                    p += 1
                if k == 0:
                    break
                p += 1
                k -= 1
            occupied |= 1 << p
            yield (2+p%3, 2+p//3)

    preset = {}
    for y in range(7):
        for x in range(7):
            if x == 0 or x == 6 or y == 0 or y == 6:
                preset[x, y] = '#'
            else:
                preset[x, y] = ' '
    for pos, piece in zip(decompress(ipc),
                          [(px, py) for py in range(3) for px in range(3)]):
        preset[pos] = piece

    if reorientate:
        ipc_hash = ord(md5.md5(str(ipc)).hexdigest()[5])
        if ipc_hash & 1: preset = D8apply(symt, preset)
        if ipc_hash & 2: preset = D8apply(symx, preset)
        if ipc_hash & 4: preset = D8apply(symy, preset)

    preset[1, 1] = '@'
    return preset

# ____________________________________________________________

def D_UP(p):
    if p >= WIDTH:
        return p - WIDTH

def D_DOWN(p):
    if p < WIDTH*(HEIGHT-1):
        return p + WIDTH

def D_LEFT(p):
    if p % WIDTH:
        return p - 1

def D_RIGHT(p):
    if (p % WIDTH) != (WIDTH-1):
        return p + 1

DIRS = [D_UP, D_RIGHT, D_DOWN, D_LEFT]

def symt(x, y, n): return y, x
def symx(x, y, n): return n-x, y
def symy(x, y, n): return x, n-y
def D8apply(f, preset):
    result = {}
    for y in range(7):
        for x in range(7):
            p = preset[f(x, y, 6)]
            if isinstance(p, tuple):
                p = f(p[0], p[1], 2)
            result[x, y] = p
    return result


def valid_config(config):
    for (x, y), piece in config.items():
        if isinstance(piece, tuple):
            px, py = piece
            assert 0 <= px <= 2 and 0 <= py <= 2
            assert 1 <= x <= 5 and 1 <= y <= 5
            if px == 0 and x == 5: return False
            if px == 2 and x == 1: return False
            if py == 0 and y == 5: return False
            if py == 2 and y == 1: return False
    return True

def cc_compress(config):
    pnth = [None]*NB_PIECES
    for (x, y), piece in config.items():
        if isinstance(piece, tuple):
            px, py = piece
            assert 0 <= px <= 2 and 0 <= py <= 2
            n = px+py*3
            assert 1 <= x <= 5 and 1 <= y <= 5
            pnth[n] = (x-1)+(y-1)*5
        elif piece == '@':
            assert 1 <= x <= 5 and 1 <= y <= 5
            playerpos = (x-1)+(y-1)*5
    a, b, c, d, e, f, g, h, i = pnth

    #corners
    corners = (compression_table_a[a] |
               compression_table_c[c] << 4 |
               compression_table_g[g] << 8 |
               compression_table_i[i] << 12)

    # borders
    n = compression_table_b[b]
    if a < b: n -= 1
    if c < b: n -= 1
    borders = n

    n = compression_table_d[d]
    if a < d: n -= 1
    if g < d: n -= 1
    borders += n * 18

    n = compression_table_f[f]
    if c < f: n -= 1
    if i < f: n -= 1
    borders += n * (18*18)

    n = compression_table_h[h]
    if g < h: n -= 1
    if i < h: n -= 1
    borders += n * (18*18*18)

    # center
    center = e;
    if a < e: center -= 1
    if b < e: center -= 1
    if c < e: center -= 1
    if d < e: center -= 1
    if f < e: center -= 1
    if g < e: center -= 1
    if h < e: center -= 1
    if i < e: center -= 1

    # player position
    occupied = {None: True}
    for p in pnth:
        occupied[p] = True

    def fill_hole(startpos):
        occupied[startpos] = True
        queue = [startpos]
        for p in queue:
            for dir in DIRS:
                p2 = dir(p)
                if p2 not in occupied:
                    occupied[p2] = True
                    queue.append(p2)
        return (len(queue) << 5) | startpos

    playerhole = fill_hole(playerpos)
    start = 0
    for p in range(WIDTH*HEIGHT):
        if p not in occupied:
            size = fill_hole(p)
            if size > playerhole:
                start += 1

    result = corners + (borders << 16)
    center += start * 17
    result += center * (16*16*16*16*18*18*18*18)
    return result

def cc_exists(cc):
    BITMAP_MAX     = 16*16*16*16*18*18*18*18*17 * 2
    FILE_SIZE_BITS = 30
    FILE_MASK      = (1<<FILE_SIZE_BITS) - 1

    if cc < BITMAP_MAX:
        offset = cc // 8
        filenum = offset >> FILE_SIZE_BITS
        f = open(os.path.join(DB_PATH, 'db-bitmap-%02d' % filenum), 'rb', 0)
        f.seek(offset & FILE_MASK)
        buf = ord(f.read(1))
        bit = cc & 7
        return ((buf >> bit) & 1) != 0
    else:
        buf = (chr(cc & 0xff) +
               chr((cc >> 8) & 0xff) +
               chr((cc >> 16) & 0xff) +
               chr((cc >> 24) & 0xff) +
               chr((cc >> 32) & 0xff) +
               chr(cc >> 40))
        f = open(os.path.join(DB_PATH, 'db-extra-s'), 'rb', 0)
        f.seek(0, 2)
        start = 0
        stop = f.tell() // 6
        while start < stop:
            mid = (start + stop) // 2
            f.seek(mid*6)
            src = f.read(6)
            if buf < src:
                stop = mid
            elif buf == src:
                return True
            else:
                start = mid + 1
        return False

def exists(config):
    return valid_config(config) and (
        cc_exists(cc_compress(config)) or
        cc_exists(cc_compress(D8apply(symx, config))) or
        cc_exists(cc_compress(D8apply(symy, config))) or
        cc_exists(cc_compress(D8apply(symx, D8apply(symy, config)))))

# ____________________________________________________________

def setup_table(x1, y1, x2, y2):
    table = [None] * 25
    n = 0
    for j in range(y1, y2):
        for i in range(x1, x2):
            table[j*WIDTH + i] = n
            n += 1
    return table
compression_table_a = setup_table(0, 0, 4, 4)
compression_table_b = setup_table(0, 0, 5, 4)
compression_table_c = setup_table(1, 0, 5, 4)
compression_table_d = setup_table(0, 0, 4, 5)
compression_table_f = setup_table(1, 0, 5, 5)
compression_table_g = setup_table(0, 1, 4, 5)
compression_table_h = setup_table(0, 1, 5, 5)
compression_table_i = setup_table(1, 1, 5, 5)
del setup_table