#!/usr/bin/python3

'''
License:
        1) To be used and distributed while in Python. If you compile this source then you may not distribute it.
        2) The credit and date and time and place below must be kept unmodified and must be shown to the user.
'''

import random

class Point:
    def __init__ (self, x, y):
        self.x = x
        self.y = y
    def __eq__ (self, other):
        if ((self.x==other.x)and(self.y==other.y)):
            return True
        return False
    def __str__ (self):
        return (str(self.x)+","+str(self.y))

class Edge:
    def __init__ (self, p0, p1=None):
        if (p1 is None):
            l = p0.split(",")
            self.a = Point (int(l[0]), int(l[1]))
            self.b = Point (int(l[2]), int(l[3]))
            return
        self.a = p0
        self.b = p1
    def revert (self):
        return Edge (self.b, self.a)
    def __str__ (self):
        return (str(self.a)+","+str(self.b))

def readMap (name):
    f = open (name)
    lines = f.readlines()
    el = []
    for l in lines:
        #print(l)
        el.append (Edge (l))
    return el

def mapGetListOfPoints (el):
    pl = []
    for edge in el:
        if (False==pl.__contains__(edge.a)):
            pl.append (edge.a)
        if (False==pl.__contains__(edge.b)):
            pl.append (edge.b)
    #print ("mapGetListOfPoints returning: "+str(pl))
    return pl

class EdgePos:
    def __init__ (self, e, p):
        self.e = e
        self.p = p

def mapGetListOfEdgesPos (el, p):
    #print ("mapGetListOfEdges (el, "+str(p)+"):")
    ret = []
    i = 0
    for edge in el:
        if (edge==None):
            i+=1
            continue
        if (edge.a==p):
            ep = EdgePos (edge, i)
            ret.append (ep)
            i+=1
            continue
        if (edge.b==p):
            ep = EdgePos (edge.revert(), i)
            ret.append (ep)
        i+=1
    #print ("mapGetListOfEdges returning "+str(ret))
    return ret

def strlist (path):
    ret = ""
    for edge in path:
        ret = ret+"["+str(edge)+"]"
    return ret

pl = None
pllen = 0

def isHamiltonianCycle (path):
    finalEdge = path[len(path)-1]
    cpp = []
    for edge in path:
        if (cpp.__contains__(edge.a)):
            #print ("Duplicated point: "+strlist(path))
            return False
        cpp.append (edge.a)
        if (edge==finalEdge):
            if (edge.b != path[0].a):
                #print ("Final point is not the begining point.")
                return False
    if (len(cpp)<len(pl)):
        #print ("Current path does not contain all points.")
        return False
    return True

def copyList (l):
    ret = []
    for i in l:
        ret.append(i)
    return ret

def mapGetPath (el):
    #print ("mapGetPath(el):")
    path = []
    if (len(el)==1):
        e = el[0]
        path.append (e)
        path.append (e.revert())
        return path
    localEdgesList = copyList (el)
    #print ("mapGetPath (el):")
    current = pl[random.randint(0, len(pl)-1)]
    #print ("Initial point is "+str(current))
    while (len(path)<pllen):
        possibilities = mapGetListOfEdgesPos (localEdgesList, current)
        lpos = len(possibilities)
        if (lpos==0): return None
        ri = random.randint (0, lpos-1)
        #print ("lpos="+str(lpos)+"\tri="+str(ri))
        ep = possibilities[ri]
        random_edge = ep.e
        localEdgesList[ep.p]=None
        #print ("random_edge="+str(random_edge))
        path.append (random_edge)
        current = random_edge.b
    if (isHamiltonianCycle (path)):
        return path
    return None

if __name__=="__main__":
    print ("hc - Find a hamiltonian cycle from a map of edges.\nWritten by Pedro Izecksohn on 30 of March of 2018 20:36 on Rio de Janeiro.\nThe format of map must be:\nx0,y0,x1,y1\nOne edge per line.")
    mn = input ("Map's name: ")
    el = readMap (mn)
    #print (el)
    pl = mapGetListOfPoints (el)
    pllen = len(pl)
    if (0==pllen):
        print ("This map does not contain any point.")
        input ("Press Enter to exit.")
        exit()
    nt = int (input ("Number of tries: "))
    i = 0
    while (i<nt):
        path = mapGetPath (el)
        if (None==path):
            i+=1
            continue
        else:
            print (strlist (path))
            input ("Press Enter to exit.")
            exit()
    print ("Hamiltonian cycle not found.")
    input ("Press Enter to exit.")