#!/usr/bin/env python3

import re
import random
import sys

# TODO: lire des grilles dans un fichier, pas au format liste d'adjacences?


class Graph:

    def __init__(self, A):
        """initialise un graphe à partir de ses listes d'adjacences `A`"""
        self.Adj = tuple(A)

    def __getitem__(self, idx):
        return self.Adj[idx]

    def randomize(self):
        for i in range(len(self.Adj)):
            random.shuffle(self.Adj[i])

    @property
    def N(self):
        return len(self.Adj)

    @classmethod
    def empty(cls, n):
        """initialise un graphe vide à partir de son nombre de sommets"""
        return cls([[] for _ in range(n)])

    @classmethod
    def random_graph(cls, n, d_min, d_max, symmetric=False):
        G = [set() for _ in range(n)]
        for s in range(n):
            d = random.randint(d_min, d_max)
            for _ in range(d):
                v = random.randrange(n)
                G[s].add(v)
                if symmetric:
                    G[v].add(s)
        return cls(list(map(list, G)))

    @classmethod
    def pred2graph(cls, Pred, *args):
        M = cls.empty(len(Pred))
        for v1, v2 in enumerate(Pred):
            if v2 is not None:
                M[v1].append(v2)
                M[v2].append(v1)
        return M

    @classmethod
    def from_file(cls, filename):
        """initialise un graphe à partir d'un fichier"""
        header = ""
        A = []
        if filename != "-":
            f = open(filename)
        else:
            f = sys.stdin
        v = -1
        for L in f:
            if re.search(r"^\s*#", L):
                if not header:
                    header = L
                continue

            v += 1
            A.append([])
            if L.strip() == "-":
                # no neighboors
                continue
            for n in L.split(","):
                try:
                    A[v].append(int(n))
                except ValueError:
                    raise ValueError(f"invalid line: '{L}' (line {v+1})")
        f.close()
        g = re.match(r"#%(?P<type>rect|cyl|hex)\s+(?P<width>[0-9]*)\s+(?P<height>[0-9]+)\s*$", header)
        G = cls(A)
        if g:
            w = int(g.group("width"))
            h = int(g.group("height"))
            t = g.group("type")
            if t == "rect":
                return RectGrid(G.Adj, w, h)
            elif t == "cyl":
                return CylinderGrid(G.Adj, w, h)
            elif t == "hex":
                return HexGrid(G.Adj, w, h)
        return G

    def to_file(self, filename, header=None):
        if filename != "-":
            f = open(filename, "w")
        else:
            f = sys.stdout

        if header:
            f.write("#"+header+"\n")
        for L in self:
            if L:
                f.write(", ".join(map(str, L)))
                f.write("\n")
            else:
                f.write("-\n")
        f.close()

    def __str__(self):
        return super().__str__()


class Grid(Graph):
    def __init__(self, A, width, height):
        assert len(A) == width*height
        super().__init__(A)
        self.width = width
        self.height = height

    @classmethod
    def empty(cls, width, height):
        return cls([[] for _ in range(width*height)], width, height)

    @classmethod
    def pred2graph(cls, Pred, width, height):
        if len(Pred) != width*height:
            raise ValueError("Size mismatch: the `Pred` argument needs to have size `width*height`.")
        M = Graph.pred2graph(Pred)
        return cls(M.Adj, width, height)

    @classmethod
    def from_file(cls, filename, width, height):
        G = Graph.from_file(filename)
        return cls(G.Adj, width, height)

    def idx(self, x, y):
        return y + x*self.height

    def xy(self, idx):
        return idx // self.height, idx % self.height


class RectGrid(Grid):
    # rectangular grids, with cells numbered as
    #    ########
    #    #0|3|6|9
    #    #-#-#-#
    #    #1|4|7|...
    #    #-#-#-#
    #    #2|5|8|...
    #    ########

    @classmethod
    def full(cls, width, height):
        G = cls.empty(width, height)
        G.width = width
        G.height = height
        for y in range(height):
            for x in range(width):
                s = G.idx(x, y)
                if x > 0:
                    v = G.idx(x-1, y)
                    G[v].append(s)
                    G[s].append(v)
                if y > 0:
                    v = G.idx(x, y-1)
                    G[v].append(s)
                    G[s].append(v)
        return G

    @classmethod
    def from_grid(cls, filename):
        f = open(filename)
        M = []
        width = None
        for L in f:
            L = L.rstrip("\n\r")
            if width is not None and width != len(L):
                raise ValueError(f"expected line of length {width}, got {len(L)} instead")
            width = len(L)
            if not re.match(r"[ .#$@]", L):
                raise ValueError(f"invalid line '{L}'")
            M.append(L)
        height = len(M)

        if width % 2 == 0:
            raise ValueError("rectangular grid should have an odd width")
        if height % 2 == 0:
            raise ValueError("rectangular grid should have an odd height")

        G = cls.empty(width//2, height//2)
        for i in range(width):
            for j in range(height):
                if i == 0 or j == 0 or i == width-1 or j == height-1 or i % 2 == j % 2 == 0:
                    if M[j][i] != '#':
                        raise ValueError(f"unexpected character '{M[j][i]}' in position ({i+1},{j+1})")

                elif i % 2 == j % 2 == 1:
                    if M[j][i] not in " .$@":
                        raise ValueError(f"unexpected character '{M[j][i]}' in position ({i+1},{j+1})")

                elif i % 2 == 0 and j % 2 == 1:
                    # door between i//2-1,j//2 and i//2,j//2
                    x = i//2
                    y = j//2
                    if M[j][i] in " .":
                        v1 = G.idx(x-1, y)
                        v2 = G.idx(x, y)
                        G[v1].append(v2)
                        G[v2].append(v1)

                elif i % 2 == 1 and j % 2 == 0:
                    # door between i//2,j//2-1 and i//2,j//2
                    x = i//2
                    y = j//2
                    if M[j][i] in " .":
                        v1 = G.idx(x, y-1)
                        v2 = G.idx(x, y)
                        G[v1].append(v2)
                        G[v2].append(v1)

                else:
                    print(i, j, M[j][i])
                    assert False

        G.grid = M

        return G

    def show(self, C=None):
        if C is None:
            C = ' ' * self.N

        print('#' * (2*self.width+1))

        for j in range(2*self.height - 1):
            print('#', end="")

            for i in range(2*self.width-1):
                x, y = i//2, j//2
                s = self.idx(x, y)
                if i % 2 == j % 2 == 0:
                    print(C[s], end="")
                elif i % 2 == j % 2 == 1:
                    print('#', end="")
                elif i % 2 == 1 and j % 2 == 0:
                    v1 = s
                    v2 = self.idx(x+1, y)
                    if v2 in self.Adj[v1]:
                        print(' ', end="")
                    else:
                        print('#', end="")
                elif i % 2 == 0 and j % 2 == 1:
                    v1 = s
                    v2 = self.idx(x, y+1)
                    if v2 in self.Adj[v1]:
                        print(' ', end="")
                    else:
                        print('#', end="")
                else:
                    assert False

            print('#')

        print('#' * (2*self.width+1))


class CylinderGrid(RectGrid):

    @classmethod
    def full(cls, width, height):
        G = super().full(width, height)
        for y in range(height):
            s = G.idx(0, y)
            v = G.idx(width-1, y)
            G[s].append(v)
            G[v].append(s)
        return G

    @classmethod
    def from_grid(cls, filename):
        f = open(filename)
        M = []
        width = None
        for L in f:
            L = L.rstrip("\n\r")
            if width is not None and width != len(L):
                raise ValueError(f"expected line of length {width}, got {len(L)} instead")
            width = len(L)
            if not re.match(r"[ .#$@]", L):
                raise ValueError(f"invalid line '{L}'")
            M.append(L)
        height = len(M)

        if width % 2 == 1:
            raise ValueError("rectangular grid should have an even width")
        if height % 2 == 0:
            raise ValueError("rectangular grid should have an odd height")

        G = cls.empty(width//2, height//2)
        for i in range(width):
            for j in range(height):
                if j == 0 or j == height-1 or i % 2 == j % 2 == 0:
                    if M[j][i] != '#':
                        raise ValueError(f"unexpected character '{M[j][i]}' in position ({i+1},{j+1})")

                elif i % 2 == j % 2 == 1:
                    if M[j][i] not in " .$@":
                        raise ValueError(f"unexpected character '{M[j][i]}' in position ({i+1},{j+1})")

                elif i % 2 == 0 and j % 2 == 1:
                    # door between i//2-1,j//2 and i//2,j//2
                    x = i//2
                    y = j//2
                    if M[j][i] in " .":
                        v1 = G.idx(x-1 if x > 0 else width//2-1, y)
                        v2 = G.idx(x, y)
                        G[v1].append(v2)
                        G[v2].append(v1)

                elif i % 2 == 1 and j % 2 == 0:
                    # door between i//2,j//2-1 and i//2,j//2
                    x = i//2
                    y = j//2
                    if M[j][i] in " .":
                        v1 = G.idx(x, y-1)
                        v2 = G.idx(x, y)
                        G[v1].append(v2)
                        G[v2].append(v1)

                else:
                    print(i, j, M[j][i])
                    assert False

        return G

    def show(self, C=None):
        if C is None:
            C = ' ' * self.N

        print('#' * (2*self.width))

        for j in range(2*self.height - 1):
            if j % 2 == 1:
                print('#', end="")
            else:
                y = j//2
                v1 = self.idx(0, y)
                v2 = self.idx(self.width-1, y)
                if v1 in self[v2]:
                    print(' ', end="")
                else:
                    print('#', end="")

            for i in range(2*self.width-1):
                x = i//2
                if i % 2 == j % 2 == 0:
                    s = self.idx(x, y)
                    print(C[s], end="")
                elif i % 2 == j % 2 == 1:
                    print('#', end="")
                elif i % 2 == 1 and j % 2 == 0:
                    v1 = self.idx(x, y)
                    v2 = self.idx(x+1, y)
                    if v2 in self.Adj[v1]:
                        print(' ', end="")
                    else:
                        print('#', end="")
                elif i % 2 == 0 and j % 2 == 1:
                    v1 = self.idx(x, y)
                    v2 = self.idx(x, y+1)
                    # print(v1, v2, self.Adj[v1], v2 in self.Adj[v1])
                    if v2 in self.Adj[v1]:
                        print(' ', end="")
                    else:
                        print('#', end="")
                else:
                    assert False

            print()

        print('#' * (2*self.width))


class HexGrid(Grid):
    # hexagonal grids, with cells numbered as follows
    # (For simplicity, only even width are allowed.)
    #  ___     ___     ___
    # /  0\___/ 10\___/ 20\___
    # \___/  5\___/ 15\___/ 25\
    # /  1\___/ 11\___/ 21\___/
    # \___/  6\___/ 16\___/ 26\
    # /  2\___/ 12\___/ 22\___/
    # \___/  7\___/ 17\___/ 27\
    # /  3\___/ 13\___/ 23\___/
    # \___/  8\___/ 18\___/ 28\
    # /  4\___/ 14\___/ 24\___/
    # \___/  9\___/ 19\___/ 29\
    #     \___/   \___/   \___/

    def __init__(self, A, width, height):
        if width % 2 != 0:
            raise ValueError(f"Only even width are allowed for hexagonal grids. (got '{width}')")
        super().__init__(A, width, height)

    @classmethod
    def full(cls, width, height):
        G = cls.empty(width, height)
        for y in range(height):
            for x in range(width):
                s = G.idx(x, y)

                if y > 0:
                    # there is a cell upward
                    v = G.idx(x, y-1)
                    G[s].append(v)
                    G[v].append(s)

                if x > 0 and (x % 2 == 1 or y > 0):
                    # there is a cell up-left
                    if x % 2 == 0:
                        v = G.idx(x-1, y-1)
                    else:
                        v = G.idx(x-1, y)
                    G[s].append(v)
                    G[v].append(s)

                if x < width-1 and (x % 2 == 1 or y > 0):
                    # there is a cell up-right
                    if x % 2 == 0:
                        v = G.idx(x+1, y-1)
                    else:
                        v = G.idx(x+1, y)
                        v = y + (x+1)*height
                    G[s].append(v)
                    G[v].append(s)
        return G

    def show(self, C=None):

        if C is None:
            C = [' ']*self.N

        # first line
        print(" " + "__    " * (self.width//2))

        for j in range(self.height):

            # first line
            print("/", end="")
            for i in range(self.width//2):
                # current cell
                s = self.idx(2*i, j)
                print(f"{C[s]*2}", end="")

                s = self.idx(2*i, j)
                v = self.idx(2*i+1, j-1)
                if v in self[s]:
                    print(' ', end="")
                else:
                    print('\\', end="")

                s = self.idx(2*i+1, j-1)
                v = self.idx(2*i+1, j)
                if v in self[s] and j != 0:
                    print('  ', end="")
                else:
                    print('__', end="")

                s = self.idx(2*i+1, j-1)
                v = self.idx(2*i+2, j)
                if v in self[s] or (i == self.width//2 - 1 and j == 0):
                    print(' ', end="")
                else:
                    print('/', end="")
            print()

            # second line
            for i in range(self.width//2):
                s = self.idx(2*i, j)
                v = self.idx(2*i-1, j)
                if v in self[s]:
                    print(' ', end="")
                else:
                    print('\\', end="")

                s = self.idx(2*i, j)
                v = self.idx(2*i, j+1)
                if v in self[s]:
                    print('  ', end="")
                else:
                    print('__', end="")

                s = self.idx(2*i, j)
                v = self.idx(2*i+1, j+1)
                if v in self[s]:
                    print(' ', end="")
                else:
                    print('/', end="")

                s = self.idx(2*i+1, j)
                # print(f"{s:02}", end="")
                print(f"{C[s]*2}", end="")
            print("\\")

        # last line
        print(" " + r"  \__/" * (self.width//2))

# vim: textwidth=100 foldmethod=indent