Surya's Blog!

Month: January 2010

  • Finding Rank of a Word. (No Repetition)

    Finding Rank of a Word. (No Repetition)

    Finding the rank of a word
    Finding the rank of a word

    Lets first, we should know what is the RANK of a word?

    Rank of a word is the position of that word from the arrangement of letters of that given word in dictionary order. Lets see an example…this can help more in understanding the RANK of a word. Its really interesting to find rank of Word.

     

    Lets took word “RANK”

    1. How many words, can be created  using the letters of word RANK? Ans: The number of characters in word “RANK” is 4. So it will be 4! = 4*3*2*1 = 24.
    2. Now if we arrange all the 24 words formed by the letters of “RANK” in dictionary order.
    3. Then at what postion the the word “RANK” will exist?
    4. That particular position of the word, will be the rank of word “RANK”.

    Algorithm 1st:

    1. Take a word which we have to find the rank. I will take “SUNIL”.
    2. Now arrange the letter of “SUNIL” in alphabatical order.
      It will be. “I L N S U“.
    3. Now take the first letter. Its “I”. Now check, Is the letter “I” is the first letter of “SUNIL”? No.
      So the no. of word found can be formed with I will be 4!. I = 4! = 24
    4. Now go for the second letter. Its “L”. Now check once again is this letter we want in first? No.
      So. the no. of words can be formed using “L” at first will be 4!.
      L = 4! = 24
    5. Now go for “N”. Is this we want? No. Write down the number of words can be formed using word. “N” is once again 4!N = 4! = 24
    6. Now go for “S”. Is this is what we want? Yes. Now cut the letter from the alphabetically ordered word. it will be now. “I L N S U”
      Write S and check the word once again in the list.
      Is we want SI? No. so the number of words can be formed using SI at first will be. 3! [S] : I -> 3! = 6
    7. Go for L. is we want SL? No. so it will be 3!. [S] : L ->  3! = 6
    8. Go for N. is we want SN? No. [S] : N ->  3!  =  6
    9. Go for SU. Is this we want? Yes cut the word U from the list and then it will be “I L N S U“.
      Now Go for I. is we want SUI? no. so the no of word can be formed which starts from SUI will be 2! Now [SU] : I -> 2! = 2
    10. Now go for L. is we want SUL. No. so the no. of words. can be formed. SUL will be 2!. [SU] : L -> 2! = 2
    11. Now go for N. Is we want SUN? Yes now cut that letter. and this will be “I L N S U“ Is we want SUNI yes. cut that word. Then only one letter will be left.”L”.
    12. Now go for L. Is we want SUNIL yes. SUNIL words having only 1!.
    13. [SUN][I][L] = 1! = 1

    Now add the whole numbers we get. The sum will be.

    24 + 24 + 24 + 6 + 6 + 6 + 2 + 2 + 1 = 95.

    So the word SUNIL will be at 95th position if we form the whole words that can be created using the letters of SUNIL arranged in dictionary order.

    Lets check the rank of SURYA now.

    1. A R S U Y//Arranged in Alphabatical Order.
    2. A = 4! = 24 // Is A We want? No.
    3. R = 4! = 24// Is R? No.
    4. [S]:A-> 3! = 6 // Is S? Yes. Cut the word S from that list. And move to next letter. Is SA? No.
    5. [S]:R-> 3! = 6 // IS SR? No.
    6. [SU]:A-> 2! =2 //Is SU? Yes. Cut the word U from that list. And move to next letter. IS SUA? No.
    7. [SUR]:A-> 1! = 1 // Is SUR? Yes. Cut the word A From that list.
    8. [SURY][A] = 1!= 1 //Is SURY? Yes. Cut Y. Only one letter is now left “A” That will be last. Is “SURYA”? Yes.

    Now sum all that. 24 + 24 + 6 + 6 + 2 + 1 + 1 = 64.

    Shortcut Method to Find the Rank of WORD
    ( No Repetition )

    Algorithm 2nd:

    Take the Word “SURYA” once again.

    1. A R S U Y // Alphabatcal Order
    2. 2 * ( 4 ! ) = 48// Search for S. Remove that word from the list and see how many letter before S? 2 letter.
    3. 2 * ( 3 ! )  = 12 // Search for U. Remove that letter and count the letters before U now. Its 2.
    4. 1 * ( 2 ! )  = 2 // Search for R. Remove that letter and count the letters before R. Its 1.
    5. 1 * ( 1 ! )  =  1// Search for Y. Remove that letter and count the letter before Y. Its 1.
    6. Add the whole numbers. and add 1 for last letter A.
    7. Sum: 48 + 12+ 2 + 1 + 1 = 64.

    That’s all. So here we see how to find the rank of word if the word has no repetition. In the next post I will tell how to find the rank of a word if the word had repetition like in the case of INDIA. “I” is repeated  2 times.

    Edit: Link of Finding Rank in Repetition

  • Solution 2: Algorithm 1

    Solution 2: Algorithm 1

    Algorithm
    Algorithm

    Below is the solution for Algorithm Problem 1

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define PI 3.14159265358979323846

float compute_comman_area(double r0,double r1,double x0,double y0,double x1,double y1){

     double c,CBA,CAB,CBD,CAD,Area;

     //length
     c = sqrt(pow((x1-x0),2) + pow((y1-y0),2));

     //IN RADIANS
     CBA = (acos((pow(r1,2) + pow(c,2) - pow(r0,2))/(2*r1*c)));
     CAB = (acos((pow(r0,2) + pow(c,2) - pow(r1,2))/(2*r0*c)));

     CBD = 2*CBA;
     CAD = 2*CAB;

     Area = (CBD*pow(r1,2) - pow(r1,2)*sin(CBD) + CAD*pow(r0,2) - pow(r0,2)*sin(CAD))/2;

     printf("%lf", CBA);

     return Area;
}

int main(){

    double r1=10,r0=10,x0=0,y0=0,x1=0,y1=10, Area, Area0;

    //getting input
    /*printf("Enter the radius of the first circle\nand the centre point");
    scanf("%lf%lf%lf",&r0,&x0,&y0);
    printf("Enter the radius of the first circle\nand the centre point");
    scanf("%lf%lf%lf",&r1,&x1,&y1);*/

    //calling function to compute area
    Area0 = PI * pow(r0, 2) + PI * pow(r1, 2);
    Area = Area0 - compute_comman_area(r0,r1,x0,y0,x1,y1);

    //printing the area
    printf("The area thus computed is:%lf",Area);

return 0;
}

    You can download the source file here.

  • Solution Hint: Algorthimic Problem 1st (How to find the shared area of two intersected circle)

    Solution Hint: Algorthimic Problem 1st (How to find the shared area of two intersected circle)

    Algorithm Image
    Algorithm Green Image

    If you will go for the problem statement then you will find that you have to find the Area covered by intersection of two or three circles and the coordinates and radius is given.

     

     

     

    Lets see how to find the shared area between intersection of two circles.

    Let two circles are given.

    1. center(x0,y0), radius (r0)
 2. center(x1,y1), radius (r1)

    Let A be the centre of the circle ( x0, y0 ) and B be the centre of the other circle ( x1,y1 ).

    Draw the circles with appropriate radii r0 and r1 so that there is a reasonable amount of overlap.  The length AB is calculated from the coordinates of the centre:

    AB = sqrt{(x1-x0)^2 + (y1-y0)^2}

    For convenience let this length be denoted by c.

    The two circles intersect in two points which I will label C and D.

    Now we must calculate the angles CAD and CBD, and we do this using the cosine formula. In fact it is half of these angles that we first calculate, using triangle CAB.

    r0^2 = r1^2 + c^2 - 2*r1*c*cos(CBA)
    cos(CBA) = (r1^2 + c^2 - r0^2)/(2*r1*c)

    found CBA, then CBD = 2(CBA).

    Similarly,
    cos(CAB) = (r0^2 + c^2 - r1^2)/(2*r0*c)
    and then
    CAD = 2(CAB)

    Express CBD and CAD in radian measure. Then we find the segment of each of the circles cut off by the chord CD, by taking the area of the sector of the circle BCD and subtracting the area of triangle BCD.
    Similarly we find the area of the sector ACD and subtract the area of triangle ACD.

    Area = ( 1/2 )( CBD ) r1 ^ 2 - ( 1/2 ) r1 ^ 2 * sin( CBD )
  + ( 1/2 )( CAD ) r0 ^ 2 - ( 1/2 ) r0 ^ 2 * sin( CAD )

    Remember that for the area of the sectors you must have CBD and CAD in radians.

    One more thing if the two circles are of the SAME radius please note that the area is symmetrical about the chord CD. Therefore, you only need to find the area in one half of the intersection and multiply by 2.

    A shorter equation is

    Area = 2 * ( ( 1/2 ) ( CBD ) r1 ^ 2 - ( 1/2 ) r1 ^ 2.sin( CBD ) ).

    One more derivation if the redis is equal then you can find out using, this formula
    Area = r^2*(q - sin(q))  where q = 2*acos(c/2r),
    where c = distance between centers and r is the common radius.

    I think now you can solve this. If something goes wrong, then post in the comments.