Project Euler #79: Passcode derivation

Sort by

recency

|

12 Discussions

|

  • + 0 comments

    This is perfect python code : 100%

    class DirectedGraph:
        def __init__(self):
            self.graph = {}
    
        def add_node(self, node):
            """Add a node to the graph."""
            if node not in self.graph:
                self.graph[node] = []
    
        def add_edge(self, from_node, to_node):
            """Add a directed edge from 'from_node' to 'to_node'."""
            if from_node not in self.graph:
                self.add_node(from_node)
            if to_node not in self.graph:
                self.add_node(to_node)
            self.graph[from_node].append(to_node)
    
        def get_neighbors(self, node):
            """Return a list of neighbors (outgoing edges) for a given node."""
            if node not in self.graph:
                return []
            return self.graph[node]
    
        def get_no_incoming_nodes(self):
            """Return a list of nodes with no incoming edges."""
            all_nodes = set(self.graph.keys())
            nodes_with_incoming = set()
            
            for neighbors in self.graph.values():
                for neighbor in neighbors:
                    nodes_with_incoming.add(neighbor)
            
            return sorted(list(all_nodes - nodes_with_incoming))
    
        def remove_node(self, node):
            """Remove a node and all edges connected to it (both incoming and outgoing)."""
            if node in self.graph:
                del self.graph[node]
            
            for key in list(self.graph.keys()):
                if node in self.graph[key]:
                    self.graph[key].remove(node)
    
        def remove_edge(self, from_node, to_node):
            """Remove a directed edge from 'from_node' to 'to_node'."""
            if from_node in self.graph and to_node in self.graph[from_node]:
                self.graph[from_node].remove(to_node)
    
        def num_nodes(self):
            """Return the number of nodes in the graph."""
            return len(self.graph)
    
        def display(self):
            """Display the graph in an easy-to-read format."""
            for node, neighbors in self.graph.items():
                print(f"{node} -> {neighbors}")
    
    
    
    # Example usage
    if __name__ == "__main__":
        T = int(input())
        graph = []
        for i in range(T):
            chain = input()
            graph.append(chain)
    
    g = DirectedGraph()
    for chain in graph:
        g.add_node(chain[0])
        g.add_node(chain[1])
        g.add_edge(chain[0], chain[1])
        g.add_node(chain[2])
        g.add_edge(chain[1], chain[2])
    
    try:
        output = ''
        while g.num_nodes() > 0:
            output += g.get_no_incoming_nodes()[0]
            g.remove_node(g.get_no_incoming_nodes()[0])
            # print(g.get_no_incoming_nodes())
            # g.display()
            # print()
        print(output)
    except:
        print('SMTH WRONG')
    
  • + 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.