#!/usr/bin/python
# -*- coding: utf-8 -*-

import codecs, re

# ## Definiendo variables globales para el diccionario de rutas y estaciones
rutas = {}
estaciones = {}

# ## Definiendo variables globales para traduccion de dias de la semana
dias = { "L": "lunes",
         "M": "martes o miércoles",
         "J": "jueves",
         "V": "viernes",
         "S": "sábado",
         "D": "domingo",
         "F": "festivo",
    }
manana = {"L":"M","M":"J","J":"V","V":"S","S":"D","D":"L","F":"M"}

# ## Definicion de la clase Estacion con solo dos atributos miembro: nombre y rutas
# ## y tres procedimientos para agregar rutas, averiguar que rutas funcionan a una hora
# ## y cuanto tarda en llegar a una estacion directa
class Estacion:
    def __init__(self,nombre):
        self.nombre = nombre
        self.rutas = set([])

    def agregueruta(self,ruta):
        self.rutas.add(ruta)

    def rutashora(self,dia,hora):
        a = set([])
        for r in self.rutas:
            if r.eshora(dia,hora):
                a.add(r)
        return a

    def tarda(self,dest,ruta):
        c=0
        f,v=False,False
        for x in ruta.recorrido:
            if f: c+= x[2]
            if self==x[0]: f,v=True,True
            if dest==x[0]: f=False
            if f: c+= x[1]
        if v and not f:
            return c
        return 100000

# ## Definicion de la clase ruta con tres atributos: nombre, horario y recorrido
# ## y dos procedimientos para saber si esta funcionando y agregar una estacion al recorrido. 
class Ruta:
    def __init__(self,nombre,horario):
        self.nombre = nombre
        self.horario = horario
        self.recorrido = []

    def eshora(self,dia,hora):
        if dia in ['L','M','J','V']:
            if self.horario[0] in ['L-V','L-S']:
                return hora >= self.horario[1] and hora <= self.horario[2]
        if dia == 'S':
            if self.horario[0] in ['L-S','S']:
                return hora >= self.horario[1] and hora <= self.horario[2]
        if dia in ['D','F']:
            if self.horario[0] == 'D-F':
                return hora >= self.horario[1] and hora <= self.horario[2]
        return False

    def agregueestacion(self,estacion):
        self.recorrido.append((estacion,1,3))
        estacion.agregueruta(self)

# ## funcion para normalizar los nombres de estaciones a items comparables
def normalice(algo):
    s = algo.lower()
    s = s.replace('-',' ')
    s = s.replace('á','a')
    s = s.replace('ç','c')
    s = s.replace('é','e')
    s = s.replace('í','i')
    s = s.replace('ñ','n')
    s = s.replace('ó','o')
    s = s.replace('ú','u')
    s = s.replace('ü','u')
    s = re.sub(r'\b[ck]r+a?\b\.?','carrera',s)
    s = re.sub(r'\bcl+\b\.?','calle',s)
    s = re.sub(r'\bav\b\.?','avenida',s)
    s = re.sub(r'\bge?ral\b\.?','general',s)
    s = re.sub(r'\bu\b\.?','universidad',s)
    s = re.sub(r'\bs\b\.?','sur',s)
    s = re.sub(r'(\d)\s+(a)\b','\1\2',s)
    s = re.sub(r'\b(:de la|del?|el|la)\b','',s)
    s = re.sub(r'\s+',' ',s)
    s = s.strip()
    return s

# ## funcion para obtener un valor numerico de una cadena que indica una hora
def atohora(h):
    m = re.match('(\d+):(\d+)\s*([ap])\.?m?\.?',h)
    if m:
        hh = int(m.group(1))+int(m.group(2))/60.0
        if hh>=12 and hh<13 and m.group(3) in 'aA':
            hh -= 12
        if m.group(3) in 'pP':
            hh += 12
        if hh >= 24:
            hh -= 12
        while hh < 0:
            hh += 12
        return hh
    m = re.match('(\d+)\s*([ap])\.?m?\.?',h)
    if m:
        hh = int(m.group(1))
        if hh>=12 and hh<13 and m.group(2) in 'aA':
            hh -= 12
        if m.group(2) in 'pP':
            hh += 12
        if hh >= 24:
            hh -= 12
        while hh < 0:
            hh += 12
        return hh
    m = re.match('(\d+):(\d+)',h)
    if m:
        hh = int(m.group(1))+int(m.group(2))/60.0
        if hh<5 and len(m.group(1))==1:
            hh += 12
        return hh
    m = re.match('(\d+)',h)
    if m:
        hh = float(m.group(1))
        if hh<5 and len(m.group(1))==1:
            hh += 12
        return hh
    return None

# ## funcion para escribir una hora a partir de un formato numerico
def horatoa(h):
    return "{0:02}:{1:02}".format(int(h),int((h-int(h))*60+0.5))

# ## Procedimiento para crear la base de datos de rutas y estaciones
# ## a partir del archivo de datos
def carguerutas(archivo="transmilenio.dat"):
    fp = codecs.open(archivo,"r","utf-8")
    t = fp.read()
    fp.close()

    rt = re.split(r"\n\n+",t)
    for x in rt:
        rs = re.split(r"\n",x.strip())

        horario=[]
        recorrido=[]
        for s in rs:
            m=re.match('\[(.*)\]',s)
            n=re.match('(L-V|L-S|S|D-F)\s+(\d+:\d+)\s+(\d+:\d+)',s)
            if m:
                nombre = m.group(1)
            elif n:
                horario.append((n.group(1),atohora(n.group(2)),atohora(n.group(3))))
            else:
                recorrido.append(s.strip())
        for i in range(len(horario)):
            rutas[(nombre,i)] = Ruta(nombre,horario[i])
            for e in recorrido:
                ek = normalice(e)
                if ek not in estaciones.keys():
                    eo = Estacion(e)
                    estaciones[ek]=eo
                rutas[(nombre,i)].agregueestacion(estaciones[ek])

# ## Rutina para buscar las posibles rutas,
# ## es una rutina recursiva a varios niveles (indicados).
def buscarrutas(est0,estF,dia,hora,niveles):
    if niveles==0:
        return []
    ee = estaciones.values()
    rr = est0.rutashora(dia,hora)
    aa = []
    while not rr:
        hora += 0.01666666666667
        if hora>24:
            dia = manana[dia]
            hora = 5.499999
        rr = est0.rutashora(dia,hora)
    for r in rr:
        for e in ee:
            if e==est0:
                continue
            t = est0.tarda(e,r)
            if t<10000:
                if e==estF:
                    aa.append([(t,r.nombre,e.nombre,r,e)])
                else:
                    ll = buscarrutas(e,estF,dia,hora+t/60,niveles-1)
                    for l in ll:
                        if not l or l[0][0]>=10000:
                            continue
                        aa.append([(t+l[0][0]+1,r.nombre,e.nombre,r,e)]+l)

    return aa

# ## Rutina para imprimir una ruta a partir de la informacion dada por
# ## buscarrutas()
def describaruta(recorrido):
    a=[]
    for x in recorrido:
        a.append("Tome el {0} hasta {1}.".format(x[3].nombre,x[4].nombre))
    return ' '.join(a)+"  Tiempo {0} minutos.".format(recorrido[0][0])

# ## Procedimiento principal
def main():
    # ## LEER EL ARCHIVO Y CARGAR RUTAS
    carguerutas()

    # ## CREAR LISTA DE ESTACIONES PARA IMPRESION
    probar = True
    prelista = estaciones.keys()
    listado = []
    for x in prelista:
        listado.append(estaciones[x].nombre)
    listado.sort()

    # ## INICIO DEL CICLO INTERACTIVO
    while probar:
        print('Estaciones: ',', '.join(listado))

        # ## PREGUNTAR ESTACIONES DE ORIGEN, DESTINO Y HORA
        orig,dest,hora,dia = None,None,None,'-'
        while orig not in estaciones.keys():
            orig = input("Estación de ingreso: ")
            orig = normalice(orig)
        while dest not in estaciones.keys() and dest != orig:
            dest = input("Estación de salida: ")
            dest = normalice(dest)
        while hora==None:
            hora = input("Hora: ")
            hora = atohora(hora)
        while dia not in "LMJVSDF":
            dia = input("Día de la semana: ")
            dia = dia[0:1].upper()

        estOrig = estaciones[orig]
        estDest = estaciones[dest]

        # ## CALCULAR LAS RUTAS
        print("Probando rutas desde {0} hasta {1} el {2} a las {3}.".format(estOrig.nombre,estDest.nombre,dias[dia],horatoa(hora)))

        alternativas = buscarrutas(estOrig,estDest,dia,hora,3)
        alternativas.sort()

        # ## PRESENTAR LAS RUTAS
        for i in range(5):
            print(describaruta(alternativas[i]))

        # ## PREGUNTAR SI DESEA CONTINUAR
        probar = False

# ejecutar el procedimiento principal solo si el archivo se llama directamente
if __name__=='__main__':
    main()