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.

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.

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.

This is actually my original code for the problem:

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

[…] I was researching the web for approaches to solving this problem, I found Kristian’s MathBlog article quite useful (as usual), and so I took up his suggestion to try implementing a topological sorting […]

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/

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

Yes – it worked beautifully!!!

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?).

Why all of numbers coming at most 1 time ?

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.

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.

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();

solution

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”

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

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 + “”));

}

}

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 + “”));

}

}

what if the success full login attempts are 012 and 210, passcode need not have any digit only once, it is a wrong assumption.

Made this in python, seemed simple and I didn’t see any other python solutions:

[code language="python"][def problem_79():

from operator import itemgetter

f = open('p079_keylog.txt', 'r')

a = f.readlines()

f.close()

a = [x.replace('''\n''', '') for x in a]

a = list(set(a))

b = [x[0] for x in a]

c = [x[1] for x in a]

d = [x[2] for x in a]

b = [x for x in b if x not in c+d]

d = [x for x in d if x not in c+b]

c = [x for x in c if x not in b+d]

dic = {str(k):0 for k in range(10) if str(k) in b+c+d}

for x in a:

if dic[x[0]] >= dic[x[1]]:

for s in dic:

if dic[s] > dic[x[1]]:

dic[s] += 1

dic[x[1]] = dic[x[0]] + 1

if dic[x[1]] >= dic[x[2]]:

for s in dic:

if dic[s] > dic[x[2]]:

dic[s] += 1

dic[x[2]] = dic[x[1]] + 1

final = sorted(dic.items(), key=itemgetter(1))

print(''.join([x[0] for x in final]))]

Made this in python, seemed simple and I didn’t see any other python solutions:

Well, I spent a long time thinking about some generic solution to this problem to the point I gave up continuing. I thought about several things, from linked lists to topological sorting. The linked list solution turned out to be wrong, and it was not obvious that each digit must appear only once in the secret passcode to use topological sorting. After some time, I decided to check solutions from other people and I got disappointed when most of them solved it by hand. I know being aware of the conditions of the problem and of what is possible to do to solve it is part of problem-solving. But still, I wanted to somehow see the beauty in this problem.