[deleted]
Regex Puzzle
21–30 of 97 posts
Re: Regex Puzzle
#22I've worked on the project where some XSD files defined fields with regex restrictions, also some rules over fields added other stricter regexps or negative regexps depending on some context in a format called Schematron. I had to generate XML files conforming to those XSD, so I used some tools around Z3 solver and Microsoft.Automata to generate those strings conforming to multiple regexps. It would convert the regexps to finite automaton and intersecting them, walking it from the starting state to a final one over a charset.
Links :
https://www.microsoft.com/en-us/research/publication/symboli...
https://www.microsoft.com/en-us/download/details.aspx?id=523...
It now seems to be Open Source (MIT):
Re: Regex Puzzle
#23Since the clues are machine parsable it should be machine solvable.
It is indeed machine-solvable; I wrote a solver for regexcrossword.com puzzles a while back (https://github.com/hermanschaaf/regex-crossword-solver). It was great fun, maybe even more than solving the puzzles by hand!
Re: Regex Puzzle
#24I've worked on the project where some XSD files defined fields with regex restrictions, also some rules over fields added other stricter regexps or negative regexps depending on some context in a format called Schematron. I had to generate XML files conforming to those XSD, so I used some tools around Z3 solver and Microsoft.Automata to generate those strings conforming to multiple regexps. It would convert the regex…
How did you solve backreferences with that approach?
Re: Regex Puzzle
#25Regex is one of those tools that I use a couple times a year - usually for cleaning up lousy input data. I always end up spending a fair amount of time using tools like: http://regex.inginf.units.it/ https://regex101.com/ http://www.regexr.com/ And of course stackoverflow.
I love the fact that you can have unit tests for your regexes on regex101.
Re: Regex Puzzle
#26This BBC report refers to a puzzle released by the UK's National Cyber Security Centre [1], as part of an online recruitment effort. [1] https://www.ncsc.gov.uk/news/take-our-regex-crossword-challe...
So I suppose is it a one time thing only? A shame, it was quite fun to solve!
There you go: https://regexcrossword.com/
Re: Regex Puzzle
#27Regex is one of those tools that I use a couple times a year - usually for cleaning up lousy input data. I always end up spending a fair amount of time using tools like: http://regex.inginf.units.it/ https://regex101.com/ http://www.regexr.com/ And of course stackoverflow.
I use https://www.debuggex.com/ a lot when it's a complex expression. The visualization really helps.
Re: Regex Puzzle
#28I know that there are problems to do with regex matching that are NP-hard. So I'm wondering if it is possible to attack this puzzle using an algorithm that simplifies the individual regexes using knowledge of the regexes that that they interact with?
This problem is NP-hard by reduction from SAT. Treat each column as a truth variable and use the rows to encode CNF clauses. For example, `(A | ^C)` becomes `(1..)|(..0)`. Then set all the column regexes to `( 0* )|( 1* )` to enforce a consistent truth value for each variable.
Re: Regex Puzzle
#29Regex is one of those tools that I use a couple times a year - usually for cleaning up lousy input data. I always end up spending a fair amount of time using tools like: http://regex.inginf.units.it/ https://regex101.com/ http://www.regexr.com/ And of course stackoverflow.
I will always keep a Windows install at the ready just for RegexBuddy. I use it mostly to take a regex and generate the code I need for it (e.g. find the first numbered group in match in javascript), without having to remember language specific details.
Re: Regex Puzzle
#30Brilliant. My dad is 71, loves puzzles (like cryptic crosswords and Sudoku), is a huge technophobe, and has just retired. This should keep him busy until about 2022.
Technophobe or technophile?