Created
April 16, 2021 15:20
-
-
Save roa-sh/2e67f5d0c90b2b8ae74353ba2c6d87a8 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
def main(): | |
#Read Arguments | |
arch = sys.argv[1] | |
#print("Nombre archivo",arch) | |
#Read file | |
file = open(arch, "r").read() | |
#replace \n to whitespace | |
file = file.replace('\n',' ') | |
#Split file | |
arr = file.split(' ') | |
#Remove empty lines | |
arr = list(filter(None, arr)) | |
#print(arr) | |
#Create the hash map | |
dict_ = create_hash(arr) | |
#print(dict_.keys()) | |
#Check every key | |
cycle = False | |
for k in dict_.keys(): | |
#print("Voy a buscar ciclo para",k) | |
cycle = recurs(dict_, k,k,[]) | |
if cycle: | |
break | |
if cycle: | |
print("Si") | |
else: | |
print("No") | |
""" | |
Create a dictionary of the accesible nodes for each node | |
""" | |
def create_hash(arr): | |
dict_ = {} | |
for pair in arr: | |
key = pair.split(',')[0] | |
value = pair.split(',')[1] | |
if key in dict_: | |
dict_[key].append(value) | |
else: | |
dict_[key] = list(value) | |
return dict_ | |
""" | |
Recursion where we found a cycle | |
""" | |
def recurs(dict_, goal, act_k, passed): | |
#print("Estoy en %s"%(act_k)) | |
#print("%s conecta con %s? %s"%(act_k, goal, goal in dict_[act_k])) | |
if goal in dict_[act_k]: | |
return True | |
else: | |
#Iterate over the posible paths | |
for i in range(len(dict_[act_k])): | |
#print("%s-%s"%(act_k, i)) | |
temp_k = dict_[act_k][i] | |
#print("He pasado por %s, no esta %s ahi?: %s"%(passed, temp_k, str(temp_k) not in passed)) | |
if (temp_k in dict_.keys()) and(str(temp_k) not in passed): | |
passed.append(temp_k) | |
#print("Agrego %s -> %s"%(temp_k, passed)) | |
if recurs(dict_,goal, temp_k, passed): | |
return True | |
#print("%s es una hoja"%(temp_k)) | |
if __name__ == "__main__": | |
main() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
M,P | |
P,T | |
P,A | |
A,C | |
T,C |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
M,A | |
M,B | |
M,C | |
A,G | |
B,C | |
M,P | |
P,D | |
D,H | |
D,F | |
F,T | |
H,D |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment