How could I detect if a character close to another character on a QWERTY keyboard?

Question

I'm developing a spam detection system and have been alerted to find that it can't detect strings like this - "asdfsdf".

My solution to this involves detecting if the previous keys were near the other keys on the keyboard. I am not getting the input (to detect spam from) from the keyboard, I'm getting it in the form of a string.

All I want to know is whether a character is one key, two keys or more than two keys away from another character.

For example, on a modern QWERTY keyboard, the characters 'q' and 'w' would be 1 key away. Same would the chars 'q' and 's'. Humans can figure this out logically, how could I do this in code?

Answer 1

You could simply create a two-dimensional map for the standard qwerty keyboard. Basically it could look something like this:

map[0][0] = 'q';
map[0][1] = 'a';
map[1][0] = 'w';
map[1][1] = 's';

and so on.

When you get two characters, you simply need to find their x, and y in the array 'map' above, and can simply calculate the distance using pythagoras. It would not fill the requirement you had as 'q' and 's' being 1 distance away. But rather it would be sqrt(1^2 + 1^2) approx 1.4

The formula would be:

• Characters are c1 and c2
• Find coordinates for c1 and c2: (x1,y1) and (x2,y2)
• Calculate the distance using pythagoras: dist = sqrt((x2-x1)^2 + (y2-y1)^2).
• If necessary, ceil or floor the result.

For example:

Say you get the characters c1='q', and c2='w'. Examine the map and find that 'q' has coordinates (x1,y1) = (0, 0) and 'w' has coordinates (x2,y2) = (1, 0). The distance is

sqrt((1-0)^2 + (0-0)^2) = sqrt(1) = 1

Answer 2

Well, let's see. That's a tough one. I always take the brute-force method and I stay away from advanced concepts like that guy Pythagoras tried to foist on us, so how about a two-dimensional table? Something like this. maybe:

+---+---+---+---+---+---+---
|   | a | b | c | d | f | s ...
+---+---+---+---+---+---+---
| a | 0 | 5 | 4 | 2 | 4 | 1 ...
| b | 5 | 0 | 3 | 3 | 2 | 4 ...
| c | 4 | 3 | 0 | 1 | 2 | 2 ...
| d | 2 | 3 | 1 | 0 | 1 | 1 ...
| f | 3 | 2 | 2 | 1 | 0 | 2 ...
| s | 1 | 4 | 2 | 1 | 2 | 0 ...
+---+---+---+---+---+---+---

Could that work for ya'? You could even have negative numbers to show that one key is to the left of the other. PLUS you could put a 2-integer struct in each cell where the second int is positive or negative to show that the second letter is up or down from the first. Get my patent attorney on the phone, quick!