Rapid Typing Coding Challenge

Question

The question asks for total time that will be required to type a string on a keyboard, which is represented as two dimensional matrix of characters, with one finger.

input:

2 31 
YLrJpXOygVUl6MqBIRFWuAKsH7Gw4Z8
kE0tTQdP1CcxSjamizon9e5NfvDbh32
YE0

The first line contains n and m as input denoting dimensions of the keyboard matrix.
Next n lines contain m characters each denoting the character in the keyboard.
Next line will contain a string S

output:

Explanation: The finger is initially at the first symbol of the keyboard so the time taken to press that key is 0. After that the new key is located at 1,1 so total time taken will be |1-0|+|1-0| i.e. 2 . Now the third key is located at position 1,2 so total time to move to that key will be |2-1|+|1-1| = 1 . So our answer is 3.

The string that's asked to print is in the last input line, YE0, consisting of letters from the above 2-D matrix.

The time calculation logic is:
If you are at cell (x1,y1) of the keyboard and now you want to press the key at (x2,y2) then the time taken will be |x1-x2| + |y1-y2|. You need to calculate the total time taken to type the complete string.
In case it is impossible to type the string you have to print -1.

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n,m;
    cin>>n>>m;
    unordered_map<char, pair<int, int>> map1;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++) {
            map1.insert({s[j], make_pair(i,j)});
        }
    }
    string key;
    cin>>key;
    long long total=0;
    pair<int,int> sp;
    for(int i=0;i<key.length();i++) {
        if(map1.find(key[i])==map1.end()) {
            total=-1;
            break;
        } else {
            auto it = map1.find(key[i]);
            if(i==0) sp=it->second;
            pair<int,int> p = it->second;
            total+=(abs(p.first-sp.first) + abs(p.second-sp.second));
            sp=p;
        }
    }
    cout<<total;
}

This solution is partially accepted and I am not able to figure out the edge cases for which its failing. Can somebody help me?

This reads like it's from some contest/challenge/competitive coding/hacking site. Is it? If your goal is to learn C++, you won't learn anything there. In nearly all cases, like this one, the correct solution is based on a mathematical or a programming trick. Other than that, there's nothing here that actually improves one's knowledge of C++. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Sam Varshavchik, Dec 20 '20 at 15:27
yeah, this is from coding challenge. Just wanted to know if I am missing some problem insight. This solution is not working for few of the test cases like its giving wrong output. And I am not able to figure out those cases. Thanks for the tip though. — Mudassir Hussain, Dec 20 '20 at 15:33
Please explain your code. Write comments, rename your variables, describe semantics. explain methods . If you do that consistently you might already find your problem. Otherwise it will help others to help you finding your problem. Please understand that "Here is my code. Why does it not work?" is often considered not to be a question here. You need to do some explaining. Being able to do that is often perceived as the difference between learning code from challenges and otherwise. — Yunnosch, Dec 20 '20 at 15:35
After reading in the keymatrix and the integers, did you output it again to verify that it is looking as expected? Did you output the partial distances to verify they look like expected? What tests did you use? Only the examples from the challenge? If not, which test cases did you come up with yourself? — Yunnosch, Dec 20 '20 at 15:38
If you know the failing examples, walk through the problem by hand with those examples to see how/why they are not matching what you expect. — Jason Peacock, Dec 20 '20 at 15:38
@jpeacock With those challenges, most of the tests are not disclosed. — Yunnosch, Dec 20 '20 at 15:40

score 1 · Answer 1 · answered Dec 20 '20 at 15:45

Here is one failing test case for free.

2 31 
YLrJpXOygVUl6MqBIRFWuAKsH7Gw4Z8
kE0tTQdP1CcxSjamizon9e5NfvDbh32
YE 0

Should be -1 because the blank is not in the key matrix.
It fails because you only read in the "word" until first whitespace.

Here is another one:

2 31 
YLrJpXOygVUl6MqBIRFW AKsH7Gw4Z8
kE0tTQdP1CcxSjamizon9e5NfvDbh32
Y E0

Shoudl not be -1, but is. Same problem, but with the matrix.

So what you need to do is change your input reading to include white space.

score 0 · Answer 2 · answered Jan 06 '21 at 08:44

It's mentioned in the question that, "The finger is initially at the first symbol of the keyboard" so when you are parsing the key In your code if(i==0) sp=it->second; should start from {0,0} to consider the movement from the first symbol of the keyboard to the first symbol of the key.

Rapid Typing Coding Challenge

2 Answers2