Don't ask to ask, just ask  
PerlMonks 
Pure regex Hamiltonian Circuit solutionby blokhead (Monsignor) 
on Oct 10, 2003 at 17:44 UTC ( [id://298341] : perlmeditation . print w/replies, xml )  Need Help?? 
I'd seen Abigail do nasty things with regexes before, but never really understood them at all. However, in the recent NQueens solver, it was a pure regex (backrefs only), there were no (?{}) constructs, and I was finally able to understand how Abigail does it..
Then, on a regex kick, I discovered Abigail's pure regex 3SAT reduction. If you haven't already seen it, it's the coolest couple of lines on the planet. With all this regex excitement, I decided to try my hand at solving some NPcomplete problem(s) with pure regexes. I tried a handful of different NPcomplete problems, but after a few emails with MJD, I understood why these attempts went wrong. I kept getting hung up on the string and regex size being exponential on the size of input (not meaning my solution was incorrect, but invalidating its use as an NPcompleteness reduction proof). Finally, I think I may have gotten it right with Hamiltonian Circuits. Abigail has done this before using extended regexes, but claimed to be stuck on a pure regex solution that wasn't exponential. So without further ado, here's my solution. Given a (simple, undirected) graph with E edges and V vertices, it finds a Hamiltonian Circuit (a cycle that visits every vertex exactly once, starting and ending in the same place). The size of the string it creates is bounded by O(V^4), and the size of the regex it creates is bounded by O(V^2). Now the dirty details.. Here's the value of $string and $regex for the example graph included: Here's how it works:
There you have it. Your feedback is welcome. I really hope I haven't made any mistakes in my analysis. This code isn't onetenth as beautiful and elegant as Abigail's 3SAT reduction, and perhaps it could be improved upon. But hey, we all have to start somewhere ;) Update: modified code so that $string is a little clearer to read. Instead of commaseparating the edge and vertex lists, they are separated by spaces. $regex is modified accordingly, matching on \b where appropriate, instead of a comma. blokhead
Back to
Meditations

Log In^{?}
Node Status^{?}
node history
Node Type: perlmeditation [id://298341] Approved by Aristotle Frontpaged by broquaint help
Chatterbox^{?}
Other Users^{?}
Others learning in the Monastery: (7)
As of 20240228 09:36 GMT
Sections^{?}
Information^{?}
Find Nodes^{?}
Leftovers^{?}
Voting Booth^{?}
My favourite way to spend a leap day ...
Results (26 votes). Check out past polls. 