C++ Code for Antikythera Mechanism (TCS Codevita) | PrepInsta

November 28, 2023

Antikythera Mechanism

TCS CodeVita is a coding competition organized by TCS every year, in search of world’s best coder. This is a global level coding competition in which coders from all around the world compete for the title of World’s Best Coder. Antikythera Mechanism is one of the sample problem of this year TCS CodeVita season 11 competition.

Question -: During expedition in the shipwreck near coast an archaeologist found an artefact with gears inside it.Later it was referred as Antikythera Mechanism.
You got the X-ray of the mechansim. From that you found it has lot of gears coupled in complicated ways.To understand the working of this mechanism you are going to study the effects of gears in action.
You will be given the position and size of each gear in order. Find how many times does the last gear rotate for each time the first gear rotates. It is not necessary that all the gears coupled to the first one including the last one.
The gear details will be given like
X Y Rr
X,Y = > coordinates of the centre of the gear
Rr => The reference radius of the gearA gear will rotate another gear if the imaginative circles made by the radius Rr from their respective centres touch externally at a point.
Now consider a gear chain of N gears. Also consider gear 1 with Rr of r1 units, gear 2 of r2 units, gear 3 of r3 units and so on.The relation between Rr and rotation is given by
n1 * r1 = n2 * r2
where n1 is the number of times the gear 1 rotates and n2 is the number time gear 2 rotates.
n2 can be calculated using the formula
n2 = ( n1 * r1 ) / r2
now continuing for gear 2 and gear 3
=> n2 * r2 = n3 * r3
we can calculate n3 no of times the third gear will rotate, using
=> n3 = ( n2 * r2 ) / r3
By substituting the value calculated for n2 one can calculate n3 i.e. no of times gear 3 rotates with respect to n1. If we continue like this till the last gear. one can calculate the nN i.e. no of times the gear N rotates given n1 i.e number of rotations of gear 1.
At every step the direction of rotation will change. If gear 1 is rotating clockwise direction then gear 2 will rotate in anti clockwise direction. If gear 1 and gear N rotate in same direction, print the output as postive integer. else negative integer.
The possible cases where processing fails are as follows

the Gear 1 and Gear N gears connect to two or more other gears
the Gear 1 or Gear N are not connected any gear
Any gear in the chain between Gear 1 and Gear N are connected to more than two gears
Any gear in the chain between Gear 1 and Gear N is connected to less than two gears

You will be given N gears. It may consist of Gear chain between Gear 1 and Gear N and may also have gears which is not a part of the gear chain.
If gear chain exist between Gear 1 and Gear N, then
print the no of times the Gear N rotates. this number can be positive or negative depending on direction as explained earlier
Else print “Could Not Process”

Constraints
0 < N < 50
0 < X < 100
0 < Y < 100
0 < Rr < 10

Input
First line contains an integer N which gives the total number of gears
Next line will have the three integers X Y Rr seperated by space representing gear details as mentioned above
The Input may consists of gears that is not in the gear chain between Gear 1 and Gear N.
Gears will not overlap each other.

Output
Print single float value upto two decimal places denoting the number of times the Gear N will rotate if Gear 1 rotates one time. else print “Could Not Process”

Time Limit (secs)
1

Examples

Example 1
Input
4
1 1 1
4 1 2
1 4 1
4 4 1
Output
1.00
Explanation
Input consist of 4 gears. X Y co ordinates and the Reference radius is provided in the input.
Upon computation it is clear that a chain of gear exist between Gear 1 and Gear 4. The Gear chain would be Gear 1, Gear 2 and Gear 4.
The Gear 1 is connected directly to the Gear 2. Here Rr of Gear 1 is 1 and the Rr of Gear 2 is 2.So given gear 1 is rotated 1 time in clockwise direction, gear 2 will rotate 0.5 time in anticlockwise direction. Next the Gear 2 is connected to Gear 4 i.e. Gear N. Gear 2 rotating 0.5 time in anti clockwise direction will make Gear 4 rotate 1 time in clockwise direction bcoz of reference radius of Gear 4 is 1. Since Gear 4 and Gear 1 both rotating in same direction, the output is a positive number. Since Gear 4 rotation is 1 the output has to be printed 1.00. Note that Gear 3 is not in the gear chain between Gear 1 and Gear 4.

Example 2
Input
5
4 9 2
7 9 1
9 9 1
7 7 1
6 4 1
Output
Could Not Process
Explanation
Gear 1, Gear 3 and Gear 4 are connected to Gear 2. This violates the criteria and since there is no other gear chain that can reach from Gear 1 to Gear 5 without constraint violation, output should be printed as “Could Not Process”.

C++

Run

#include < iostream>
#include < vector>
#include < cmath>

using namespace std;

struct Gear {
    double x, y, rr;
};

double calculateRotation(const vector< Gear>& gears, int n) {
    vector< double> rotations(n, 0.0);

    for (int i = 0; i < n - 1; ++i) {
        rotations[i + 1] = rotations[i] + (M_PI * gears[i].rr) / gears[i + 1].rr;
    }

    return rotations.back();
}

int main() {
    int n;
    cin >> n;

    vector< Gear> gears(n);

    for (int i = 0; i < n; ++i) {
        cin >> gears[i].x >> gears[i].y >> gears[i].rr;
    }

    // Check if Gear 1 is connected to only one other gear and Gear N is connected to only one other gear
    if ((gears[0].rr == 0) || (gears[n - 1].rr == 0) || (gears[0].rr == 0 && gears[n - 1].rr == 0)) {
        cout << "Could Not Process" << endl;
        return 0;
    }

    // Check if any gear in the chain between Gear 1 and Gear N is connected to more or less than two gears
    for (int i = 1; i < n - 1; ++i) {
        if (gears[i].rr == 0 || (gears[i - 1].rr == 0 && gears[i + 1].rr == 0)) {
            cout << "Could Not Process" << endl;
            return 0;
        }
    }

    // Calculate rotations
    double result = calculateRotation(gears, n);

    // Check the direction of rotation and print the result
    if ((gears[0].rr > 0 && gears[n - 1].rr > 0) || (gears[0].rr < 0 && gears[n - 1].rr < 0)) {
        cout << fixed << result << endl;
    } else {
        cout << fixed << -result << endl;
    }

    return 0;
}