Codeforces Alice's Adventures in Chess Problem in Python and C++

If you are preparing for USACO, ACSL or any other competitive programming, Codeforces is a good place to practice your programing. This article contains my Python and C++ solutions for the Alice's Adventures in Chess problem 2028A, a part of Codeforces Round 986 (Div. 2).

Alice's Adventures in "Chess" problem

Please read the Adventures in "Chess" problem on Codeforces fully. Make sure you understand the problem. Write the algorithm on paper before coding anything. For your algorithm, you can either write pseudocode or draw a flowchart.

Test cases

You can download this test case input and the expected output:

• alice_adventures_in_chess_1.in input file
• alice_adventures_in_chess_1.out output file

Programming Solution Logic

The first line of input is t, the number of test cases.

For each test case, the first line has 3 integers representing n, a, b. The second line of has a string s containing N, E, W, S.

For each of these test cases, the output is either YES or NO depending on whether the coordinates of Alice and the Red Queen are the same or not, respectively.

In our algorithm, we want to see if after all the iterations, Alice's coordinates match with Red Queen's coordinates a and b.

Our algorithm can be something like this:

Main Algorithm

1. Read the number of test cases t.
2. Start a loop for each test case.
3. Read the first line of each test case and store the integer values in n, a, b.
4. Read the second line of this test case and store the string value in s.
5. Call function do_it(a, b, s) and print the returned value

Algorithm for function do_it(a, b, s)

1. Accept a, b, s as input parameters. a and b represent Red Queen's coordinates.
2. Initialize x and y to 0. These represent Alice's coordinates.
3. Start a loop that reads every letter in s into the variable direction.
4. If direction equals to 'N', you have to travel 1 up, so increment y.
5. Elseif direction equals to 'S', you have to travel 1 down, so decrement y.
6. Elseif direction equals to 'E', you have to travel 1 right, so increment x.
7. Elseif direction equals to 'W', you have to travel 1 left, so decrement x.
8. If x equals to a and y equals to b, it means that Alice is on the same coordinate as Red Queen. Return 'YES' if they match. Or else, go to the next step.
9. Go back to (2) and continue until all test cases are complete.
10. Repeat the loop (2) through (6) 50 times*
11. Return 'NO' if you have come this far. It means that Alice and the Red Queen will never be at the same coordinates.

* The problem says forever, but 50 should be enough.

We will look at the test cases in the the input file alice_adventures_in_chess_1.in and compare the answers to the ones in the output file alice_adventures_in_chess_1.out .

First Test Case

2 2 2
NE

Here, n = 2, a = 2, b = 2.

The string s = 'NE'. In two iterations, Alice's coordinates will be (2, 2). So, it will return YES.

Second Test Case

3 2 2
NNE

Here, n = 3, a = 2, b = 2.

The string s = 'NNE'. Even after 50 iterations, Alice's coordinates will never be (2, 2). So, it will return NO.

For all the 6 test cases, our algorithm will give the correct expected output.

Install Python or C++

If you do not have Python or C++, you should first install it. Codeforces uses Python 3.8 for evaluating your code. If you are using C++, they have versions 17 and 20.

My Python solution

alice_adventures_in_chess.py

'''
Codeforces Round 986 (Div. 2)
Problem : https://codeforces.com/contest/2028/problem/A
Solution: https://aruljohn.com/blog/alice-adventures-in-chess-problem/
'''

def do_it(a, b, s):
    x, y = 0, 0
    for _ in range(50):
        for direction in s:
            if direction == 'N':
                y += 1
            elif direction == 'S':
                y -= 1
            elif direction == 'E':
                x += 1
            elif direction == 'W':
                x -= 1
            if x == a and y == b:
                return 'YES'
    return 'NO'

t = int(input())
for _ in range(t):
    n, a, b = list(map(int, input().split()))
    s = input()
    print(do_it(a, b, s))

Running the Python code

Run the Python code from your Terminal. I am using macOS, but you can use any Linux-based OS as well.

Here, I am running the program, which reads the input file with 4 test cases. Later, I also viewed the contents of the output file to compare the results.

$ cat alice_adventures_in_chess_1.in  | python alice_adventures_in_chess.py 
YES
NO
YES
YES
YES
NO

$ cat alice_adventures_in_chess_1.out 
YES
NO
YES
YES
YES
NO

My C++ solution

alice_adventures_in_chess.cpp

This is my C++ solution:

/*
Codeforces Round 986 (Div. 2)
Problem : https://codeforces.com/contest/2028/problem/A
Solution: https://aruljohn.com/blog/alice-adventures-in-chess-problem/
*/

#include <iostream>
#include <vector>

using namespace std;

// Return YES or NO
string do_it(int a, int b, string s) {
    int x, y;
    x = y = 0;
    for (int i=0; i < 50; i++) {
        for (int j=0; j < s.length(); j++) {
            switch(s[j]) {
                case 'N':
                    y++; break;
                case 'S':
                    y--; break;
                case 'E':
                    x++; break;
                case 'W':
                    x--; break;
                default:
                    break;
            }
            // Check if they are on the same coordinate
            if (x == a && y == b) {
                return "YES";
            }
        }
    }
    return "NO";
}

// Main function
int main() {
    int t;
    cin >> t;

    for (int i=0; i < t; i++) {
        int n, a, b;
        string s;
        cin >> n >> a >> b;
        cin >> s;
        cout << do_it(a, b, s) << "\n";
    }
}

In the C++ code, we used the same logic.

Running the C++ code

Compile the C++ code from your Terminal. This command creates a.out.

$ g++ alice_adventures_in_chess.cpp

Now, run the test cases against a.out.

$ cat alice_adventures_in_chess_1.in | ./a.out 
YES
NO
YES
YES
YES
NO

$ cat alice_adventures_in_chess_1.out 
YES
NO
YES
YES
YES
NO

Submit your code

Submit your Python code and C++ code to Codeforces. When your code successfully passes all test cases, you will get a green "Accepted" message with the time taken.

Which is faster?

In the Codeforces submission page, these were the results:

Python 3        -- Time taken: 93 ms
GNU C++23 (64)  -- Time taken: 46 ms

The C++ program was 47 ms faster. This may vary on your submissions because this depends on how busy the server was at the time of submission.

What about software design, conventions and standards?

This is competitive programming. The goal is to complete the program with minimum effort and maximum efficiency. Using single character variables and ugly formatted code are okay, as long as the program runs and runs well within the scope. That is fine, as long as your program works and you are able to submit it.

Later in life, when you start working in a professional environment, please beautify your ugly code, follow conventions, add comments and make your code readable. Readability and maintainability is key if you want to be a successful software engineer.

Conclusion

If there is anything you would like me to add to this article, feel free to comment below or contact me. Thanks.

Related Posts

If you have any questions, please contact me at arulbOsutkNiqlzziyties@gNqmaizl.bkcom. You can also post questions in our Facebook group. Thank you.