Project Euler #79: Passcode derivation

Sort by

recency

|

11 Discussions

|

  • + 0 comments

    C++ Solution

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() 
    {        
        int t;
        cin >> t;            
            
        vector<unordered_set<char>> after(127), before(127);
        vector<string> b_str(127), a_str(127);
        set<char> characters;
        
        for(int i=0; i<t; i++)
        {
            string s;
            cin >> s;
            
            for(int j=0; j<3; j++)
            {            
                characters.insert(s[j]);
                
                for(int k=0; k<3; k++)
                {
                    if(j == k) continue;
                    
                    if(k < j) 
                    {
                        before[s[j]].insert(s[k]);
                        after[s[k]].insert(s[j]);
                    }
                    if(k > j) 
                    {
                        after[s[j]].insert(s[k]);
                        before[s[k]].insert(s[j]);
                    }
                }
            }
        }
    
        for(auto c : characters)    
        {                
            for(auto b : before[c])
            {
                for(auto a : after[c])
                {
                    before[a].insert(b);
                    after[b].insert(a);
                    
                    for(auto x : after[a])
                    {
                        before[x].insert(c);
                        before[x].insert(b);
                        after[c].insert(x);
                        after[b].insert(x);
                    }           
                }
            }
            if(before[c].count(c) || after[c].count(c)) 
            {
                cout << "SMTH WRONG";
                return 0;
            }
        }        
        
        vector<vector<int>> possible(127);
        vector<vector<char>> index(characters.size());
        
        for(auto c : characters)
        {        
            for(int i = before[c].size(); i < characters.size() - after[c].size(); i++)
            {
                index[i].push_back(c);
            }
            for(auto it : before[c])
            {
                b_str[c].push_back(it);
            }
            for(auto it : after[c])
            {
                a_str[c].push_back(it);
            }
        }    
        bool used[127] = {0};
        string ans;
        
        for(int i=0; i<characters.size(); i++)
        {
            sort(index[i].begin(), index[i].end());
            
            for(auto it : index[i])
            {
                if(b_str[it].find_first_not_of(ans) != string::npos)
                {
                    continue;
                }
                if(!used[it])
                {
                    used[it] = 1;
                    ans += it;
                    break;
                }
            }
        }
        cout << ans;
        return 0;
    }
    
  • + 0 comments

    This is how I solve this challenge. I uses a topological sorting approach to recover the shortest possible secret passcode based on the given login attempts. How it works:

    Character Set: First, it extracts all unique characters from the login attempts and stores them in the chars set.

    Graph Construction: It constructs a directed graph where each character is a node, and there is a directed edge from character a to character b if a comes before b in any login attempt.

    In-Degree Calculation: It calculates the in-degree of each node, representing the number of characters that should come before it.

    Topological Sorting: It performs a topological sort on the graph. Starting with characters that have an in-degree of zero, it adds them to the result in lexicographically sorted order. It updates in-degrees and continues the process until all characters are processed.

    Result and Validity Check: The final result is the lexicographically smallest order of characters that satisfies the given login attempts. It also checks if there is a unique topological order. If any character has a non-zero in-degree at the end, it indicates an issue, and the result is "SMTH WRONG."

    This approach ensures that the recovered passcode is the shortest and lexicographically smallest possible, and it handles cases where there is ambiguity or inconsistencies in the login attempts.

  • + 0 comments

    I solved this problem using mathematica and graph theory, too bad I can't use it here..

  • + 0 comments

    My code is not pretty, but it worked, and despite being O(v^3) where v is the number of distinct characters in the logins, it's fast --- all testcases run in 0.05 s or less.

  • + 3 comments

    Solved this problem in O(T log T). For those seeking hints: one can look at this problem as being a graph problem, in which each letter is a Node and "letter X has to occur before letter Y in the passcode" is a directed edge from X to Y. You can then repeatedly take the lexicographically smallest letter with in-degree zero (this will be the next letter in the passcode) and remove it from the graph. If there is no letter with in-degree zero, then something is wrong. By using the right data structures, you can do this in O(E log E) where E is the number of edges in the graph.

    Let me know if you solved this problem in a completely different way, I'm curious!