Lock Screen Combinations

Computer Science Level 5

Screen Combination Screen Combination

On Android, there is an option to have your password as a pattern. The pattern is a continuous line that connects the dots of a square grid together, subjected to the following rules:

  • Once the line passes through a dot, the dot is lit
  • Once a dot is lit, it can't be used again.
  • You cannot go over an unlit dot without lighting it.
  • Once a dot is lit, you can use it to reach another unlit dot.

The pattern drawn is directional: Drawing the same pattern in the opposite direction is considered a pattern distinct from the former.

Let F ( x , y , n ) F(x,y,n) be the number of distinct patterns possible on a grid of size ( x , y ) (x,y) and which lights up n n dots.

As an example:

  • F ( 3 , 3 , 0 ) = 1 F(3,3,0) = 1
  • F ( 3 , 3 , 1 ) = 9 F(3,3,1) = 9
  • F ( 2 , 2 , 4 ) = 24 F(2,2,4) = 24
  • F ( 3 , 3 , 4 ) = 1624 F(3,3,4) = 1624
  • F ( 3 , 3 , 9 ) = 140704 F(3,3,9) = 140704

Find the value of F ( 3 , 4 , 12 ) F(3,4,12) .


The answer is 93100144.

Julian Poon by Julian Poon , 20, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Julian Poon
Apr 6, 2020

My solution involves a recursive function that navigates the search tree, enumerating all patterns. This function will navigate the pattern such that only 1 additional dot is lit before calling itself again, to prevent double counting.

I welcome other solutions with different methods and languages ^-^

Anyways here's my script: 

 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
 
import math

# Size of grid
N_GRID_X = 3
N_GRID_Y = 4

# Number of dots used
N_DOTS = 12

# Mutable variable
COUNT = [0]

def recursive_enumerate(available, prev, n_dots):

    '''
    available: The available positions
    prev: The previous position taken
    n_dots: Number of dots that should be taken
    '''
    # Checks if pattern has been found
    if len(available) == N_GRID_X*N_GRID_Y - n_dots:
        COUNT[0] += 1
        return

    # For each dot to try next
    for a in available:

        # Make a copy since lists are mutable
        copy = available.copy()

        # If no previous dot (first dot)
        if prev == -1:
            copy.remove(a)
            recursive_enumerate(copy, a, n_dots)
            continue

        # If previous dot exists:

        gcd = math.gcd(a[0] - prev[0], a[1] - prev[1])
        diff = ((a[0] - prev[0])//gcd, (a[1] - prev[1])//gcd)

        to_remove = []
        for i in range(1,gcd+1):
            middle = (prev[0] + diff[0]*i, prev[1] + diff[1]*i)
            if middle in copy:
                to_remove.append(middle)

        if len(to_remove) > 1:
            continue

        copy.remove(to_remove[0]) 
        recursive_enumerate(copy, a, n_dots)

available = [(i,j) for i in range(N_GRID_X) for j in range(N_GRID_Y)]
prev = -1
recursive_enumerate(available, prev, N_DOTS)

print("COUNT =", COUNT[0])

1 Helpful 1 Interesting 0 Brilliant 1 Confused
Piotr Idzik
Apr 28, 2020

Here is my python code. I use kind of a mixture of depth-fist-search and dynamic programming. The tricky part is to determine, which nodes can be accessed from a given one after several moves (i.e. after some nodes were used ). In the main function, I store the partial results by saving the current (i.e. unused) node set and the current node . Each time, I shift them in such a way, that would touch the X and the Y axis. One could think about exploiting some symmetry in the in the current node set. 

 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
"""
https://brilliant.org/problems/lock-screen-combinations/
"""
import itertools

def connections_to(node_set, cur_node):
    """
    returns all nodes, which can be reached from cur_node in the node_set
    """
    def is_connected(start_node, end_node):
        def is_between(in_val, in_a, in_b):
            return in_a <= in_val <= in_b or in_b <= in_val <= in_a
        def are_colinear(node_a, node_b, node_c):
            """
            checks if the points node_a, node_b, node_c are on the same straight line
            """
            def get_vec(p_a, p_b):
                return tuple([a-b for (a, b) in zip(p_a, p_b)])
            vec_a = get_vec(node_a, node_b)
            vec_b = get_vec(node_a, node_c)
            return vec_a[1]*vec_b[0] == vec_a[0]*vec_b[1]
        res = True
        if start_node == end_node:
            res = False
        else:
            for tmp_node in node_set-{start_node, end_node}:
                if is_between(tmp_node[0], start_node[0], end_node[0]) \
                and is_between(tmp_node[1], start_node[1], end_node[1]):
                    if are_colinear(tmp_node, start_node, end_node):
                        res = False
                        break
        return res
    return {tmp_node for tmp_node in node_set if is_connected(tmp_node, cur_node)}


def fun(size_x, size_y, max_len):
    """
    returns the number of "android locking paths" on a grid of the size size_x*size_y
    """
    def move_to_zero(node_set):
        min_x = min((x for (x, _) in node_set))
        min_y = min((y for (_, y) in node_set))
        if (min_x, min_y) != (0, 0):
            out_node_set = {(x-min_x, y-min_y) for (x, y) in node_set}
        else:
            out_node_set = node_set
        return (out_node_set, min_x, min_y)
    def input_to_hashable(cur_node, cur_node_set):
        return (cur_node, tuple(cur_node_set))
    hash_data = {}
    def inner(cur_node, cur_path_len, cur_node_set):
        nonlocal hash_data
        cur_input_hash = input_to_hashable(cur_node, cur_node_set)
        if cur_input_hash in hash_data:
            res = hash_data[cur_input_hash]
        else:
            if cur_path_len == max_len:
                res = 1
            else:
                res = 0
                for new_node in connections_to(cur_node_set, cur_node):
                    tmp_node_set = cur_node_set-{cur_node}
                    tmp_node_set, shift_x, shift_y = move_to_zero(tmp_node_set)
                    tmp_node = (new_node[0]-shift_x, new_node[1]-shift_y)
                    res += inner(tmp_node, cur_path_len+1, tmp_node_set)
            hash_data[cur_input_hash] = res
        return res
    path_num = 0
    all_node_set = set(itertools.product(range(size_x), range(size_y)))
    for start_node in all_node_set:
        start_node_set = all_node_set-{start_node}
        path_num += inner(start_node, 1, start_node_set)
    return path_num

assert fun(3, 3, 0) == 0
assert fun(3, 3, 1) == 9
assert fun(2, 2, 4) == 24
assert fun(3, 3, 4) == 1624
assert fun(3, 3, 9) == 140704
assert fun(2, 4, 5) == fun(4, 2, 5)
assert fun(3, 4, 6) == fun(4, 3, 6)
RES = fun(3, 4, 12)
assert RES == fun(4, 3, 12)
print(RES)

0 Helpful 1 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...