Project Euler #79: Passcode derivation
Project Euler #79: Passcode derivation
+ 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!
+ 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); } }
}
+ 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?
Sort 9 Discussions, By:
Please Login in order to post a comment