Nine-Dot Lock Patterns

Medium

A phone lock screen is a 3 × 3 grid of dots numbered like this:


1 2 3
4 5 6
7 8 9

A lock pattern is a sequence of dots that the finger joins one after another with straight segments. A pattern is valid when: - all of its dots are different; - a segment between two consecutive dots never jumps over a dot that has not been picked yet. If the segment runs straight through the centre of a third dot, that dot must already appear earlier in the pattern. For example, the move 1 → 3 passes through dot 2, so it is allowed only if 2 is already picked. The move 2 → 9 crosses no dot centre and is always allowed. Given shortest and longest, count the valid patterns that use from shortest to longest dots inclusive. Two patterns are different if they use different dots or visit them in a different order.

Example 1

shortest=1, longest=1 → 9

A one-dot code is just any of the nine dots.

Example 2

shortest=2, longest=2 → 56

There are 9 · 8 = 72 ordered pairs of distinct dots. Sixteen are forbidden: the eight pairs whose line runs across a middle dot (1–3, 4–6, 7–9, 1–7, 2–8, 3–9, 1–9, 3–7), in both directions. That leaves 56.

Example 3

shortest=3, longest=2 → 0

No length is both at least 3 and at most 2, so the answer is 0.

Constraints

1 ≤ shortest ≤ 9
1 ≤ longest ≤ 9
shortest may be greater than longest

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Dynamic Programming Backtracking Bitmask