Tuesday, 6 January 2009

Project Euler, Problem 79

I decided to take another look at some of the problems over on Project Euler, and number 79 jumped out at me yesterday evening when I saw it. Within about ten minutes I had an approach, and in less than ten minutes after that I had a solution. No explicit calculations or anything like that required, just a bit of logical thought.

Here's the problem as stated:

"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 asked 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."

Now, I'm not going to go into all the details of it, but my approach was as follows: delete any duplicates, they won't tell you anything new; since none of the entries contain multiple copies of digits and we're looking for the shortest possible passcode, assume that there is only one instance of a digit in the code; then simply look, it's not that hard after that to deduce what the correct answer is.

This takes my total of completed problems on Project Euler to seven. Only another eighteen to go, and I think I've about reached my limit of problems that can be solved with pen and paper or by inspection. There are several others I've made inroads on by considering what the problem is actually asking, but they'll all require some computer assistance and practice of C++.

Which is cool!

No comments: