# Project Euler #79: Passcode derivation

# Project Euler #79: Passcode derivation

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

kitchent + 1 comment Would you mind sharing how you handled the broken edges when you constructed the directed graph? An example like

`SMH TON RNG WRO THG`

, where I have difficulty visualizing the edge between`M`

and`T`

, or that between`H`

and`W`

.**EDIT**: If I didn't get wrong after some reading, those edges were handled with "in-degree zero" as you stated (i.e. the next valid node is a node with no connected edge). And we could confidently remove the smallest node having zero in-degree, without worrying that the answer lies in another node.ErikTillema + 0 comments I'm not sure what you mean with "broken edges" and "node with no connected edge". If it helps, look up the meaning of "directed edge" and "in-degree" in the context of graph algorithms. Good luck!

tieros + 0 comments Thanks for hints. I tried a few different way but returned to your method after 2 days. In projecteuler original problem I used DFS, but here it was giving weird paths (WRONG, MHG, SMHG, RONG, TONG, NG, HG, ONG). Last method that I had used was finding isolated vertices, adding last item to result and removing it from graph. But only got 4 correct answer with it (10 points). With your way now I got 90 score. Still 2 WA to go :)

Edit: Got 100 score, next hint was in problem description

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

nickytobal + 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?

plw_mail + 0 comments It is a possible password, but when there are two or more possible passwords, you print the one that comes first in lexicographical order.

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

randomraccoon + 0 comments I just have to say: I'm a novice coder, but I worked for two days on this problem, eventually restarting from scratch. But I flipping got it. That is satisfying.

nandansvamc + 2 comments Hi anyone can give an abstract idea about this problem.. I understood it in case of numbers .But,in charecters i didn't get what that exactly mean?

shashank21jHackerRank AdminChallenge Author + 0 comments Apply the same logic on a larger character set

zerosnake0 + 1 comment [deleted]Dalimil + 0 comments Please remove your comment as it gives away the solution.

steer_p1ke + 1 comment *

*I have written this code for the original project euler and it worked perfectly to find the passcode there. I tweaked it alittle for validation and something really went awfully wrong. Though, it works well for the sample testcases, original problem, only some testcases are passed. What's wrong in this code? **import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class Solution {

`public static void main(String args[]) { Scanner in = new Scanner(System.in); int size = in.nextInt(); String temp[] = new String[size]; for(int i = 0; i < size; i++){ temp[i] = in.next(); } boolean flag = false; StringBuffer tempPassWord = new StringBuffer(temp[0]); for (int countLogs = 1; countLogs < temp.length && !flag; countLogs++) { for (int count = 2; count >= 0; count--) { if (!(tempPassWord + "").contains(temp[countLogs].charAt(count) + "") && count == 2) { tempPassWord = tempPassWord.append(temp[countLogs].charAt(count) + ""); } else if (!(tempPassWord + "").contains(temp[countLogs].charAt(count) + "")) { tempPassWord = tempPassWord.insert(tempPassWord.indexOf(temp[countLogs].charAt(count + 1) + ""), temp[countLogs].charAt(count)); } } char tempChar; for (int count = 0; count < 2; count++) { if (tempPassWord.indexOf(temp[countLogs].charAt(count) + "") > tempPassWord .indexOf(String.valueOf(temp[countLogs].charAt(count + 1)))) { int index1 = tempPassWord.indexOf(String.valueOf(temp[countLogs].charAt(count))); int index2 = tempPassWord.indexOf(String.valueOf(temp[countLogs].charAt(count + 1))); tempChar = temp[countLogs].charAt(count); tempPassWord.replace(index1, index1 + 1, String.valueOf(temp[countLogs].charAt(count + 1))); tempPassWord.replace(index2, index2 + 1, tempChar + ""); } } for(int validateCount = 0; validateCount < countLogs; validateCount++){ for (int count = 0; count < 2; count++) { if (tempPassWord.indexOf(temp[validateCount].charAt(count) + "") > tempPassWord .indexOf(String.valueOf(temp[validateCount].charAt(count + 1)))) { flag = true; break; } } } } if(flag){ System.out.println("SMTH WRONG"); } else{ System.out.println(tempPassWord); } }`

}

zeo_zagart + 0 comments [deleted]

No more comments

Sort 8 Discussions, By:

Please Login in order to post a comment