I'm not sure what to make of the fact that for the abstract matrix problem in the original post, I thought about it for a moment without making any progress, but then for the knights on the phone pad problem it took me just two moments (about twenty seconds) to come up with the third solution -- and for context, I'm a product manager with a history as a developer. It would take me less than five minutes to code it up.

I wish I hadn't read the fourth solution description -- the language used wasn't clear at all to me, but it was enough to point me in the right direction, or maybe I'm just that clever?

That said, I don't like interview questions like that -- there's very much a component of you either get it or you don't. The interviewer says they talk people through it, and if they're good at that, great. But if not, a question like that is (in my book) unfair.

I am struggling to understand some of the explanations offered here. It’s certainly a skill issue on my part. I never learned DP in school and tabular DP has never clicked for me. However, I think there are a few things you could clarify.

> queue = [(A, 0)] # We track (length of walk, current node)

Surely the comment should be reversed, right?

Also, how are we encoding “current node”? Is it an integer? Does A=0, and the rest of the nodes have some arbitrary value? How do we calculate `neighbors(node)`?

> To avoid dealing with very large numbers, assume that we're computing our answer modulo a large prime.

Or tool up and get a better programming language?

Odd to use Berlelamp-Massey to recover a linear recurrence, when Cayley-Hamilton already directly gives you a linear recurrence whose characteristic polynomial is that of the matrix.