# Project Euler #79: Passcode derivation

# Project Euler #79: Passcode derivation

+ 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!

+ 1 comment in the sample 1, why TSMHWRONG is not a possible password? Given that input, how do you know that T comes after SM?

+ 0 comments can someone please upload hrer a few test cases and res?

+ 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.

Sort 9 Discussions, By:

Please Login in order to post a comment