-
-
Save luishurtado/a0d693c802485780114bbbe480cb0f6e to your computer and use it in GitHub Desktop.
Segunda prueba donde se encuentra el numero de ciclos.
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 | |
cont = 0 | |
paths = [] | |
for k in dict_.keys(): | |
#print("Voy a buscar ciclo para",k) | |
cycle = recurs(dict_, k,k,[]) | |
#print("El camino es: ",cycle) | |
if cycle: | |
set_cycle = set(cycle) | |
if set_cycle not in paths: | |
cont += 1 | |
#print("ordenado",set_cycle) | |
#print("ciclo %s, ciclo ordenado %s"%(cycle)) | |
paths.append(set_cycle) | |
if cycle: | |
print("Si con %s ciclos"%(cont)) | |
#print("Los caminos son:",paths) | |
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]: | |
#print("Match",list(act_k)) | |
return list(act_k) | |
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)) | |
try: | |
path = list(recurs(dict_,goal, temp_k, passed)) | |
if len(path) > 0: | |
path.append(act_k) | |
#print("Match 0 >",path) | |
return path | |
except: | |
pass | |
#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,A | |
M,B | |
M,C | |
A,G | |
B,C | |
M,P | |
P,D | |
D,H | |
D,F | |
F,T | |
H,D | |
F,P |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment