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

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

Written by on 14 January 2012

Topics: Project Euler

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.

15 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    I remember this being a pretty weird problem. Me and my friend had found the solution by hand (which wasn’t too hard), but I had trouble creating a program. So I wrote down the steps that I was using to solve the problem by hand, and created a flowchart of sorts. After I did that, it was trivial to convert that into working code. I guess that was the first “algorithm” that I created.

  2. Kristian says:

    Nice way of solving it SuprDewd. I guess that is a good first solution for almost any algorithm. It probably wont be the best algorithm, but it is a good first attempt.

  3. SuprDewd says:

    This is actually my original code for the problem:

    List<string> codes = new List<string> {
                       /* ... Here were the codes ...  */
                     };
    
    codes = codes.Distinct().OrderBy(i => i).ToList();
    
    string code = "";
    
    while (codes.Count > 0)
    {
        List<char> possibleNext = new List<char>();
    
        for (int i = 0; i < codes.Count; i++)
        {
            if (!possibleNext.Contains(codes[i][0]))
            {
                possibleNext.Add(codes[i][0]);
            }
        }
    
        for (int i = 0; i < codes.Count; i++)
        {
            for (int j = 1; j < codes[i].Length; j++)
            {
                for (int c = 0; c < possibleNext.Count; c++)
                {
                    if (possibleNext == codes[i][j])
                    {
                        possibleNext.RemoveAt(c);
                    }
                }
            }
        }
    
        char next = possibleNext.Single();
    
        code += next;
    
        List<string> buffer = new List<string>();
    
        for (int i = 0; i < codes.Count; i++)
        {
            codes[i] = codes[i].Replace(next, ' ').Trim();
    
            if (codes[i].Length > 0)
            {
                buffer.Add(codes[i]);
            }
        }
    
        codes = buffer;
    }
    
    Console.WriteLine(code);

    This is another solution I created later. I think this one is faster.

    string[] codes = File.ReadAllLines("Problem79.txt").Distinct().ToArray();
    char nextChar = codes[0][0];
    List<char> triedChars = new List<char> { nextChar };
    List<char> code = new List<char>();
    
    while (true)
    {
        if (codes.All(c => !c.Skip(1).Contains(nextChar))) { code.Add(nextChar); codes = codes.Select(l => l.TrimStart(nextChar)).ToArray(); triedChars.Clear(); }
        codes = codes.Where(c => c != "").Distinct().ToArray();
        if (codes.Length > 0)
        {
            nextChar = codes.Select(i => i.First()).Where(i => !triedChars.Contains(i)).First();
            triedChars.Add(nextChar);
        }
        else break;
    }
    
    Console.WriteLine(new String(code.ToArray()));
  4. Thanks Kristian for another great blog post. I took up your advice, and tried to implement a topological sort algorithm.

    http://problematicsets.com/project-euler-79-by-analysing-a-users-login-attempts-find-the-secret-passcode/

  5. Kristian says:

    Cool. I guess I have to make a test implementation of that as well. Did it work well?

  6. Yes – it worked beautifully!!!

  7. Khaur says:

    Nice one spotting the relation with topological sorting!

    I just solved this using gedit and the replace function: find the digit that only occurs at the beginning, write it down, delete it and repeat. I think this instance of the problem is not very interesting because the greedy solution is too easy.

    It would be interesting to try and find an algorithm that works even when there are repeated digits, and what are the conditions on the sampling of the password for the algorithm to successfully recover it. Put that way, it sounds a lot like grammatical inference (and it actually is, can you find the class of grammar that we are trying to learn?).

  8. S.Ged says:

    Why all of numbers coming at most 1 time ?

  9. Ethereal_shore says:

    SuprDewd,I faced the same problem while trying to create the program for the problem I easily solved by observation. Now will try to implement a algorithm.

  10. Martin Kirk says:

    1: 319
    2: 680 -> 319680
    3: 180 tells us 1 < 8 319680 = ok
    4: 690 -> swap 9 & 6 -> 316980
    5: 129 -> inject 2 after 1 -> 3162980
    6: 620 = ok
    7: 762 -> inject 7 before 6 -> 31762980
    8: 689 -> swap 8 & 9 -> 31762890
    9: 762 (repeat of 7)
    10: 318 = ok
    11: 368 = ok
    12: 710 -> swap 1 & 7 -> 37162890
    .. ok
    20: 736 -> swap 7 & 3 -> 73162890 (solved)
    ..
    50: all ok

    should be pretty easy to build an algorithm on that.

  11. Martin Kirk says:

    Solution:

    var solution = new List();

    var lines = from txt in File.ReadAllLines(Path.GetDirectoryName (Util.CurrentQueryPath) + “\\p079_keylog.txt”)
    let num = Convert.ToInt32(txt).ToArr()
    select new
    {
    A = num[0],
    B = num[1],
    C = num[2]
    };

    foreach (var line in lines)
    {
    if(!solution.Contains(line.A)) solution.Add(line.A);
    if(!solution.Contains(line.B)) solution.Add(line.B);
    if(!solution.Contains(line.C)) solution.Add(line.C);

    if(solution.IndexOf(line.B) < solution.IndexOf(line.A))
    {
    var tmp = solution.IndexOf(line.A);
    solution[solution.IndexOf(line.B)] = line.A;
    solution[tmp]= line.B;
    }

    if(solution.IndexOf(line.C) < solution.IndexOf(line.B))
    {
    var tmp = solution.IndexOf(line.B);
    solution[solution.IndexOf(line.C)] = line.B;
    solution[tmp]= line.C;
    }
    }
    String.Join("", solution).Dump();

  12. Martin Kirk says:

    solution

    var solution = new List&lt;int&gt;();
    
    var lines = from txt in File.ReadAllLines(Path.GetDirectoryName (Util.CurrentQueryPath) + &quot;\\p079_keylog.txt&quot;)
    			let num = Convert.ToInt32(txt).ToArr()
    			select new
    			{
    				A = num[0],
    				B = num[1],
    				C = num[2]
    			};
    			
    foreach (var line in lines)
    {
    	if(!solution.Contains(line.A)) solution.Add(line.A);
    	if(!solution.Contains(line.B)) solution.Add(line.B);
    	if(!solution.Contains(line.C)) solution.Add(line.C);
    	
    	if(solution.IndexOf(line.B) &lt; solution.IndexOf(line.A))
    	{
    		var tmp = solution.IndexOf(line.A);
    		solution[solution.IndexOf(line.B)] = line.A;
    		solution[tmp]= line.B;
    	}
    	
    	if(solution.IndexOf(line.C) &lt; solution.IndexOf(line.B))
    	{
    		var tmp = solution.IndexOf(line.B);
    		solution[solution.IndexOf(line.C)] = line.B;
    		solution[tmp]= line.C;
    	}
    }
    String.Join(&quot;&quot;, solution).Dump();
    
  13. Jeremy Miller says:

    There is a much simpler algorithm.

    1. Determine the digits in the passcode by making a list of digits in the keys, without duplicates.

    2. Make a list of pairs of numbers from the order in the keys.

    3. Find the unique digit which never appears at the beginning of any of the pairs. This is the last digit in the passcode, because nothing comes after it.

    4. Remove pairs which include the last digit in the second entry of the pair, and repeat step 3 to find the second-last digit.

    5. Loop this process n times, where n is the length of the passcode until you have constructed the whole passcode.

    fileName = raw_input(“Enter the file name: “)

    entries = []

    with open(fileName) as inputKeys:
    entries = map(str.strip, inputKeys.readlines())

    #print “entries \t\t= \n\n”, entries, “\n”

    L = len(entries[0])
    N = len(entries)

    #print “key length \t\t= “, L, “\n”

    #print “number of entries \t= “, N, “\n”

    digitsInPasscode = set()

    for attempt in entries:
    #print attempt
    #attemptDigits = map(int,str(attempt))
    attemptDigits = attempt
    #print attemptDigits
    for digit in attemptDigits:
    digitsInPasscode.add(digit)

    passcodeLength = len(digitsInPasscode)
    #print ‘Digits in the passcode are’, digitsInPasscode, ‘\n’
    #print ‘Number of digits in the passcode =’, passcodeLength, ‘\n’
    #print ‘range(passcodeLength) =’, range(passcodeLength), ‘\n’

    ###################################################################

    pairOrder = []

    for n in range(N):
    entryDigits = entries[n]
    for i in range(L-1):
    for j in range(i+1,L):
    pairOrder = pairOrder + [entryDigits[i],entryDigits[j]]

    pairOrder = [pairOrder[i:i+2] for i in range(0, len(pairOrder),2)]

    def uniq(input):
    output = []
    for x in input:
    if x not in output:
    output.append(x)
    return output

    pairOrder = uniq(pairOrder)

    #print “The order of pairs of numbers \t= \n\n”, pairOrder, “\n”

    ###################################################################

    solution = []

    digitsInPasscodeList = list(digitsInPasscode)
    possibleDigits = digitsInPasscodeList

    for d in range(passcodeLength):

    for pair in pairOrder:
    if pair[0] in possibleDigits:
    possibleDigits.remove(pair[0])

    for i in range(len(pairOrder)):
    for pair in pairOrder:
    if (pair[1] == possibleDigits[0]):
    pairOrder.remove(pair)

    solution.insert(0,possibleDigits[0])

    del digitsInPasscodeList
    del possibleDigits

    digitsInPasscodeList = list(digitsInPasscode)
    possibleDigits = digitsInPasscodeList

    for n in solution:
    possibleDigits.remove(n)

    #print “The solution so far starting from the end = “, solution, “\n”
    #print “The new pair order = \n”, pairOrder, “\n”
    #print “The new possibleDigits = “, possibleDigits, “\n”

    ###################################################################

    Solution = map(int, solution)
    print “\nSolution: “, solution, “\n”

    ###################################################################

  14. Aravind says:

    What I really did was first solving it by hand. And it seemed that, it was somewhat easy enough to implemented.
    public class checker {
    public static void main(String args[]) {
    String temp[] = { “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” };
    StringBuffer tempPassWord = new StringBuffer(temp[0]);
    for (int countLogs = 0; countLogs -1; 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));
    }
    }
    for (int count = 0; 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 + “”);
    }
    }
    }
    System.out.println((tempPassWord + “”));
    }
    }

  15. Ranjith says:

    I tried using java for the problem it checks using the same way manual work does.

    public class checker {
    public static void main(String args[]) {
    String temp[] = { “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” };
    StringBuffer tempPassWord = new StringBuffer(temp[0]);
    for (int countLogs = 0; countLogs -1; 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));
    }
    }
    for (int count = 0; 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 + “”);
    }
    }
    }
    System.out.println((tempPassWord + “”));
    }
    }

Trackbacks For This Post

  1. Project Euler 79 – By analysing a user’s login attempts, find the secret passcode

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.