200LinesOfCodeADay/bfs_findingMutation.py at master · proishan11/200LinesOfCodeADay · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
def replace(temp, i ,x):
	result = list(temp)
	result[i] = x
	return "".join(result)

def findMutation(start, end, bank):
	changes = {'A': ['C','T','G'],
				'C': ['A','T', 'G'],
				'T': ['A', 'C', 'G'],
				'G': ['A', 'C', 'T']}
	level={start:0}
	tolevel={end: 0}
	l=1
	tol = 1
	frontier = [start]
	tofrontier = [end]

	while(frontier and tofrontier):
		#print(frontier)
		flag = False
		toflag = False
		next = []
		tonext = []
		for dna in frontier:
			next_node = dna
			#print(next_node)
			for i in range(8):
				temp=next_node
				#print("temp=",temp)
				strand = temp[i]
				#print(changes[strand])
				for x in changes[strand]:
					#print(temp)
					temp = replace(temp, i, x)
					#print(temp)
					if(temp in bank):
						flag=True
						next.extend([temp])
						level[temp]=l
						if(temp in tolevel):
							return level[temp]+tolevel[temp]

					temp = next_node
		if(flag==False):
			return -1
		else:
			flag=False
			frontier=next
			l=l+1

		for todna in tofrontier:
			tonext_node = todna
			for i in range(8):
				totemp = tonext_node
				tostrand = totemp[i]
				for x in changes[tostrand]:
					totemp = replace(temp, i ,x)
					if(totemp in bank):
						toflag = True
						tonext.extend([totemp])
						tolevel[totemp] = tol
						if(totemp in level):
							return level[totemp]+tolevel[totemp]
					totemp = tonext_node
		if(toflag==False):
			return -1
		else:
			toflag=False
			tofrontier=tonext
			tol=tol+1


start = "AAAAAAAA"
end = "GGAAAAAA"
bank = ["GAAAAAAA","AAGAAAAA", "AAAAGAAA", "GGAAAAAA"]
print(findMutation(start, end, bank))