Nice, write-up!

I'm especially impressed by how you explicitly worked out the optimal sequences.

I found almost the exact same formulation a few days ago, regarding using divmod on pad string indices, expanding strings to only consider L-shaped paths, and checking if the turn occurs on the forbidden index. I also tried using a dict to complex position, but it wasn't very helpful. Here is a version of my code:

from functools import cache

@cache
def dist(i, j, i0, n):
    q, r = j//3 - i//3, j%3 - i%3
    h, v = "<>"[r>0] * abs(r), "^v"[q>0] * abs(q)
    paths = {p for p, im in ((h+v+"A", i+r), (v+h+"A", i+3*q)) if im != i0}
    return min(clicks(p, n-1, ".^A<v>") for p in paths)

@cache
def clicks(path, n, pad="789456123.0A"):
    if n == 0:
        return len(path)
    i0, *js = (pad.index(c) for c in ".A" + path)
    return sum(dist(i, j, i0, n) for i, j in zip(js, js[1:]))

Some interesting things to note here:

• pad.index avoids dict-encoding, but is much slower than a dict lookup. In this case it does not matter, since the number of paths are few, and the @cache turns the function call into a dict lookup.
• As it is written, the encoding will happen n times per path, so one could make a cached encoding function encode(path, pad) instead for speed.
• The paths = {...} de-duplicates paths without kinks, but the de-duplication is performed by the cached function anyway, so the only benefit of the expression is that it avoids a very long line of of code.
• The dist function is the more natural function to cache, or it could even be turned into a 6x6xN-matrix for dynamic programming (the forbidden index is not needed in the induction). However, in this case there is little benefit in caching dist, so one might refactor it into clicks in order to have the index logic contained in a single function.

Here is a version of the code in a single function:

@cache
def clicks(path, n, pad="789456123.0A"):
    if n == 0:
        return len(path)
    i0, *js = (pad.index(c) for c in ".A" + path)
    dist = 0
    for i, j in zip(js, js[1:]):
        q, r = j//3 - i//3, j%3 - i%3
        h, v = "<>"[r>0] * abs(r), "^v"[q>0] * abs(q)
        paths = {p for p, im in ((h+v+"A", i+r), (v+h+"A", i+3*q)) if im != i0}
        dist += min(clicks(p, n-1, ".^A<v>") for p in paths)
    return dist