Do you know of other "freak" examples of using regexes to solve combinatorial problems?

Here is a list of some that I know about (with an obvious selection bias -- the first three are due to Abigail, and the last three are some of my posts):

• RE: sieve of erothenes
• The N-queens problem using pure regexes
• Perl regular expression matching is NP-complete (offsite)
• Pure regex Hamiltonian Circuit solution
• Golf: Buying with exact change
• The greedy change-making problem using regexes