A common security method used for online banking is to ask the user for three ra
ID: 3580290 • Letter: A
Question
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.
The text file contains:
319
680
180
690
129
620
762
689
762
318
368
710
720
710
629
168
160
689
716
731
736
729
316
729
729
710
769
290
719
680
318
389
162
289
162
718
729
319
790
680
890
362
319
760
316
729
380
319
728
716
I am trying to code this in Java Netbeans and i am trying to use topological sorting to answer this question but i cant seem to figure it out. i was wondering if you could code it so i can see how it is coded using topological sorting algorithm to get the answer: 73162890
Explanation / Answer
Before even starting this problem I would like to say that I have solved the major part of Problem 79 of Project Euler by hand. The problem reads
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.
I actually just wanted to take a look at the data before figuring out a solution, and as I saw there were some multiple entries I wanted to remove them. So I imported the input file into a spread sheet and sorted the entries to remove the duplicate entries.
After doing that I was down to 31 entries to analyse – a tad easier to get an overview over. I noticed one thing. 0 never comes first or second. So I could safely place 0 at the end of the string. I also noted that 4 and 5 was not present at all and that 7 always comes first.
This lead me to write a small piece of code to pin out what numbers were before and after what other numbers. I wrote this
int[,] input = ReadInput(filename);
bool[,] edge = new bool[10, 10];
bool[] found = new bool[10];
for (int i = 0; i < input.GetLength(0); i++) {
edge[input[i, 1], input[i, 0]] = true;
edge[input[i, 2], input[i, 0]] = true;
edge[input[i, 2], input[i, 1]] = true;
}
for (int i = 0; i < 10; i++) {
Console.Write("Comes before " + i + ": ");
for (int j = 0; j < 10; j++) {
if (edge[i, j]) Console.Write(j + ", ");
}
Console.WriteLine();
}
for (int i = 0; i < 10; i++) {
Console.Write("Comes after " + i + ": ");
for (int j = 0; j < 10; j++) {
if (edge[j, i]) Console.Write(j + ", ");
}
Console.WriteLine();
}
with the read input as
private int[,] ReadInput(string filename) {
string[] message = File.ReadAllText(filename).Split(' ')
.Select(x => x.Trim()).ToArray();
int[,] retVal = new int[message.Length, 3];
for(int i= 0; i < message.Length; i++){
for (int j = 0; j < message[i].Length; j++) {
retVal[i, j] = int.Parse(message[i].Substring(j,1));
}
}
return retVal;
}
Executing that gave me
Comes before 0: 1, 2, 3, 6, 7, 8, 9,
Comes before 1: 3, 7,
Comes before 2: 1, 3, 6, 7,
Comes before 3: 7,
Comes before 4:
Comes before 5:
Comes before 6: 1, 3, 7,
Comes before 7:
Comes before 8: 1, 2, 3, 6, 7,
Comes before 9: 1, 2, 3, 6, 7, 8,
Comes after 0:
Comes after 1: 0, 2, 6, 8, 9,
Comes after 2: 0, 8, 9,
Comes after 3: 0, 1, 2, 6, 8, 9,
Comes after 4:
Comes after 5:
Comes after 6: 0, 2, 8, 9,
Comes after 7: 0, 1, 2, 3, 6, 8, 9,
Comes after 8: 0, 9,
Comes after 9: 0,
And from that we can see that 4,5 is indeed not present in the input.
Further more by inspection we can see that there are no repeated digits so we should be able to produce a sequence without repeated digits.
Using what comes before the others we can see that 7 comes first, and the only thing that is before 3 is 7, so we can write 73 as the first digits. This can be continued by hand and yields the sequence 73162890. We can then check that it also fits the other way around.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.