Regex Puzzle

Well, there is <a href="https:&#x2F;&#x2F;regexcrossword.com&#x2F;" rel="nofollow">https:&#x2F;&#x2F;regexcrossword.com&#x2F;</a>

Brilliant. 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.

Regex is one of those tools that I use a couple times a year - usually for cleaning up lousy input data.<p>I always end up spending a fair amount of time using tools like:<p><a href="http:&#x2F;&#x2F;regex.inginf.units.it&#x2F;" rel="nofollow">http:&#x2F;&#x2F;regex.inginf.units.it&#x2F;</a><p><a href="https:&#x2F;&#x2F;regex101.com&#x2F;" rel="nofollow">https:&#x2F;&#x2F;regex101.com&#x2F;</a><p><a href="http:&#x2F;&#x2F;www.regexr.com&#x2F;" rel="nofollow">http:&#x2F;&#x2F;www.regexr.com&#x2F;</a><p>And of course stackoverflow.

I&#x27;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.<p>Links :<p><a href="https:&#x2F;&#x2F;www.microsoft.com&#x2F;en-us&#x2F;research&#x2F;publication&#x2F;symbolic-automata-the-toolkit&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.microsoft.com&#x2F;en-us&#x2F;research&#x2F;publication&#x2F;symboli...</a><p><a href="https:&#x2F;&#x2F;www.microsoft.com&#x2F;en-us&#x2F;download&#x2F;details.aspx?id=52302" rel="nofollow">https:&#x2F;&#x2F;www.microsoft.com&#x2F;en-us&#x2F;download&#x2F;details.aspx?id=523...</a><p>It now seems to be Open Source (MIT):<p><a href="https:&#x2F;&#x2F;github.com&#x2F;AutomataDotNet&#x2F;Automata" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;AutomataDotNet&#x2F;Automata</a>

Worth doing this by hand to exercise your knowledge of regular expressions. My solution (SPOILER): <a href="http:&#x2F;&#x2F;imgur.com&#x2F;a&#x2F;9iK9J" rel="nofollow">http:&#x2F;&#x2F;imgur.com&#x2F;a&#x2F;9iK9J</a>

This BBC report refers to a puzzle released by the UK&#x27;s National Cyber Security Centre [1], as part of an online recruitment effort.<p>[1] <a href="https:&#x2F;&#x2F;www.ncsc.gov.uk&#x2F;news&#x2F;take-our-regex-crossword-challenge" rel="nofollow">https:&#x2F;&#x2F;www.ncsc.gov.uk&#x2F;news&#x2F;take-our-regex-crossword-challe...</a>

Wow, finally a crossword I have a chance at!

If you want a challenge, try this one: <a href="http:&#x2F;&#x2F;twiki.org&#x2F;p&#x2F;pub&#x2F;Codev&#x2F;TWikiPresentation2013x03x07&#x2F;regex-crossword-puzzle.png" rel="nofollow">http:&#x2F;&#x2F;twiki.org&#x2F;p&#x2F;pub&#x2F;Codev&#x2F;TWikiPresentation2013x03x07&#x2F;reg...</a>

I know that there are problems to do with regex matching that are NP-hard. So I&#x27;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?

I love regexes. In addition to doing cool things and saving time, I feel like I&#x27;m a &quot;real programmer&quot; whenever I write a good one.

Anyone know a decent android app for these? the MIT one has the most insane and broken scrolling functionality it&#x27;s shocking.

That wasn&#x27;t as hard as I thought it would be. I was worried that, without stard&#x2F;end of string anchors, things could get quite hairy, but the biggest stretch of logic was just, &quot;There are five spaces for me to fit a character, an optional characters and two two-character sequences. Therefore that optional character must not appear.&quot;

Column H pattern starts [MVFU]{2}, and 3 of those options don&#x27;t match the Row 0 pattern, leaving &quot;U&quot;<p>The published solution says H0 should be &quot;S&quot;.

Does any common regex format&#x2F;dialect require &#x27;\-&#x27; for a literal hyphen? AFAIK it&#x27;s only special inside character classes, and escaping it doesn&#x27;t necessarily work there if it would form a valid range identifier.

Direct link to the crossword:<p><a href="https:&#x2F;&#x2F;ichef.bbci.co.uk&#x2F;images&#x2F;ic&#x2F;976xn&#x2F;p057t19t.jpg" rel="nofollow">https:&#x2F;&#x2F;ichef.bbci.co.uk&#x2F;images&#x2F;ic&#x2F;976xn&#x2F;p057t19t.jpg</a>

Since the clues are machine parsable it should be machine solvable.

Nice! At Keplers in Mountain View you can buy version of Scrabble that uses regexes. The designer used to sell it in front of the shop -- he is obviously a programmer.

I believe column E is under-constrained; a solution with column E = &quot;YYYY &quot; or &quot;OOOO &quot; passes the tests, but is clearly not what&#x27;s intended.

Fun! I made a few mistakes by writing letters sideways which was then confusing (C vs U, for example), but this was a nice puzzle.

That&#x27;s a very odd thing to see in a mainstream publication.