Psionicist: Memoized-dekoratorn var trevlig, jag har knappt använt mig av dekoratorer innan, men det verkar finnas anledning att börja. Koden vart mycket tydligare.
Jag hoppas att du inte misstycker, men jag jagade ut buggarna ur din kod. Det handlade om två problem:
1. solution_X[i, j] där i eller j är 0 blir inte '' utan motsvaras ju av ett antal tecken från den ena strängen och samma mängd "gaps" från den andra.
2. Eftersom solution_X[1, 1] gäller lösningen för de två första tecknen så måste lösningen för alla vara solution_X[len(A), len(B)], som det var tidigare hoppades det sista tecknet över.
def needleman_wunsch(A, B, matrix, gap):
score = {}
solution_A = {}
solution_B = {}
Al, Bl = len(A), len(B)
solution_A[0, 0] = ''
solution_B[0, 0] = ''
score[0, 0] = 0
for i in range(1, Al+1):
score[i, 0] = i * gap
solution_A[i, 0] = solution_A[i-1, 0] + A[i-1]
solution_B[i, 0] = '-' * i
for j in range(1, Bl+1):
score[0, j] = j * gap
solution_A[0, j] = '-' * j
solution_B[0, j] = solution_B[0, j-1] + B[j-1]
for i in range(1, Al+1):
for j in range(1, Bl+1):
s1 = score[i-1, j-1] + matrix[A[i-1], B[j-1]]
s2 = score[i-1, j] + gap
s3 = score[i, j-1] + gap
if max(s1, s2, s3) == s1:
score[i, j] = s1
solution_A[i, j] = solution_A[i-1, j-1] + A[i-1]
solution_B[i, j] = solution_B[i-1, j-1] + B[j-1]
elif max(s1, s2, s3) == s2:
score[i, j] = s2
solution_A[i, j] = solution_A[i-1, j] + A[i-1]
solution_B[i, j] = solution_B[i-1, j] + '-'
else:
score[i, j] = s3
solution_A[i, j] = solution_A[i, j-1] + '-'
solution_B[i, j] = solution_B[i, j-1] + B[j-1]
return solution_A[Al, Bl], solution_B[Al, Bl]
