BA5G.py

"""
https://www.youtube.com/watch?v=We3YDTzNXEk&ab_channel=TusharRoy-CodingMadeSimple
"""

def edit_distance(X, Y):
  n = len(X)
  m = len(Y)

  dp = []
  for i in range(m+1):
    small = []
    for j in range(n+1):
      small.append(100000000)
    dp.append(small)

  dp[0][0] = 0
  n += 1
  m += 1
  
  for i in range(1, n):
    dp[0][i] = i
  for i in range(1, m):
    dp[i][0] = i

  X = "U" + X
  Y = "U" + Y
  for i in range(1, m):
    for j in range(1, n):
      if Y[i] == X[j]:
        dp[i][j] = dp[i-1][j-1]
      else:
        mn = min(dp[i][j-1], dp[i-1][j])
        dp[i][j] = min(dp[i-1][j-1], mn) + 1

  return dp[m-1][n-1]

if __name__ == "__main__":
  X = "TGGAGCCATGGAAATGAGCCCTAAAGACTTCGGTCGCGTGAGGCAGCCGCTGCGTTATTCTTAGTACGCTTACCTAAGGCGTAATCTATACACACTAGCGTCCGCGCATTGGCGCCAGGATTGTGCCTGACGTAACTATACTGCTGGTACACACCGAGCGACCGTCTCACCCAAAAACATTCGATCGATGGCACGTGATACGCTTGTAAAGTAGAGTGGCGTAGGAGTTTGCCAGTAAATAAAGAGAGTAGTCGCAATCCCATCAATAGGTATTCCGGCTAACATAGTAAGAGGCCATGCCCTGTCTTGATCAAATAACGCATATGTAACAGAGAGACTAAGCAGTAGAGGTGGTCTCCGCTGGTCCGGATTGGTTACGCGACATTAGACCGCAGGTCTAGGCGCAGTTATCGACGACGAAATTGAATGAGCGACCTTTATGTAGCTGGCGAGCTAGGCGACTGTAGCTGGAGTGCGTAGGTGGTTATGGTCCCGGTGGCCTTGGTACACACATAAACTTTTTAAGCCTACCACCAAAACATTAACACAGCGAGCGAAGGGATTATAGAGTTATACCCTATTACGTGTCCGGATTTTCTGGTTGGTCTAATGAACTAGTGATATGGATGAACCTGCGAACTCGCGACTCCCCTTGCGTCGGCTAATATAGGATGGCGACCCTTCAGGAGGTATTGTATATAGGTAGAAAACGTTAAGAAATTTAAACTCCAAATGATGTTGGGAGCAGAACGTCGCCTAGGTGTTTGTTGACATTCAAAAGAGGCGATGCTTGACTTCCAGCCACCCATCTGCCTGTATCCGCTCATTATCCCTCAACGATTTCAACGCGGACTTTTTAACAGGATACTGAATTTGACGTGCATCAGTTCCAGGCAAGTT"
  Y = "CGGAGCCAAATGAGCCCTAAAGAACGAGCCGCTGCGTTATTCTCACTGACACTCTAGGGTACGTCAGGGGTAATCTACACTAGCGTCCGCGCATTGCCGCCAGGAAACCATACTGTCCTAACTGGCACTCACACTGCGCAGCAGTTCGTTTGCCGTCTCCACCCAGGAGAAAACATTCGATCGTTGGCACGTAATACTCGCTTGTAAAGTAGATTGGCGTAGGGGTTTGCCAATAAATGATAAAACATGAGTACTGCCATAGTCCGGCTAACATGGTAAGGTGGGCCGAAGGCCTGTCTTGATATTGCACAAATAACTCAAACAATGTAACAGAGACACCATCCGGACCTAGAGGTGTTGGCTCGCTTCCGCGTCCGGACTGGTTACGCTTAGACCGCCGGCGTTAGCGGCGCACTTATCGATCGGATACCGACGAAAATGAAAACGAGCTACCTTTATGGAGCTGGCGGGAGTGCGCGCTAGTCCACAATAGTAGGCAAGGGAGCGCGTAGGGGTCGCGGTCGTGCTCTGCATTTTGGTACATGCGAGGCGCATAAACTAAGACGCGCATTAATCCTACCACCAAAACATTAACACAACGAGCGAAATACCGGATGTATGCCCTATTACAATTCTGATTTGATATCTGGTTGGTCTAATTATAGTGAAATGGCCCAAGGGCCTTCGCGCCCTTGCCTCGGTTATAGGATGAGCTTCTTTCGCCAGACCCTGCCTCAGGCGGCCGGCGTATTAGGTAGAAAACGTTAAACTTTGCTCTTTCAAATGATGTTGGGTGCAGGCGTCGCCTATGTTGATTATTCTATGTGGTCACGTTTTACCACTTGCTTGACTTCCAGCCACCCAATATCCTGCCTGTTTATCAACGCGGGCTTTTCGGTTACTGACGTGGCGTCAGTGCGCCAAGGCAAGTT"
  
  with open('rosalind_ba5g.txt') as file:
    f = file.read().split()
    X = f[0]
    Y = f[1]
  
  d = edit_distance(X, Y)
  print(d)