SHACO - The jokes on you!

# -*- coding: utf-8 -*-
## Shaco ##

import random

def creaMatriz(n, limite_superior, seed):
    """ Crea una matriz de n x n con valores menores a limite_superior """
    random.seed(seed)
    m = []
    for row in range(n):
        cel = []
        m.append(cel)
        for col in range(n):
             cel.append(limite_superior * random.random())
    return m

def imprimeMatriz(matriz):
    """ Imprime la matriz dada de manera ORDENADA """
    for fil in range(len(matriz)):
            print str(matriz[fil])

def sumarPesosAdyacentes(ciudades, feromonas, usadas, ciudad_actual):
    """ Suma el peso de las ciudades adyacentes """

    suma_total = 0.0

    for ciudad in range(len(ciudades)):
        if not usadas.has_key(ciudad):
            suma_total =(suma_total + ciudades[ciudad_actual][ciudad] * (1.0 + feromonas[ciudad_actual][ciudad]))

    return suma_total

def encuentraCiudad(ciudades, feromonas, usadas, ciudad_actual, porcentaje):
    """ Regresa la siguiente ciudad visitada en el recorrido """

    suma_total = 0.0
    siguiente = 0

    for ciudad in range(len(ciudades)):
        if suma_total >= porcentaje:
            break
        if not usadas.has_key(ciudad):
             suma_total =(suma_total + ciudades[ciudad_actual][ciudad] * (1.0 + feromonas[ciudad_actual][ciudad]))
             siguiente = ciudad
    return siguiente

def crearCamino(ciudades, feromonas):
    """ Regresa el camino que recorre una hormiga como una lista """

    ciudad_actual = random.randint(0, len(ciudades)-1)
    camino = [ciudad_actual]
    usadas = {ciudad_actual:1}

    while len(usadas) < len(ciudades):
        suma_de_pesos = sumarPesosAdyacentes(ciudades, feromonas, usadas, ciudad_actual)
        porcentaje = random.random() * suma_de_pesos
        ciudad_actual = encuentraCiudad(ciudades, feromonas, usadas, ciudad_actual, porcentaje)
        camino.append(ciudad_actual)
        usadas[ciudad_actual] = 1

    return camino

def caminoAdelantado(camino):
    """ Regresa una copia del camino pero adelantando todo un indice """
    return camino[1:4] + [camino[0]]


def longitudCamino(ciudades, camino):
    """ Regresa la longitud del camino seguido por la hormiga """
    pares = zip(camino, caminoAdelantado(camino))
    return sum([ciudades[fil][col] for (fil,col) in pares])

def actualizarFeromonas(feromonas, camino, boost):
    """ Actualiza las feromonas en la matriz de feromonas """

    pares = zip(camino, caminoAdelantado(camino))
    for (fil,col) in pares:
        feromonas[fil][col] = feromonas[fil][col] + boost

def evaporarFeromonas(feromonas, hormigas, boost):
    """ Evapora las feromonas en la matriz de feromonas """

    decremento = boost / float(hormigas)
    for fil in range(len(feromonas)):
        for col in range(len(feromonas[fil])):
            if feromonas[fil][col] > decremento:
                feromonas[fil][col] = feromonas[fil][col] - decremento
            else:
                feromonas[fil][col] = 0.0

def mejorCamino(ciudades, seed, hormigas, boost):
    """ Regresa el camino óptimo """

    feromonas = creaMatriz(len(ciudades), 0, 0)
    random.seed(seed)
    mejor_camino = []

    for i in range(hormigas):
        camino = crearCamino(ciudades, feromonas)
        longitud_camino = longitudCamino(ciudades, camino)
        if i == 0:
            longitud_mejor_camino = longitud_camino
        print "El camino que siguio la hormiga fue: ", camino
        print "Su recorrido fue: ", longitud_camino
        print "----------------------"
        if longitud_camino < longitud_mejor_camino:
           actualizarFeromonas(feromonas, camino, boost)
           longitud_mejor_camino = longitud_camino
           mejor_camino = camino
        evaporarFeromonas(feromonas, hormigas, boost)
    return mejor_camino

seed = 2
boost = 1000
hormigas = 30
num_de_ciudades = 6
distancia_max = 100
seed_de_distancias = 1

ciudades = creaMatriz(num_de_ciudades, distancia_max, seed_de_distancias)

mejor_camino = mejorCamino(ciudades, seed, hormigas, boost)

print("El mejor camino fue este: \n")
print(mejor_camino)
print("Distancia recorrida: ", longitudCamino(ciudades, mejor_camino))