from IPython.display import HTML
from jinja2 import Template

def make_table(M, N, id):
    table = Template("""<table id="{{ id }}">
{% for row in rows %}
<tr>
    {% for col in cols %}<td id="c{{ row }}{{ col }}">$c_{ {{ row }}{{ col }} }$</td>{% endfor %}
</tr>
{% endfor %}
</table>""").render(rows=range(M), cols=range(N), id=id)
    return table

style = """<style>
table#t1 #c22 { background-color: #bcd; border-width: 2px; }
table#t1 #c11,
table#t1 #c12,
table#t1 #c13,
table#t1 #c21,
table#t1 #c23,
table#t1 #c31,
table#t1 #c32,
table#t1 #c33 { background-color: #def; }
</style>
"""

HTML(style + make_table(5, 5, "t1"))

style = """<style>
table#t2 #c21 { background-color: #bcd; border-width: 2px; }
table#t2 #c10,
table#t2 #c11,
table#t2 #c12,
table#t2 #c20,
table#t2 #c22,
table#t2 #c30,
table#t2 #c31,
table#t2 #c32 { background-color: #def; }
</style>
"""

HTML(style + make_table(5, 5, "t2"))

%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm

A55 = np.array([
[0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0],
[0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1],
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0],
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0]
])

"""
$$ A = \tiny \begin{pmatrix}
0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & \normalsize{0} & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0
\end{pmatrix} $$
"""

plt.matshow(A55, cmap=cm.gray_r)
plt.grid(False)

M, N = 5, 5  # Dimensiones del tablero

R_22 = np.zeros((5, 5))  # Idea de Chema Cortés
R_22[1:4, 1:4] = np.ones((3, 3))
R_22[2, 2] = 0
print(R_22)
R_22 = R_22.flatten()

R_00 = np.roll(R_22, 2 * (-N - 1))  # Trasladamos el vector
R_00

cnt = np.count_nonzero(R_00)
nonzero_idx = R_00.nonzero()[0]
print(cnt, nonzero_idx)

import scipy.sparse as ss

np.set_printoptions(linewidth=100)
ss.diags(np.ones(cnt),  # Número de unos
         nonzero_idx,  # Posiciones
         shape=(M * N, M * N),  # Tamaño de la matriz
         format="csr",  # Formato (CSR es mejor para productos matriz-vector)
         dtype=int  # Tipo entero
         ).todense()

ss.diags(np.ones(cnt * 2),  # Número de unos
         list(-nonzero_idx) + list(nonzero_idx),  # Posiciones
         shape=(M * N, M * N),  # Tamaño de la matriz
         format="csr",  # Formato (CSR es mejor para productos matriz-vector)
         dtype=int  # Tipo entero
         ).todense()

def adjacency_matrix(M, N):
    """Matriz de adyacencia de un tablero M x N.

    Reglas:

    * 8 vecinos por celda
    * Geometría toroidal

    No he implementado el caso N < 3 o M < 3.

    """
    if M < 3 or N < 3:
        raise NotImplementedError

    R_11 = np.zeros((M, N))
    R_11[0:3, 0:3] = np.ones((3, 3))
    R_11[1, 1] = 0
    R_00 = np.roll(R_11.flatten(), -N - 1)
    mn = M * N
    cnt = np.count_nonzero(R_00)
    nonzero_idx = R_00.nonzero()[0]
    A = ss.diags(np.ones(cnt * 2, dtype=int), list(-nonzero_idx) + list(nonzero_idx),
                 shape=(mn, mn), format="csr", dtype=int)
    return A

def plot_board(A, axis=True):
    plt.matshow(A, cmap=cm.gray_r)
    plt.grid(False)
    if not axis:
        plt.axis('off')

plot_board(adjacency_matrix(5, 5).todense())
plot_board(adjacency_matrix(4, 12).todense())

%timeit adjacency_matrix(100, 200)

adj_matrices = {}
def get_adj_matrix(M, N):
    try:
        A = adj_matrices[(M, N)]
    except KeyError:
        A = adjacency_matrix(M, N)
        adj_matrices[(M, N)] = A
    return A

%timeit -n1 -r1 get_adj_matrix(100, 200)

%timeit get_adj_matrix(100, 200)

from scipy.signal import convolve2d
def life_step_1(X):
    """Game of life step using generator expressions"""
    nbrs_count = sum(np.roll(np.roll(X, i, 0), j, 1)
                     for i in (-1, 0, 1) for j in (-1, 0, 1)
                     if (i != 0 or j != 0))
    return (nbrs_count == 3) | (X & (nbrs_count == 2))

def life_step_2(X):
    """Game of life step using scipy tools"""
    nbrs_count = convolve2d(X, np.ones((3, 3)), mode='same', boundary='wrap') - X
    return (nbrs_count == 3) | (X & (nbrs_count == 2))

def life_step_3(X):
    """Calcula el paso usando la matriz de adyacencia."""
    A = get_adj_matrix(*X.shape)
    nbrs_count = A.dot(X.flatten()).reshape(X.shape)
    return (nbrs_count == 3) | (X & (nbrs_count == 2))

tab = np.round(np.random.rand(100, 200)).astype(int)  # Tablero aleatorio
get_adj_matrix(*tab.shape)  # Cacheamos la matriz correspondiente

%timeit life_step_1(tab)

%timeit life_step_2(tab)

%timeit life_step_3(tab)

from functools import reduce

for ii in range(0, 18, 6):
    plot_board(reduce(lambda x, _: life_step_3(x), range(ii), tab), False)
    plt.title("{} iteraciones".format(ii))