#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Aug 23 08:02:49 2019

@author: adomps
"""

import random as rd
import matplotlib.pyplot as plt

#####################################################
##  Construction d'un labyrinthe parfait
######################################################
##  On prend un réseau carré (par simplicité) et on donne
# un poids aléatoire à chaque arête. On extrait son arbre couvrant
# minimal : c'est la labyrinthe parfait !


def numero(i, j, N_col) :
    ''' Renvoie le numéro de la case (i, j). Les cases sont parcourues
    dans l'ordre de lecture, les numéros vont de 0 (en haut à gauche)
    à (N_lig * N_col - 1) en bas à droite. '''
    return i * N_col + j

def indices_lig_col(num, N_col) :
    ''' réciproque de la fonction précédente '''
    return divmod(num, N_col) 

def ajoute_arete_alea(L_adj, p, q):
    ''' Ajoute une arête aléatoire de p vers q en modifiant la liste
    d'adjacence passée en paramètre '''
    poids = rd.random() # poids aléatoire dans [0, 1]
    L_adj[p].append((q, poids))

def reseau_carre_alea(N_lig, N_col) :
    L_adj = [[] for _ in range(N_lig * N_col)]
    for i in range(N_lig) :
        for j in range(N_col) :
            p =  numero(i, j, N_col)
            for (a, b) in ((i-1, j), (i, j-1),  (i, j+1), (i+1, j)) :
                if 0 <= a <= N_lig - 1 and 0 <= b <= N_col - 1 :
                    q = numero(a, b, N_col)
                    ajoute_arete_alea(L_adj, p, q)
    return L_adj

def produit_labyrinthe_alea(N_lig, N_col) :
    ''' renvoie la liste des couples (i, j) reliés par un passage '''
    Laby = []
    L_adj_graphe = reseau_carre_alea(N_lig, N_col)
    couvrant = Kruskal(L_adj_graphe)
    for A in couvrant :
        p, q = A[0], A[1] # numéro des sommets connectés par l'arête
        couple_p = indices_lig_col(p, N_col)
        couple_q = indices_lig_col(q, N_col)
        Laby.append((couple_p, couple_q))
    return Laby
    
def dessine_labyrinthe(Pile_labyrinthe, n) :
    plt.figure()
    ax = plt.gca()
    ax.patch.set_facecolor('blue')  # Pour avoir un fond qui représentera les murs    
    plt.xlim(-1, n)
    plt.ylim(-1, n)
    while not est_vide(Pile_labyrinthe) :
        segment = depile(Pile_labyrinthe)
        x_A, y_A = segment[0]
        x_B, y_B = segment[1]
        plt.plot([x_A,x_B], [y_A,y_B], color='white', linewidth = 15)


Z = produit_labyrinthe_alea(8, 8)
dessine_labyrinthe(Z, 8) # fonction d'un code du chapitre sur les piles pour les laby carrés