from numpy import *
from pylab import *

def Exp1(A,n) :
    p=len(A[0,:]) # nombre de colonnes de A
    Mat_Temp=eye(p,p) # matrice unité
    for k in range(n) :
        Mat_Temp=dot(Mat_Temp,A)
    return Mat_Temp
    
A=array([[1,2,3],[0,2,4],[0,0,-1]])

def Exp2(A,n) :
    ### on décompose d'abord n en base deux ###
    Liste_A_Remplir=[]
    exposant=n
    while exposant !=0 :
        if exposant%2==0 :
            Liste_A_Remplir.append(0)
            exposant=exposant//2
        else :
            Liste_A_Remplir.append(1)
            exposant=(exposant-1)//2
    ## Liste_A_Remplir = décomposition inversée en binaire de n 
    
    p=len(A[0,:]) # nombre de colonnes de A
    Mat_Temp=eye(p,p)
    for k in range(len(Liste_A_Remplir)) :
        if Liste_A_Remplir[k]==1 :
            Mat_Init=A
            for q in range(k) :
                Mat_Init=dot(Mat_Init,Mat_Init)
            ### Mat_Init = A puissance (2**k)
            Mat_Temp=dot(Mat_Temp,Mat_Init)
    return Mat_Temp

def Exp3(A,n) :
    if n==0 :
        p=len(A[0,:])
        return eye(p,p)
    else :
        if n%2==0 :
            Mat_Temp=Exp3(A,n//2) # sinon, on perd le bénéfice de la récursivité
            return dot(Mat_Temp,Mat_Temp) 
        else :
            return dot(Exp3(A,n-1),A)

# k=5
# print(Exp1(A,k))
# print(Exp2(A,k)) # ok
# print(Exp3(A,k)) # ok 

def Place(p,q,k) :
    """ retourne [i,j] avec i le numéro de la ligne et j le numéro de la colonne """
    return [k//q,k%q]

# p,q=8,3
# for k in range(24) :
#     print(Place(p,q,k))
    
        
def Test(p,q,x,y) :
    """ teste si les cases x et y sont distantes de 1 dans le tore """
    return ((x[0]-y[0])%p==0 and (((x[1]-y[1])%q)==1 or ((x[1]-y[1])%q)==q-1)) or ((x[1]-y[1])%q==0 and (((x[0]-y[0])%p)==1 or ((x[0]-y[0])%p)==p-1)) 
    
def Mat_Transitions(p,q) :
    """ renvoie la matrice d'adjacence sur le tore Z_p*Z_q  :  matrice carrée """
    Mat_Temp=zeros((p*q,p*q))
    for i in range(p*q) :
        for j in range(p*q) :
            x,y=Place(p,q,i),Place(p,q,j)
            if Test(p,q,x,y) :
                Mat_Temp[i,j]=1/4
    return Mat_Temp
# 
# p,q=3,2
# print(Mat_Transitions(p,q))

import time 

def Graphiques_Temps_Calculs(p,q,nombre) :
    
    LX=list(range(nombre))

    A=Mat_Transitions(p,q)
    LY1,LY2,LY3=[],[],[]
    for x in LX :
        t_0=time.clock()
        Exp1(A,x)
        t_1=time.clock()
        LY1.append(t_1-t_0)
    
    for x in LX :
        t_0=time.clock()
        Exp2(A,x)
        t_1=time.clock()
        LY2.append(t_1-t_0)
    
    for x in LX :
        t_0=time.clock()
        Exp3(A,x)
        t_1=time.clock()
        LY3.append(t_1-t_0)
    
    figure()
    plot(LX,[log(x) for x in LY1],color="blue")
    plot(LX,[log(x) for x in LY2],color="green")
    plot(LX,[log(x) for x in LY3],color="red")
    legend(("Algo naïf","Algo rapide itératif","Algo rapide récursif"),
            'upper center', shadow=True)
    show()

Graphiques_Temps_Calculs(7,8,101)

# conclusion : Algo Naïf < Algo rapide itératif < Algo rapide récursif
# 
# p,q=3,6  # problème si p ou q vaut 2
# A=Mat_Transitions(p,q)
# print(A)

def Liste_Positions_Plus_Probables(p,q,n) :
    """ calcule la liste des positions les plus probables en partant de (0,0) après n itérations """
    Liste_Temp=[x for x in Exp3(Mat_Transitions(p,q),n)[0,:]] # première ligne de A**n
    Liste_Gagnants=[]
    Maxi=0 # car certaines occurrences (en fait toutes) de la matrice sont positives
    for k in range(len(Liste_Temp)) :
        if Liste_Temp[k]>Maxi :
            Maxi=Liste_Temp[k]
            Liste_Gagnants=[k]
        elif Liste_Temp[k]==Maxi :
            Liste_Gagnants.append(k)
    return [Place(p,q,x) for x in Liste_Gagnants]

p,q=6,8
n=7
print(Liste_Positions_Plus_Probables(p,q,n))