#!/usr/bin/env pypy3

# école supélec contrale - 2016 - c. dürr
# devoir maison 1 - connect
# www-desir.lip6.fr/~durrc/Iut/optim/t/dm1-connect/

import sys
from random import randint
from itertools import product   # produit cartésien
from constraint_programming import constraint_program


# ====================================== grille

def generate(rows, cols):
    """Generates a random grid
    """
    # generate random connections, place 0 at the border
    lr = [[randint(0, 1) for j in range(cols - 1)] + [0] for i in range(rows)]
    tb = [[randint(0, 1) for j in range(cols)]  for i in range(rows - 1)]
    tb += [[0] * n]
    for i in range(rows):
        for j in range(cols):
            # encoding of the cell
            c = tb[i - 1][j] + 2*lr[i][j - 1] + 4*tb[i][j] + 8*lr[i][j]
            cc = c | (c << 4)
            # normalized orientation
            p = min((cc >> i) & 15 for i in range(4))
            print(hex(p)[-1], end='')
        print()


def read_grid():
    """reads a grid from stdin
    """
    grid = []
    for line in sys.stdin:
        line = line.strip()
        if line:
            grid.append(list(int(x, 16) for x in line))
    return grid


def prettyprint(grid):
    """ reads a grid from stdin and pretty prints it.
    """
    rows = len(grid)
    cols = len(grid[0])
    for i in range(rows):
        # top row of cell
        for j in range(cols):
            if grid[i][j] & 1:
                print("  |  ", end='')
            else:
                print("     ", end='')
        print()
        # center row of cell
        for j in range(cols):
            if grid[i][j] & 2:
                print("--o", end='')
            else:
                print("  o", end='')
            if grid[i][j] & 8:
                print("--", end='')
            else:
                print("  ", end='')
        print()
        # bottom row of cell
        for j in range(cols):
            if grid[i][j] & 4:
                print("  |  ", end='')
            else:
                print("     ", end='')
        print()


# ====================================== tuiles

# toutes les tuiles possibles
T = range(16)

# les faces d'une tuile
TOP = 0
LEFT = 1
BOTTOM = 2
RIGHT = 3

# formes possible d'une tuile pour les différentes rotations
rotation = { 0: [0],
             1: [1, 2, 4, 8],
             3: [3, 6, 12, 9],
             5: [5, 10],
             7: [7, 14, 13, 11],
             15:[15]}

# pour une tuile et une face donnée, y a-t-il un connecteur ?
def tile_side(tile, side):
    "presence of a connnector on a side of the tile"
    return (tile >> side) & 1

# couples de tuiles adjacents qui sont compatibles
left_match_right = {(a,b) for a in T for b in T if tile_side(a, RIGHT) == tile_side(b, LEFT)}
top_match_bottom = {(a,b) for a in T for b in T if tile_side(a, BOTTOM) == tile_side(b, TOP)}

# tuiles sans connecteur vers le bord
def border_tile(border):
    return {a for a in T if not tile_side(a, border)}


# ====================================== variables

# variables du modèle 1

def cell(i, j):
    return (i, j)

# variables du modèle 2

def hpair(i, j):
    return ('hpair', i, j)

def vpair(i, j):
    return ('vpair', i, j)



# ====================================== modéleur

# --- résolution avec notre solveur CSP

def solve(grid, model=1):
    rows = len(grid)
    ROWS = range(rows)
    cols = len(grid[0])
    COLS = range(cols)

    #  --- rotations possible par case
    dom_cell = {cell(i, j): set(rotation[grid[i][j]]) for i in ROWS for j in COLS}
    #  --- appliquer les contraintes unaires sur les cases du bord
    for j in COLS:
        dom_cell[ cell(0, j) ] &= border_tile(TOP)
    for i in ROWS:
        dom_cell[ cell(i, 0) ] &= border_tile(LEFT)
    for j in COLS:
        dom_cell[ cell(rows - 1, j) ] &= border_tile(BOTTOM)
    for i in ROWS:
        dom_cell[ cell(i, cols - 1) ] &= border_tile(RIGHT)

    # paires de rotations possibles par paires de cases adjacentes
    dom_hv = {}
    #  --- rotations possibles pour cases adjacentes horizontalement
    for i in ROWS:
        for j in range(cols - 1):
            Dx = dom_cell[ cell(i, j) ]
            Dy = dom_cell[ cell(i, j + 1) ]
            dom_hv[hpair(i, j)] = set(product(Dx, Dy)) & left_match_right
    #  --- rotations possibles pour cases adjacentes verticalement
    for i in range(rows - 1):
        for j in COLS:
            Dx = dom_cell[ cell(i, j) ]
            Dy = dom_cell[ cell(i + 1, j) ]
            dom_hv[vpair(i, j)] = set(product(Dx, Dy)) & top_match_bottom

    if model == 1:  # ------------------------------------------------------------ 1
        P = constraint_program(dom_cell)
        #  --- tuiles adjacentes dans une même colonne
        for i in range(rows - 1):
            for j in COLS:
                P.add_constraint(cell(i, j), cell(i + 1, j), dom_hv[vpair(i, j)])
        #  --- tuiles adjacentes dans une même ligne
        for i in ROWS:
            for j in range(cols - 1):
                P.add_constraint(cell(i, j), cell(i, j + 1), dom_hv[hpair(i, j)])
        #  --- trouver les solutions
        sol = P.solve()
        for i in ROWS:                        # print solution
            for j in COLS:
                print(hex(sol[cell(i, j)])[-1], end='')
            print()

    elif model == 2:  # ------------------------------------------------------------ 2
        P = constraint_program(dom_hv)
        # --- paires horizontaux intersectant en une case
        for i in ROWS:
            for j in range(cols - 2):
                x = hpair(i, j)
                y = hpair(i, j + 1)
                constr = set((uv, vw) for uv in dom_hv[x] for vw in dom_hv[y] if uv[1] == vw[0])
                P.add_constraint(x, y, constr)
        # --- paires verticaux intersectant en une case
        for i in range(rows - 2):
            for j in COLS:
                x = vpair(i, j)
                y = vpair(i + 1, j)
                constr = set((uv, vw) for uv in dom_hv[x] for vw in dom_hv[y] if uv[1] == vw[0])
                P.add_constraint(x, y, constr)
        # --- paires horizontaux-verticaux intersectant dans la case bas-droite
        for i in range(1, rows):
            for j in range(1, cols):
                x = vpair(i - 1, j)
                y = hpair(i, j - 1)
                constr = set((uv, wv) for uv in dom_hv[x] for wv in dom_hv[y] if uv[1] == wv[1])
                P.add_constraint(x, y, constr)
        # --- paires horizontaux-verticaux intersectant dans la case haut-gauche
        for i in range(rows - 1):
            for j in range(cols - 1):
                x = vpair(i, j)
                y = hpair(i, j)
                constr = set((uv, uw) for uv in dom_hv[x] for uw in dom_hv[y] if uv[0] == uw[0])
                P.add_constraint(x, y, constr)
        #  --- trouver les solutions
        sol = P.solve()
        for i in ROWS:                        # print solution
            for j in range(cols - 1):
                print(hex(sol[hpair(i, j)][0])[-1], end='')
            print(hex(sol[hpair(i, cols - 2)][1])[-1]) # special care for last cell in row

    else: # ------------------------------------------------------------ 3
        assert model == 3
        # combine les variables de modèles précédents
        dom = dom_cell
        dom.update(dom_hv)
        P = constraint_program(dom)
        # --- paire horizontale et case
        for i in ROWS:
            for j in range(cols - 1):
                x = hpair(i, j)
                y = cell(i, j)
                constr = set((ab, a) for ab in dom[x] for a in dom[y] if ab[0] == a)
                P.add_constraint(x, y, constr)
                y = cell(i, j + 1)
                constr = set((ab, b) for ab in dom[x] for b in dom[y] if ab[1] == b)
                P.add_constraint(x, y, constr)
        # --- paire verticale et case
        for i in range(rows - 1):
            for j in range(cols):
                x = vpair(i, j)
                y = cell(i, j)
                constr = set((ab, a) for ab in dom[x] for a in dom[y] if ab[0] == a)
                P.add_constraint(x, y, constr)
                y = cell(i + 1, j)
                constr = set((ab, b) for ab in dom[x] for b in dom[y] if ab[1] == b)
                P.add_constraint(x, y, constr)
        # --- trouver les solutions
        sol = P.solve()
        for i in ROWS:                        # print solution
            for j in range(cols):
                print(hex(sol[cell(i, j)])[-1], end='')
            print()


def help():
    print("Usage: ./connect.py <arguments>")
    print("  -g <rows> <cols> to generate a grid of given dimension")
    print("  -p               to pretty print a grid given in stdin")
    print("  -s <model>       to solve a grid given in stdin, model can be 1,2 or 3, default=1")


if __name__ == '__main__':
    if len(sys.argv) == 3 and sys.argv[1] == "-g":
        n = int(sys.argv[2])
        generate()
    elif len(sys.argv) == 2 and sys.argv[1] == "-p":
        prettyprint(read_grid())
    elif len(sys.argv) == 2 and sys.argv[1] == "-s":
        solve(read_grid())
    elif len(sys.argv) == 3 and sys.argv[1] == "-s":
        solve(read_grid(), int(sys.argv[2]))
    else:
        help()