12
\$\begingroup\$

Scenario

I am using pattern matching lockscreen and I sadly forgot my pattern. I would like to know how much time I will need to unlock it. Here are the specifications of Google's lock screen, that we will use for this challenge.

  • Every 5 wrong code, the user has to wait 30 seconds before any further entry.
  • A pattern must, at least, consist in 4 points (see below)

  • A point can be only used once, but you can go over it several times (see image right below): wierd

Here, the center point is only used once, even if we go over it again for this particular pattern.

Hypothesis & Facts

We'll assume we're superheroes and that we can draw any pattern in 1 second, we never need to eat or sleep. Yeah, we're superhumans.

I'm a very unlucky person. "Worst case scenario" is my daily life so the pattern I will attempt last will be the right one.

What do we have to pwn?

For those who don't know it, Android (and other phones now) offers the ability of unlocking the phone through drawing a pattern on a 9-point matrix. This matrix can be described as follow :

C(A)  M(B)  C(C)
M(D)  X(E)  M(F)
C(G)  M(H)  C(I)
  • C standing for "corner point"
  • M for "middle point"
  • X for "center point"
  • I have given identifiers to the points to make it easier

The permitted direct connections are as follows :

Corner point :

Corner

Middle point :

Middle

Center point :

Center

However, as pointed out by steveverrill, "once the centre has been used (and therefore becomes unavailable) a direct connection between the bottom left and top right corner becomes unambiguous and therefore possible". Same goes for every "middle point", if e.g. the point B has already been counted, then a direct connection between A and C is possible. If e.g. F has already been counted, then a direct connection between C and I is possible. Etc...

Rules

  • The point of this challenge is to return how much time (in human readable form, aka year/day/month/hour/whatever the time you find) I will need to unlock this damn phone.
  • You can't hardcode the number of possible valid patterns (don't even Google it, you fool), calculate it (that's actually the fun part, isn't it ?)
  • Shortest piece of code wins
  • Good luck !
\$\endgroup\$
  • 2
    \$\begingroup\$ I don't have Android, but I'd like to point out that your example appears to violate the permitted direct connections. I'm guessing that once the centre has been used (and therefore becomes unavailable) a direct connection between the bottom left and top right corner becomes unambiguous and therefore possible. \$\endgroup\$ – Level River St Jul 27 '14 at 23:19
  • 1
    \$\begingroup\$ As a user of this lock screen, I'm almost entirely sure that with enough finger precision, you can connect any two unused points. \$\endgroup\$ – Οurous Jul 27 '14 at 23:44
  • 4
    \$\begingroup\$ @Ourous: At least on my phone, if you move your finger around a dot to connect dots on either side of it, the dot in between is inserted into the sequence and counted as used anyway. \$\endgroup\$ – user2357112 supports Monica Jul 28 '14 at 5:20
  • 1
    \$\begingroup\$ @steveverrill : You're right, I added a tip about that. I hope you don't mind I quoted you directly, since I thought it was a good explanation. \$\endgroup\$ – user8670 Jul 28 '14 at 5:41
  • 1
    \$\begingroup\$ "You can't hardcode the number of possible valid patterns" is not an observable requirement. \$\endgroup\$ – Post Rock Garf Hunter Jun 26 '17 at 2:36
2
\$\begingroup\$

Rebmu: 197 175 168 167 characters

Generates combinations as a series of numbers (ex. 12369 is top-left to top-right to bottom-right), checks if combination is valid, and increments a counter if it is. This might take a while* to run. Returns the number of seconds needed to unlock the phone.

B[[2 13][4 17][6 39][8 79][5 19][5 28][5 37][5 46][a 0]]Fdz[Q1feCb[st[a]paStsC/1 Qa^Qa^e?NNfiAtsC/2 e?NNfiArvTSc/2]]rpJ987653088[StsADj1233iA^e?SuqSf[++K]]adKmp30dvK 5

Unmushed and commented:

; for each subarray c: 
; the sequences c/2 and c/3 are invalid before the point c/1 is pressed
; a 0 - a is never in the sequence, therefore 0 is always invalid
b: [[2 13] [4 17] [6 39] [8 79] [5 19] [5 28] [5 37] [5 46] [a 0]]
; checks (most) conditions of validity
f: dz[
    ; set q to 1
    q: 1
    ; foreach array in b as c
    fe c b [
        ; set a to be portion of s before c/1
        st [a] pa s ts c/1
        ; q = q and (a does not contain c/2) and (a does not contain reverse of c/2)
        q: a^ q 
           a^ e? nn fi a ts c/2 
              e? nn fi a ts rv c/2
    ]
]
; repeat 98765308 times, with j = 1 to 98765308
; 987653088 = 987654321 (largest valid combination) - 1234 (smallest valid combination) + 1
rp j 987653088 [
    ; set s to j+1233 (smallest valid combination - 1) as a string
    s: ts ad j 1233 
    ; if f returns trues and s does not contain duplicates, increment k
    i a^ e? s uq s 
          f
     [++ k]
]
; print k (number of combinations) + 30 * (k/5) -> number of seconds needed
ad k mp 30 dv k 5

The program loops from 1 to (987654321-1233), checking 1233+loop counter (therefore checking 1234 to 987654321).

If the number 987653088 is replaced with, 9876-1233 or 8643, then the program will find the time taken for all 4-point combinations.

Output for 9876-1233=8643 (4-point combinations):

>> rebmu %combinations.rebmu
== 11344

Output for 98765-1233=97532 (4 and 5-point combinations):

>> rebmu %combinations.rebmu
== 61426

Output for 987654-1233=986421 (4,5,6-point combinations):

>> rebmu %combinations.rebmu
== 243532

*4/5-point took me about 8 seconds to run; 4-6 took about 77 seconds. It might take ~24 hours or longer depending on who runs this to calculate number of combinations for 4-9 point combinations.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy