Tried my hand at doing this with US states, feel free to contribute any improvements

https://docs.google.com/spreadsheets/d/1QUdlGrjWuo77QFAjBd1p...

Would be cool to add some geographic features? Maybe the Mississippi and the Rockies?

improved, gives 80

    ^(x|(xx){1,9}|x{32}|(x{64})+)$

I tried to get rid of those redundant ^ and $ but it somehow didn't work. I probably forgot to put it all inside one group.

They are not redundant. Any string of one or more exes is going to constrain a substring of exes of length 2^n (consider n=0 for a trivial proof), so you do need those anchors!

I meant my previous post where I had them in every single possibility.

^[01349][064] works for 197