Android lock screen

Java code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

// Points are indexed from 0 through 8:
//   0   1   2
//   3   4   5
//   6   7   8

int implicit[][] = new int[9][9];          // implicit[0][8] = 4 because going from 0 to 8 requires passing through 4, etc.

for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) implicit[i][j] = -1;      // -1 = no intermediate point
implicit[0][2] = 1; implicit[3][5] = 4; implicit[6][8] = 7;
implicit[0][6] = 3; implicit[1][7] = 4; implicit[2][8] = 5;
implicit[0][8] = 4; implicit[2][6] = 4;

for (int i = 0; i < 9; i++) for (int j = i+1; j < 9; j++)
    implicit[j][i] = implicit[i][j];

boolean used[] = new boolean[9];    // 'true' for points currently used in the pattern
int pattern[] = new int[9];                // current pattern

int N = 0, count = 0;
for (int i = 0; i < 9; i++) used[i] = false;

do {
    int to = -1;
    while (true) {
        if (N < 9) {

            int from = (N > 0) ? pattern[N-1] : -1;         // first, we try to extend the pattern by one point
            while (true) { 
                to++; if (to >= 9) break;                       // no points left
                if (used[to]) continue;                         // point already used; keep trying
                if (from < 0) break;                            // first point: no restrictions
                int imp = implicit[to][from];
                if (imp < 0 || used[imp]) break;             // if there is no intermediate point, or it is already used
            }

            if (to < 9) {                             // a point was found to add to the pattern
                pattern[N] = to; used[to] = true;
                N++;
                break;
            }
        }

        N--; if (N < 0) break;                     // if no point was found, remove the last point of the pattern

        to = pattern[N]; used[to] = false;         // and use it as starting point for next search
    }

    if (N >= 4) {         // count only patterns of length >= 4

//        for (int i = 0; i < N; i++) {            // un-comment to see all possible paths
//            out.print(pattern[i]);
//        }
//        out.println();

        count++;
    }

} while (N >= 0);

out.println(count);

Output:

1

839112

And a pattern can be anything as long as the following restrictions are observed:

He needs to have at least four points (and obviously no more than nine). -Once The point is marked can not be reused. He can use one or several "plays horse," as [0 5 4 2]. 'You can not go through a point not scored without dialing. For example, the pattern [0 2 1 4] is illegal because moving your finger between 0 and 2 mark the 1. 'Once a point is marked, can be used to reach another point unmarked. For example, [0 4 3 5] and [0 4 5 3] are valid.

With these restrictions it reaches a certain amount of points used combinations as:

4 points: 1624 combinations.

5 points: 7152 combinations.

6 points: 26016 combinations.

7 points: 72912 combinations.

8 points: 140 704 combinations.

9 points: 140 704 combinations.

Making a total of 389112 possible combinations to lock your phone.

In Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# e.g. change digit 6 to position (2,1)
def digitToGrid(n):
        return ((n-1)%3, (n-1)/3)

# e.g. change position (2,1) to digit 6 
def gridToDigit(x, y):
        return 1 + x + 3*y

# returns digit between digits a and b
def via(a, b):
        ax, ay = digitToGrid(a)
        bx, by = digitToGrid(b)
        dx = bx - ax
        dy = by - ay
        if (dx%2 == 0 and dy%2 == 0): 
                return [ gridToDigit(ax + dx/2, ay + dy/2) ]
        else:
                return []

# test if we can jump from a to b
def isValidMove(a, b, remainings):
        for v in via(a, b):
                if v in remainings:
                        return False
        return True


DIGITS = range(1, 10)
NB_DIGITS = len(DIGITS)
MIN_DIGITS = 4 

def getPatterns(remainingDigits, last=None):
        global NB_DIGITS, MIN_DIGITS

        patterns = []
        # pick one of the remaining digits
        for i in xrange(0, len(remainingDigits)):
                # test if we can jump from last digit to this one
                if last<>None and not isValidMove(last, remainingDigits[i], remainingDigits):
                        continue
                for pattern in getPatterns(remainingDigits[:i] + remainingDigits[i+1:], remainingDigits[i]):
                        patterns += [ [ remainingDigits[i] ] + pattern ]

        # if there's already enough digits, we add an empty "tail"
        if len(remainingDigits) <= NB_DIGITS - MIN_DIGITS:
                patterns += [ [] ]

        return patterns

print len( getPatterns(DIGITS) )

Here's my MATLAB code. To get the answer I just called f([],[]).

function [outputArg] = f(A,B)
    outputArg=(length(A)>=4);
    if isempty(A)
        for i=-1:1
            for j=-1:1
                B=[B; i,j]; %B stores points not yet used
            end
        end
        outputArg=4*f([1,1],B(1:8,:))+4*f([1,0],[B(1:7,:); B(9,:)])+f([0,0],[B(1:4,:); B(6:9,:)]);
    elseif length(A)<9
        for i=1:size(B,1)
            if ~ismember((B(i,:)+A(1,:))/2,B,'rows')
                outputArg=outputArg+f([B(i,:); A],[B(1:i-1,:); B(i+1:size(B,1),:)]);
            end
        end
    end
end

Here is a solution that calculates both the total number of valid paths as well as finds the longest path. The length of a path is defined as the sum of Euclidean distances between successive dots placed on a unit grid.

from math import sqrt
from itertools import combinations, permutations


def middle_point(p, q):
    return (p[0] + q[0]) // 2, (p[1] + q[1]) // 2


def distance(p, q):
    return sqrt((p[0] - q[0])**2 + (p[1] - q[1])**2)


def check_path(path):
    used_points = set()
    prev_point = None
    path_length = 0

    for point in path:
        if prev_point != None:
            d = distance(prev_point, point)
            path_length += d
            if (d == 2 or d > sqrt(5)) and middle_point(prev_point, point) not in used_points:
                return False, None
        prev_point = point
        used_points.add(point)
    return True, path_length


ALL_DOTS = tuple((i, j) for i in range(-1, 2) for j in range(-1, 2))
max_length = 0
best_path = None
count = 0

for r in range(4, 10):
    print("Checking paths of length", r)
    for combination in combinations(ALL_DOTS, r):
        for path in permutations(combination):
            is_valid, length = check_path(path)
            if is_valid:
                count += 1
                if length > max_length:
                    max_length = length
                    best_path = path

print(max_length, best_path, count, sep="\n")

$C code:$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <stdio.h>

int not_allowed[9][9] = {
{-1,-1,1,
-1,-1,-1,
3,-1,4},

{-1,-1,-1,
-1,-1,-1,
-1,4,-1},

{1,-1,-1,
-1,-1,-1,
4,-1,5},

{-1,-1,-1,
-1,-1,4,
-1,-1,-1},

{-1,-1,-1,
-1,-1,-1,
-1,-1,-1},

{-1,-1,-1,
4,-1,-1,
-1,-1,-1},

{3,-1,4,
-1,-1,-1,
-1,-1,7},

{-1,4,-1,
-1,-1,-1,
-1,-1,-1},

{4,-1,5,
-1,-1,-1,
7,-1,-1}
};

int count = 0;

void step(int index, int last, unsigned long long map) {

int i;

if (index==9)
return;

for (i=0; i<9; i++) {
if (((map & (1<<i)) == 0) && ((last == -1) || (not_allowed[last][i] == -1) || ((map & (1<<not_allowed[last][i])) != 0))) {
if (index+1>=4) {
count ++;
}
step(index+1, i, map+(1<<i));
}
}
}

int main() {
step(0,-1,0);
printf("%d\n", count);
}

If you compile and run this simple C program then you will get the solution $\boxed{389112}$