keyboard = ["QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"] ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" inf = 1000000 def manhattan_distance(x1, y1, x2, y2): distance = abs(x1 - x2) + abs(y1 - y2) return distance def compute_distances(): dist = {} for letter in "ABCDEFGHIJKLMNOPQRSTUVWXYZ": dist[letter] = {} for x1, line1 in enumerate(keyboard): for y1, letter1 in enumerate(line1): for x2, line2 in enumerate(keyboard): for y2, letter2 in enumerate(line2): dist[letter1][letter2] = manhattan_distance(x1, y1, x2, y2) return dist dist = compute_distances() sequence = input() sequence = sequence.upper() d = [] d.append({}) for letter in ALPHA: d[0][letter] = {} for let1 in ALPHA: for let2 in ALPHA: d[0][let1][let2] = inf d[0]['F']['J'] = 0 for char in sequence: newD = {} for letter in ALPHA: newD[letter] = {} for let1 in ALPHA: for let2 in ALPHA: newD[let1][let2] = inf # left index prevD = d[-1] for let1 in ALPHA: for let2 in ALPHA: if prevD[let1][let2] != inf: newD[char][let2] = min(newD[char][let2], prevD[let1][let2] + dist[let1][char]) # right index prevD = d[-1] for let1 in ALPHA: for let2 in ALPHA: if prevD[let1][let2] != inf: newD[let1][char] = min(newD[let1][char], prevD[let1][let2] + dist[let2][char]) d.append(newD) answer = inf lastD = d[-1] for let1 in ALPHA: for let2 in ALPHA: if lastD[let1][let2] < answer: answer = lastD[let1][let2] print(answer)