Find the distance between letters in the keyboard-CodePudding

I am trying to find the minimum distance between two letters in the 'qwerty' keyboard, for example if i evaluating letters q and w the minimum distance should be 1, since they are together in the keyboard, letter q and e minimum distance should be 2 since they are just two position away from each

I was trying to create a dictionary for doing like

coords = {
    'qw':1, 'qe':2, 'qr':3, 'qt':4, 'qy':5, 'qu':6, 'qi':7, 'qo':8, 'qp':9, 'qa':1, 'qs':2, 'qd':3, 
    'qf':4, 'qg':5, 'qh':6, 'qj':7, 'qk':8, 'ql':9, 'qz': 2, 'qx':3, 'qc':4, 'qv':5, 'qb':6, 'qn':7, 'qm':8,
    'q1':1, 'q2':1, 'q3':2, 'q4':3, 'q5':4, 'q6':5, 'q7':6, 'q8':7, 'q9':8}

for afterwards doing something like this to find the value of the minimum distance for each two letters ( in only did it for one-side pair for letter q)

sentence = 'qw'
grams = [sentence[i:i N] for i in range(len(sentence)-N 1)]
[coords[i] for i in grams]

CodePudding user response：

Instead of saving all possible pairs by hand, I think saving position of each letter and calculating distance would be much easier.

For example, q is (0, 0), w is (1, 0), a is (0, 1), and so on. First element represents X coordinate and second element represents Y coordinate, starting from upper-left.

Calculating distance from each other can be automated easily(I chose manhattan distance, and you can choose distance calculation algorithm as you want)

key_positions = {"q": (0, 0), "w": (1, 0), ...}
def dist(c1, c2):
    pos1 = key_position[c1]
    pos2 = key_position[c2]
    return abs(pos1[0] - pos2[0])   abs(pos1[1] - pos2[1])

CodePudding user response：

You can youse the find() function to find the indices of the first and second letters of your query and then calculate the difference between the indices to get the distance, like so:

text = 'qwerty'
query = 'qy'

index1 = text.find(query[0])
index2 = text.find(query[1])
distance = index2 - index1

CodePudding user response：

You can make a graph of the keys with a node for each key and an edge for each adjacency, then run BFS on the fly to get distances (or pre-compute for your dictionary if you prefer). BFS will be fast on such a small graph.