#!/usr/bin/env python3

from typing import List, Tuple, Optional, Set, TextIO
import re
import random
import sys
import copy


USE_UTF8 = False


class Graph:
    Adj: List[List[int]]

    def __init__(self, n: int, A: Optional[List[List[int]]] = None) -> None:
        """initialise un graphe à partir de son nombre de sommets et éventuellement ces listes
        d'adjacences"""
        if A is None:
            self.Adj = [[] for _ in range(n)]
        else:
            if len(A) > n:
                raise ValueError("adjacency list too long!")
            self.Adj = copy.deepcopy(A) + [[] for _ in range(n - len(A))]

    def __len__(self) -> int:
        return len(self.Adj)

    def __getitem__(self, idx: int) -> List[int]:
        return self.Adj[idx]

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

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

    @classmethod
    def random_graph(cls, n: int, d_min: int, d_max: int, symmetric: bool = False) -> "Graph":
        G: List[Set[int]] = [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(n, list(map(lambda l: list(l), G)))

    def pred2edges(self, Pred: List[int]) -> None:
        for v1, v2 in enumerate(Pred):
            if v2 is not None:
                self.Adj[v1].append(v2)
                self.Adj[v2].append(v1)

    @staticmethod
    def from_file(filename: str) -> "Graph":
        """initialise un graphe à partir d'un fichier"""
        header = ""
        A: List[List[int]] = []
        if filename != "-":
            f: TextIO = open(filename, encoding="utf-8-sig")
        else:
            f = sys.stdin
        v = -1
        for L in f:
            if re.search(r"^\s*#", L):
                # comment
                if 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}'")
        f.close()
        g = re.match(r"#%\s*(?P<type>grid|rect|cyl|hex)\s+(?P<width>[0-9]*)\s+(?P<height>[0-9]+)\s*%", header)
        if g:
            w = int(g.group("width"))
            h = int(g.group("height"))
            t = g.group("type")
            if t == "rect":
                return RectGrid(w, h, A)
            elif t == "cyl":
                return CylinderGrid(w, h, A)
            elif t == "hex":
                return HexGrid(w, h, A)
        return Graph(v+1, A)

    def to_file(self, filename: str, header: Optional[str] = None) -> None:
        if filename != "-":
            f: TextIO = open(filename, mode="w", encoding="utf-8")
        else:
            f = sys.stdout

        if header is not None:
            for line in header:
                f.write("#" + line + "\n")

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

    def __str__(self) -> str:
        return str(self.Adj)


class Grid(Graph):
    def __init__(self, width: int, height: int, A: Optional[List[List[int]]] = None):
        self.width = width
        self.height = height
        super().__init__(width*height, A)

    def to_file(self, filename: str, header: Optional[str] = None) -> None:
        if header is None:
            header = ""
        super().to_file(filename, f"#% grid {self.width} {self.height}" + header)

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

    def xy(self, idx: int) -> Tuple[int, int]:
        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: int, height: int) -> "RectGrid":
        G = cls(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

    def to_file(self, filename: str, header: Optional[str] = None) -> None:
        if header is None:
            header = ""
        super().to_file(filename, f"#% rect {self.width} {self.height}" + header)

    @classmethod
    def from_grid(cls, filename: str) -> "RectGrid":
        f = open(filename, encoding="utf-8-sig")
        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)
        if width is None:
            raise ValueError(f"from_grid: file {filename} is empty!")
        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(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
        return G

    def show(self, C: Optional[str] = None) -> None:
        obst = '█' if USE_UTF8 else '#'

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

        print(obst * (2*self.width+1))

        for j in range(2*self.height - 1):
            print(obst, 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(obst, 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(obst, 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(obst, end="")
                else:
                    assert False

            print(obst)

        print(obst * (2*self.width+1))


class CylinderGrid(RectGrid):

    @classmethod
    def full(cls, width: int, height: int) -> "CylinderGrid":
        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 cls(width, height, G.Adj)

    def to_file(self, filename: str, header: Optional[str] = None) -> None:
        if header is None:
            header = ""
        super().to_file(filename, f"#% cyl {self.width} {self.height}" + header)

    @classmethod
    def from_grid(cls, filename: str) -> "CylinderGrid":
        f = open(filename, encoding="utf-8-sig")
        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)
        if width is None:
            raise ValueError(f"from_grid: file {filename} is empty!")
        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(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: Optional[str] = None) -> None:
        obst = '█' if USE_UTF8 else '#'

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

        print(obst * (2*self.width))

        for j in range(2*self.height - 1):
            if j % 2 == 1:
                print(obst, 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(obst, 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(obst, 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(obst, 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(obst, end="")
                else:
                    assert False

            print()

        print(obst * (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, width: int, height: int, A: Optional[List[List[int]]] = None):
        if width % 2 != 0:
            raise ValueError(f"Only even width are allowed for hexagonal grids. (got '{width}')")
        super().__init__(width, height, A)

    def to_file(self, filename: str, header: Optional[str] = None) -> None:
        if header is None:
            header = ""
        super().to_file(filename, f"#% hex {self.width} {self.height}" + header)

    @classmethod
    def full(cls, width: int, height: int) -> "HexGrid":
        G = cls(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: Optional[str] = None) -> 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=120 foldmethod=indent