Hacker News Reader

Comment by taeric | Hacker News Reader

This gets greatly compounded when you have a lot of states. As an easy example, consider the "state machine" for a rubik's cube. All told, this isn't insurmountable, but you are almost certainly not going to write down all of the allowed states with all of the possible transitions.

Which is not to say you can't make a program to reason about what the allowed states are. I started a probably bad attempt at that a while back at https://taeric.github.io/cube-permutations-1.html. (And, I just noticed the mathjax included on that page isn't loading. Almost certainly my fault... :( )

View on HN

I think your answer boils down to "pick the right tool for the job". Of course state machines are cumbersome for systems with loads of different states and transitions.

But state machines are really useful when designing safety-critical systemsfor aeronautical, automotive or train components, especially if one uses timed automata for modelling.

It's possible to either generate the code from the model or use the model to automatically generate a complete test suite for the modelled system. Very useful for verification purposes.

Completely agree. I did not mean my post as an argument against state machines.

The permutations you're getting are Cayley's Theorem in action: https://en.wikipedia.org/wiki/Cayley%27s_theorem

Basically, there's a finite group that acts on the Rubik's cube, and every finite group is a subgroup of a permutation group if you squint at it right. (what's a 'finite group action?' The 'group' is a set of composable and reversible "moves." The 'action' means that the group moves are effectively state transitions acting on a set of states, and that the action is nice and associative: g(hs) = (gh)s. And 'finite' just says that there's only so many states possible...)

Really nice demo, by the way! Very fun to see the squares go flying.

I'll have to read up on Cayley's Theorem. Thanks for the link!

Glad others found the squares flying as much fun to watch as I did. :D

State charts avoid that problem to some extent, you don't explode the number of state like in a simple finite state machine. But that's a point where you certainly want to use a library.

Right. My assertion would then be that many things are modeled on a ton of possible states.

Granted. In context of this story, I'm in complete agreement with you.

Might be worth reposting that link, it's an interesting topic on its own. Rubik's cube transformations as permutations is one of those "obvious" things that had never occurred to me before, plus the neat interactive demo at the bottom.

Would love to see feedback on it. I posted back when I wrote it. I think it was mostly lost to the noise.

Reply on news.ycombinator.com