CMU Coding Bootcamp
thecoded.prof
1from typing import List, Optional, TypeVar
2
3
4T = TypeVar("T")
5
6
7def repeatingPattern(L: List[T]) -> Optional[List[T]]:
8 """Returns the smallest repeating pattern of a list or None if no pattern exists."""
9 if len(L) < 2:
10 return None
11 repeat_options = list(
12 reversed([i for i in range(2, max(len(L) // 2 + 1, 3)) if len(L) % i == 0])
13 )
14 M = [L[0]]
15 for repeat in repeat_options:
16 M = L[: len(L) // repeat]
17 if M * repeat == L:
18 return M
19 if len(M) > len(L):
20 return None
21 return None
22
23
24print("Testing repeatingPattern()...", end="")
25assert repeatingPattern([1, 2, 1, 2]) == [1, 2]
26assert repeatingPattern([1, 2, 1, 2, 1, 2, 1, 2]) == [1, 2]
27assert repeatingPattern([1, 2, 3, 1, 2, 3]) == [1, 2, 3]
28assert repeatingPattern([1, 1]) == [1]
29assert repeatingPattern([]) == None
30assert repeatingPattern([42]) == None
31assert repeatingPattern([1, 2, 3, 1, 2]) == None
32assert repeatingPattern([121, 212, 12]) == None
33L = [1, 2, 3, 4]
34assert repeatingPattern(L * 20) == L
35
36# Finally, verify that the function is non-mutating
37L = [1, 2, 1, 2]
38repeatingPattern(L)
39assert L == [1, 2, 1, 2]
40print("Passed!")