Project Euler 79: By analysing a user’s login attempts, can you determine the secret numeric passcode?

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('\n')
                       .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.

Wrapping up

I don’t have the full solution through an algorithm, but the piece of source code I have can be downloaded here..

Later on I have found out that since we don’t have repeated digits in the solution we could have used topological sorting where the nodes of the input graph is the digits 0-9 and there is a directed edge between two nodes if the number comes before the other. This can then be fed to this algorithm and the answer should be provided. However, a combination of laziness and … well just laziness means that I haven’t implemented the algorithm. If you have I would love to see it.

Today’s blog image is provided by Marc Falardeau who shared it under the creative commons license.