Find the distance between letters in the keyboard

user_8627559 0
Viewed 62

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]
algorithm python
3 Answers

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])
user_190113380

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
user_142932740

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.

user_20410770
Related