Thread: Random Password Generator

  1. #1
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    39

    Random Password Generator

    Arnab has an online account which requires him to change
    his password every month. He wants to create a program to
    help him generate the password.
    He comes up with an algorithm to generate all combinations
    of strings of a fixed length using only the starting letter and
    ending letter of his name (A & B). To randomize the password selection, he then sorts the list in
    lexicographical (ascending) order and chooses a string at a random position.
    Help Arnab implement this algorithm.
    For example:
    Consider the length of password to be 3 for which Arnab generates all the combinations of strings. He
    sorts them in ascending order and then picks a password at 2nd position.
    The sorted possible strings of length 3 with characters A and B are as follows:
    AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB
    The string at index 2 is AAB

    Input

    The first line contains the length N of the password.
    The second line contains the index M of the string to be picked from the sorted list of strings (consider the
    first item as index 1).

    Output

    Print the chosen password.

    Constraints

    0 < N < 10
    0 < M < 2^N

    Sample Input #1

    3
    2

    Sample Output #1

    AAB

    Sample Input #2

    4
    7

    Sample Output #2

    ABBA


    This is my solution but I'm not sure if this is the simplest way to achieve the end solution. Is there a better way to do this?

    Code:
    #include <iostream>
    
    
    using namespace std;
    
    
    int main()
    {
        int N , M , Total_Possibilities = 1 , temp;
    
    
        string result;
    
    
        cin >> N >> M;
    
    
        temp = N;
    
    
        while ( temp-- > 0 )
        {
            Total_Possibilities*=2;
        }
    
    
        for ( temp = 0 ; temp < N ; temp++ )
        {
            Total_Possibilities/=2;
    
    
            if ( M <= Total_Possibilities )
                result += "A";
    
    
            else
            {
                M -= Total_Possibilities;
                result += "B";
            }
        }
    
    
        cout << endl << result;
    
        return 0;
    }
    My first attempt was to use an string array of size 2^N which contains the possibilities in the proper lexicographical series and then displaying the string at the Mth position. But, as advised by @Salem in my Last Man Standing Thread to not just hop into the question for the sake of doing it but instead looking for patterns and clues behind simpler solutions, I wrote down the possibilities and figured out my current solution. This is the best I could achieve but I still have a feeling that the solution may actually be simpler. So if anyone can state it out, I might give it another try. Thanks
    Last edited by Zeus_; 4 Weeks Ago at 11:01 AM.

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    627
    The answer is just the binary representation of M - 1 given in N bits, where 0 is represented by A and 1 by B.
    Code:
    #include <iostream>
     
    int main() {
        int n, m;
        std::cin >> n >> m;
        --m;
        for (int x = 1 << n; x; x /= 2) {
            if (m / x) {
                std::cout << 'B';
                m -= x;
            }
            else
                std::cout << 'A';
        }
        std::cout << '\n';
    }
    Last edited by john.c; 4 Weeks Ago at 01:18 PM.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  3. #3
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    646
    The constraints seem wrong because they exclude the last index. Using the given example, it's not possible to pick "BBB" because that's at index 8 (M = 8), but M must be less than 8. The constraints should be:

    0 < N < 10
    0 < M <= 2^N

    (This doesn't affect your solution, though.)

  4. #4
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    39
    I haven't learnt how to do use binary representations and neither do I know what (1 << n) means but I'm definitely gonna look it up now.

    Also, even though I didn't understand the working, I copied the code and compiled it with the latest version GNU GCC and the code seems to be working fine except that when I do something like

    INPUT: 4 16 (or any other number <=16)

    OUTPUT: ABBBB (or the correct representation of the number <=16) except that the extra "A" is displayed in the front of every correct answer.

    Thanks for your solution, it gave me a new way to approach this sort of stuff

  5. #5
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    39
    Edit: I read a lot more about it in the past hour and all I can say is it's a shame we are not taught basic things like this in school. I've been learning C++ for over a year and I had no clue about this. I modified the code slightly and now it works perfectly without the extra "A". Thanks a lot!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help with password list generator
    By casper29 in forum C Programming
    Replies: 4
    Last Post: 02-12-2009, 02:23 AM
  2. Password Generator
    By My Overflow in forum C Programming
    Replies: 7
    Last Post: 11-17-2007, 05:22 PM
  3. random password generator
    By cDev in forum C Programming
    Replies: 11
    Last Post: 07-07-2006, 10:07 AM
  4. Random Password Generator v1.0 - download it
    By GaPe in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 08-18-2002, 01:27 AM
  5. Password generator
    By MrJake in forum C++ Programming
    Replies: 9
    Last Post: 02-24-2002, 11:44 PM

Tags for this Thread