Created
April 27, 2021 15:06
-
-
Save roa-sh/8787fd8a49dd3e7be5fb17fe9e3dad56 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