##### Short Problem Definition:

A non-empty zero-indexed array A consisting of N integers is given. Two integers P and Q are called adjacent in array A if there exists an index 0 ≤ K < N−1 such that:

• P = A[K] and Q = A[K+1], or
• Q = A[K] and P = A[K+1].

A non-empty zero-indexed sequence B consisting of M integers is called adjacent in array A if the following conditions hold:

• B = A;
• B[M−1] = A[N−1];
• B[K] and B[K+1] are adjacent in A for 0 ≤ K < M−1.

##### Complexity:

time complexity is O(NlogN)

space complexity is O(N)

##### Execution:

This is a graph problem, the shortest adjacent sequence is basically a shortest path in a bidirectional graph.

To calculate the shortest path I am using Breath-first-search or Dijkstra’s algorithm.

I don’t agree with the problem specification of one of the extreme cases such as [1,2,1]. I believe that the shortest path is 3, since the beginning and end are not adjacent. But it seems that Codility expects 1.

##### Solution:
```from collections import defaultdict

def bfs_shortest_path(paths, start, end):
q = [(start, 1)]

visited_paths = set()

while q:
key, distance = q.pop(0)
new_distance = distance + 1
for path in paths[key]:
if path == end:
return new_distance
elif path not in visited_paths:
q.append((path, new_distance))

def solution(A):
if len(A) <= 2:
return len(A)

# I dont agree with this edge case based on the problem statement
if A == A[-1]:
return 1

paths = defaultdict(set)