#!/usr/bin/env python3 def before(a, b): if a == "Q": return b >= "U" return a <= b def solve(lines): front = lines[0] sides: list[set[str]] = [set() for _ in range(16)] for line in lines[1:5]: for i, l in enumerate(line): sides[i].add(l) back = lines[-1] # best[c] = smallest number or rotations to sort the # current prefix such that it ends in c. If this is impossible, None. best = { back[0]: 2 } for letter in sides[0]: best[letter] = 1 best[front[0]] = 0 for i in range(1, 16): new_best: dict[str, int] = {} for letter, delta in [(front[i], 0)] + [(side, 1) for side in sides[i]] + [(back[i], 2)]: vals = [turns + delta for (prev, turns) in best.items() if before(prev, letter)] if vals: if letter in new_best: new_best[letter] = min(min(vals), new_best[letter]) else: new_best[letter] = min(vals) best = new_best if best: return(min(best.values())) else: return('impossible') print(solve([input() for _ in range(6)]))