[quote_box_center]This is a real example, recounted in details on a forum[/quote_box_center]
Intro: My wife constantly strives to make me screw up: set the alarm for 3:00 AM, change the ringtone, removed the sync settings, removed she’s messages and then proves that she didn’t wrote that.
Joking aside, at some point i decided, “Enough!” – And put the graphical password on my android device.
The wife laughed and said that she will pick up. I laughed in response, and went on. Now she was thinking how to pick it up, but me which is the probability of this event.
The first and logical idea was to come up with a mathematical way of calculating combinations.
For this it’s necessary to specify the initial conditions:
- Direction is important,
- Each point could be passed only once,
- To connect the two points they need to be in direct line of sight. I mean the first could be united with the second but not with the third.
- Number of points: from 5 to 9. Will call it one stroke, one connection – a hop. This means, we may have from 4 to 8 hops.
Attempts to calculate options mathematically have failed. As imposed condition didn’t allowed to reveal the rules.
The next step: overkill. No that i was hoping to sort out all the tens of thousands of options. The basic idea was – to find patterns. I spent a few hours drawing diagrams. But all laws rested on the symmetry and the fact that all corners are equivalent, as well as all intermediate (except the central).
But when we are scared of difficulties? I began still with one hop.
1 hop – easy as pie – 56 options
2 hop – nothing complicated – 320 options
3 hop – had to work hard – 1624 version
4 hop – it was, huh, tedious – 7152 version
5 hops – Mamma Mia, and torn hair – the result is unknown.
Then i decided not to force my brain and remember the long forgotten programming.
Uncovered Turbo Pascal, blew the dust from the variables and begat to develop the algorithm.
After 4 years of pause, a simple script on Bash took me a whole evening to debug the program. Nothing, that the algorithm was born in 20 minutes.
Here’s the output of options for each number of hops. As you can see, from 1 to 4 the numbers coincides with the practical calculations, but when the number of hops is more than 8 – there is no way, that is logical.
Pascal has a limit of 64 KB on the size of the array. Therefore, even an array of Byte of a few tens of thousands of items is not possible. To bother with dynamic memory allocation or the records i didn’t want, so i could count the ways in details up to 4 hops:
UPDATE. When calculating the above wasn’t considered to pass through a used point. In the new version the bug is fixed.
This is the result of sequence: 11-22-31-32-12:
And the long-awaited result:
So, we have 389488 options. Even if we eliminate from them 50% of the perverse choices, that no every person deprived of schizophrenia, will be able to score the first try, remains 194744 options.
Android gives 20 attempts, after which locks the phone.
Thus, 20/194744 = ,0001 That is the probability of 0.01% !
“Well, well” – I said to my wife, showing the calculations. “Well, well” – said my wife, showing the unlocked phone.