DEV Community: Rishit Chaudhary

Learning Rust (Part 1 of N)

Rishit Chaudhary — Mon, 09 Aug 2021 14:55:53 +0000

I recently started reading up about the Rust programming language. I've read a lot of cool stuff about it, and I've decided to blog my journey through the process of learning Rust.

As far as I've read, Rust follows a completely different model, with regards to sharing of variables, with the concept of owner, borrowing and shared borrows. It also statically checks programs for memory leaks and data race conditions, so you know your program is free of such insidious bugs, if it compiles successfully.

I've read that it also gives pleasant helpful error messages. I've dealt with and diagnosed long error logs such as template meta-programming bugs in C++, so I have firsthand experience in being at the receiving end of the compiler vomiting volumes of information at you. I'm curious to see how the Rust compiler's error messages are in terms of their description and accuracy.

So, at the outset, I've set my learning path as follows:

I plan to go through each resource sequentially, while also solving all the exercises in each one. I estimate that this whole process would take me about 6 months.

As any curious reader would notice, I've not mentioned the primary resource for Rust: The Book. I plan to keep this resource as my main reference as I go through the learning process.

Update: (11/08/2021)
As noted out by @vorfeedcanal , the book The Rust Programming Language (Covers Rust 2018)
by Steve Klabnik and Carol Nichols is actually the printed version of The Book.

I've decided to refer the The Book, as being the web version, it will be continually updated.

You can find more details about this here.

How do I Apply What I Learn?

As I start off, I plan to apply what I learn in solving competitive programming questions on CodeForces. I've solved question from there before, and written 2 blogs on them as well, here on dev.to.

I'll restart blogging about solving CodeForces questions, but I'll switch my language from Modern C++ to Rust, so that I can really dive into learning this new language.

In addition, solving the questions and exercises in the different material I read, will be important. I'll maintain a GitHub repository for each resource I work on, to keep everything in sync.

So When Do I Start?

I have already started working through the Microsoft Developer series on YouTube, which I plan to finish a little more than halfway by August 19th, Thursday. I'll add another blog post then, to update my progress and share what I learnt.

Onwards and Upwards! ...

Solving Codeforces Problem: 136A - Presents

Rishit Chaudhary — Wed, 23 Jun 2021 14:45:17 +0000

Today we are going to attempt to solve the Codeforces problem: 136A - Presents. Alright! so let's begin.

The Question
My Analysis with Sample Examples
Code and Complexity
Links and References

The Question

Problem Statement

Little Petya very much likes gifts. Recently he has received a new laptop as a New Year gift from his mother. He immediately decided to give it to somebody else as what can be more pleasant than giving somebody gifts. And on this occasion he organized a New Year party at his place and invited n his friends there.

If there's one thing Petya likes more that receiving gifts, that's watching others giving gifts to somebody else. Thus, he safely hid the laptop until the next New Year and made up his mind to watch his friends exchanging gifts while he does not participate in the process. He numbered all his friends with integers from 1 to n. Petya remembered that a friend number i gave a gift to a friend number pi. He also remembered that each of his friends received exactly one gift.

Now Petya wants to know for each friend i the number of a friend who has given him a gift.

Input

The first line contains one integer n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party. The second line contains n space-separated integers: the i-th number is pi — the number of a friend who gave a gift to friend number i. It is guaranteed that each friend received exactly one gift. It is possible that some friends do not share Petya's ideas of giving gifts to somebody else. Those friends gave the gifts to themselves.

Output

Print n space-separated integers: the i-th number should equal the number of the friend who gave a gift to friend number i.

My Analysis with Sample Examples

Now, before discussing the solution, I first need to address a mistake in the description in the input of the question as given on Codeforces. In the input description, it says that:

the i-th number is pi — the number of a friend who gave a gift to friend number i.

This is not how the input is given in the various test cases. On closer inspection this is very similar to the description of the expected output of the questions:

i-th number should equal the number of the friend who gave a gift to friend number i.

So, now the natural question you'll be asking is "What exactly is the input format?"

If we re-examine the description of the Problem Statement above, we see the line:

He numbered all his friends with integers from 1 to n. Petya remembered that a friend number i gave a gift to a friend number pi.

Eureka! This is the correct description of the input format! We can verify this as well with the given sample examples. Let's try that now.

Example-1

Input

4
2 3 4 1

Here, on the first line we are given that Petya invited 4 friends to the party (I sincerely hope none of his friends got left out 😅), and on next line we are given a list of numbers that needs to be interpreted as follows (Notice: The numbers in bold are the ones visible in the input, in that order):

Friend 1 gave a present to Friend 2
Friend 2 gave a present to Friend 3
Friend 3 gave a present to Friend 4
Friend 4 gave a present to Friend 1

Alright, so now what we need to do is to output a list of numbers such that at the i-th position we give the number of the friend who gave a present to friend i.

So our output should be:

4 1 2 3

Which should be interpreted as (Notice: The numbers in bold are the ones visible in the output, in that order):

Friend 4 gave a present to Friend 1
Friend 1 gave a present to Friend 2
Friend 2 gave a present to Friend 3
Friend 3 gave a present to Friend 4

Output

4 1 2 3

Example-2

Input

3
1 3 2

Here, on the first line we are given that Petya invited 3 friends to the party, and on next line we are given a list of numbers that needs to be interpreted as follows (Notice: The numbers in bold are the ones visible in the input, in that order):

Friend 1 gave a present to Friend 1
Friend 2 gave a present to Friend 3
Friend 3 gave a present to Friend 2

Alright, so other than the fact that Friend 1 doesn't seem to have the New Year spirit, what we need to do is to output a list of numbers such that at the i-th position we give the number of the friend who gave a present to friend i.

So our output should be:

1 3 2

Which should be interpreted as (Notice: The numbers in bold are the ones visible in the output, in that order):

Friend 1 gave a present to Friend 1
Friend 3 gave a present to Friend 2
Friend 2 gave a present to Friend 3

Output

1 3 2

Example-3

Input

2
1 2

Here, on the first line we are given that Petya invited 2 friends to the party, and on next line we are given a list of numbers that needs to be interpreted as follows (Notice: The numbers in bold are the ones visible in the input, in that order):

Friend 1 gave a present to Friend 1
Friend 2 gave a present to Friend 2

Alright, so other than the fact that Friend 1 and Friend 2 should starting asking themselves why they came with presents to the party, what we need to do is to output a list of numbers such that at the i-th position we give the number of the friend who gave a present to friend i.

So our output should be:

1 2

Which should be interpreted as (Notice: The numbers in bold are the ones visible in the output, in that order):

Friend 1 gave a present to Friend 1
Friend 2 gave a present to Friend 2

Output

1 2

Code and Complexity

Alright, so now we know how to interpret out input and process it to get our output. To be extra sure we have also verified our logic over the given examples as well. Let's now translate this logic into code. For this I'll be using modern C++ (C++11 and beyond), so that it's easier to get the big picture logic which is implemented in the code.

Another interesting reason to use modern C++ is that some of its features make the code more readable and similar looking to Python code (many people consider this a plus).

/**
 * @file 136A-Presents.cpp
 * @author Rishit Chaudhary (@rishitc)
 * @version 1.0
 * @date 2021-06-23
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    int p;

    std::cin >> n;

    int ans[n];

    for (int i = 1; i < n + 1; ++i)
    {
        std::cin >> p;

        ans[p - 1] = i; // Zero index correction for p
    }

    for (int i = 0; i < n; ++i)
    {
        std::cout << ans[i] << " ";
    }
    std::cout << "\n";
}

Complexity

Complexity Type	Answer	My Comments
Time Complexity	O(n)	n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party.
Space Complexity	O(n)	n (1 ≤ n ≤ 100) — the quantity of friends Petya invited to the party.
Difficulty (subjective value)	Easy	The use of language in the question combined with the mistake in the description of the input does make the question a bit hard to grasp at first.

Links and References

Link to the problem: https://codeforces.com/problemset/problem/136/A
Link to my submission: https://codeforces.com/contest/136/submission/120021060
Link to the solution at my GitHub Repository: https://github.com/rishitc/Codeforces-Codes/blob/main/136A-Presents.cpp

Solving Codeforces Problem: 467A - George and Accommodation

Rishit Chaudhary — Sat, 19 Jun 2021 16:08:21 +0000

Today we are going to attempt to solve the Codeforces problem 467A - George and Accommodation. Alright! so let's begin.

The Question
My Analysis with Sample Examples
Code and Complexity
Links and References

The Question

Problem Statement

George has recently entered the BSUCP (Berland State University for Cool Programmers). George has a friend Alex who has also entered the university. Now they are moving into a dormitory.

George and Alex want to live in the same room. The dormitory has n rooms in total. At the moment the i-th room has pi people living in it and the room can accommodate qi people in total (pi ≤ qi). Your task is to count how many rooms has free place for both George and Alex.

Input

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of rooms.

The i-th of the next n lines contains two integers pi and qi (0 ≤ pi ≤ qi ≤ 100) — the number of people who already live in the i-th room and the room's capacity.

Output

Print a single integer — the number of rooms where George and Alex can move in.

My Analysis with Sample Examples

Now, as per the question we need to check if a room, say ri has enough space left for 2 people, i.e. George and Alex. So putting this in the form of a condition, we get (assuming we start counting the rooms from 1):

qi - pi ≥ 2, ∀ i ∈ [1, n]

Now let's try out our logic on the examples given in the problem:

Example-1

Input

3
1 1
2 2
3 3

Here, it's clearly visible that each and every room in the dormitory is full, so there is no space for our two friends 😢. Hence the answer will be 0.

Output

0

Example-2

Input

3
1 10
0 10
10 10

Here, we see that the first room with capacity 10 and number of occupants 1, and the second room with capacity 10 and number of occupants 0 have more than enough space for our 2 friends 😊. Great! So that gives us the answer of 2 rooms in the dormitory.

Output

2

Code and Complexity

Alright, so now we know mathematically what we need to check for each room in the dormitory and we have verified our logic over the examples as well. Let's now translate this logic into code. For this I'll be using modern C++ (C++11 and beyond), so that it's easier to get the big picture logic which is implemented in the code.

Another interesting reason to use modern C++ is that some of its features make the code more readable and similar looking to Python code (many people consider this a plus).

/**
 * @file 467A-George_and_Accommodation.cpp
 * @author Rishit Chaudhary (@rishitc)
 * @version 1.0
 * @date 2021-06-19
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>

int main()
{
    int n;
    int p, q;
    int count{0};
    const int Space_for_George_and_Alex{2};

    std::cin >> n;

    while (n--)
    {
        std::cin >> p >> q;

        if (q - p >= Space_for_George_and_Alex)
        {
            ++count;
        }
    }

    std::cout << count << "\n";
}

Complexity

Complexity Type	Answer
Time Complexity	O(n)
Space Complexity	O(1)
Difficulty (subjective value)	Easy

Links and References

Link to the problem: https://codeforces.com/problemset/problem/467/A
Link to my submission: https://codeforces.com/contest/467/submission/120009560
Link to the solution at my GitHub Repository: https://github.com/rishitc/Codeforces-Codes/blob/main/467A-George_and_Accommodation.cpp

DEV Community: Rishit Chaudhary

Learning Rust (Part 1 of N)

How do I Apply What I Learn?

So When Do I Start?

Solving Codeforces Problem: 136A - Presents

Table Of Contents

The Question

Problem Statement

Input

Output

My Analysis with Sample Examples

Example-1

Input

Output

Example-2

Input

Output

Example-3

Input

Output

Code and Complexity

Complexity

Links and References

Solving Codeforces Problem: 467A - George and Accommodation

Table Of Contents

The Question

Problem Statement

Input

Output

My Analysis with Sample Examples

Example-1

Input

Output

Example-2

Input

Output

Code and Complexity

Complexity

Links and References