Hacker News Reader

Isn't this overkill to verify that you don't have any invalid states? Consider the state machine as a directed graph, reverse each edge and run DFS from the end state. if you have any vertices in the graph you didn't visit, they're dead ends. That should be more efficient than the O(n^3) way of finding eigenvectors.

View on HN

More precisely, construct a graph with vertices (u, v) where u is a prior state and v a possible successor state, then there must not be a node of out-degree zero unless it is an end state.

As far as complexity goes, this should be linear in number of vertices. In fact, you don't even really have to construct the graph, just count out degree.

That is not enough, since you may still get stuck in a loop.

Fair point, but that is inevitable unless it's a game where the user cannot go back, very few games would fit that bill then.

Reply on news.ycombinator.com