11 ms·
Regex Puzzle
- Emyr42 9y agoColumn H pattern starts [MVFU]{2}, and 3 of those options don't match the Row 0 pattern, leaving "U" The published solution says H0 should be "S".
- Emyr42 9y agoThe version at https://www.ncsc.gov.uk/content/files/regex_cross_hard_v3.png https://www.ncsc.gov.uk/content/files/regex_cross_hard_v3.pn... has S[MVU]... for column H. Guess nobody tested it.
- Cephlin 9y agoWow, finally a crossword I have a chance at!
- bluesmoon 9y agoWell, there is https://regexcrossword.com/ https://regexcrossword.com/
- kreetx 9y agoNice!
- samjs 9y agoThe OP converted into this format: https://regexcrossword.com/playerpuzzles/595e5542d2433 https://regexcrossword.com/playerpuzzles/595e5542d2433
- angry_albatross 9y agoThere's an error in the second "Across" expression. [^PZVJG]{4}(.)[EFUG]{6}(.)[^\sPZVJI]{2} should be [^PZVJG]{4}(.)[EFUG]{6}\1[^\sPZVJI]{2}
- deleted 9y ago[deleted]
- ColinDabritz 9y agoThis threw me off for a bit. The \1 is from the original puzzle, and refers to the value of the first (capture group). I ran into this issue while filling out the puzzle. The \1 is required to 'propagate' the value in that square to other places. The puzzle is ambiguous without this fix. Thanks for the pointer, I've added the note in the comments. Hopefully the puzzle is editable. Lovely puzzle, and it's a great quote. :)
- rpearl 9y agoFixed the typo: https://regexcrossword.com/playerpuzzles/595e8c8e86584 https://regexcrossword.com/playerpuzzles/595e8c8e86584
- Already__Taken 9y agoAnyone know a decent android app for these? the MIT one has the most insane and broken scrolling functionality it's shocking.
- jgrahamc 9y agoWorth doing this by hand to exercise your knowledge of regular expressions. My solution (SPOILER): http://imgur.com/a/9iK9J http://imgur.com/a/9iK9J
- stedaniels 9y agoWell, thanks. I tried to cheat with https://github.com/blukat29/regex-crossword-solver https://github.com/blukat29/regex-crossword-solver and got hit with lex parsing errors! My limited python and 5 minute effort resulted in failure! At least I got to read the message though :-)
- simias 9y agoWell done. I don't know what you think but I found that most of the time the character classes would intersect perfectly (i.e. there'd only be one character possible once you intersect both sides of a single square). That made it pretty easy overall since for the vast majority of the board you don't have to worry about the "context". But I guess if it's meant for an audience of folks not very familiar with regexes it's difficult enough as it is.
- jgrahamc 9y agoI thought it was pretty easy given that the character classes meant that it was pretty easy to take a row/column and eliminate possibilities.
- rootlocus 9y agoI'm assuming the solution isn't unique because I found some positions that are under-constrained.
- angry_albatross 9y agoWhich positions? I didn't find any that were under-constrained.
- 9y ago
- andyjohnson0 9y agoI 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?
- IanCal 9y agoIt certainly should be. There limited things in the puzzle help as well. For example, you can split each one of these regexes up into smaller ones based on positioning. Now some of them are simply "match any of the following characters" which can be combined together with set intersections (and something similar with "none of these characters).
- eutectic 9y agoYou could expand each regex to a regex on the whole table, and then take the intersection of the corresponding NFA/DFAs. Unfortunately, I suspect this takes exponential (or worse?) time in the worst case.
- deleted 9y ago[deleted]
- eutectic 9y agoThis 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.
- jonahx 9y agoCould you elaborate on the encoding? What are valid mappings?
- eutectic 9y agoA variable becomes '1' in the corresponding position and '.' everywhere else, and similarly with negations of variables and '0'. The regex is then just an alternation of these sub-regexes. This incurs just a linear blow-up in the number of variables, for the '.'s. For an n x m grid, you can encode any CNF formula with n clauses on m variables. See here if you are unfamiliar with CNF: https://en.wikipedia.org/wiki/Conjunctive_normal_form https://en.wikipedia.org/wiki/Conjunctive_normal_form
- dbrgn 9y agoIf you want a challenge, try this one: http://twiki.org/p/pub/Codev/TWikiPresentation2013x03x07/regex-crossword-puzzle.png http://twiki.org/p/pub/Codev/TWikiPresentation2013x03x07/reg...
- dmit 9y agoOriginally from the MIT Mystery Hunt: https://devjoe.appspot.com/huntindex/puzzle/mit2013601 https://devjoe.appspot.com/huntindex/puzzle/mit2013601 PDF: http://web.mit.edu/puzzle/www/2013/coinheist.com/rubik/a_regular_crossword/grid.pdf http://web.mit.edu/puzzle/www/2013/coinheist.com/rubik/a_reg...
- rspeer 9y agoNote that as a Mystery Hunt puzzle, the goal of the puzzle isn't just to fill in the grid, it's to find the answer, a secret word or phrase that would be filled into another puzzle (the metapuzzle). The puzzles generally don't tell you how to extract the answer, but the idea is you know it when you see it.
- gregable 9y agoI also created an HTML-based version of this one some time ago that allows rotation and color codes the rows as matching or not: https://gregable.com/p/regexp-puzzle.html https://gregable.com/p/regexp-puzzle.html
- deleted 9y ago[deleted]
- proactivesvcs 9y agoThanks for the gregex in HTML format! (gets coat)
- KineticLensman 9y agoThis 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-challenge https://www.ncsc.gov.uk/news/take-our-regex-crossword-challe...
- arien 9y agoSo I suppose is it a one time thing only? A shame, it was quite fun to solve!
- simlevesque 9y agoThere you go: https://regexcrossword.com/ https://regexcrossword.com/
- cag_ii 9y agoInterstingly, Bletchly Park is known to have used crossword puzzles published in The Daily Telegraph as a recruitment tool for "codebreakers" during WWII. https://en.wikipedia.org/wiki/Bletchley_Park#Personnel https://en.wikipedia.org/wiki/Bletchley_Park#Personnel
- ape4 9y agoSince the clues are machine parsable it should be machine solvable.
- hermanschaaf 9y agoIt is indeed machine-solvable; I wrote a solver for regexcrossword.com puzzles a while back (https://github.com/hermanschaaf/regex-crossword-solver https://github.com/hermanschaaf/regex-crossword-solver). It was great fun, maybe even more than solving the puzzles by hand!
- mtharrison 9y agoWill your tool work on this puzzle though? I don't think so because it has backreferences.
- canada_dry 9y agoRegex 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/ http://regex.inginf.units.it/ https://regex101.com/ https://regex101.com/ http://www.regexr.com/ http://www.regexr.com/ And of course stackoverflow.
- simlevesque 9y agoI love the fact that you can have unit tests for your regexes on regex101.
- TACIXAT 9y agoI use https://www.debuggex.com/ https://www.debuggex.com/ a lot when it's a complex expression. The visualization really helps.
- squeaky-clean 9y agoI 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.
- rgb122 9y agoWhy don't you just learn learn Linux and pcre? What use are 2-bit windows tools? Don't fill your head with windows - a dead os walking
- dahart 9y agoI think parent said why: there's no RegexBuddy on Linux. I can see you're new, so I won't be harsh but HN isn't the place for this kind of commentary. Everyone here understands the difference between Windows and Linux. Judging and/or trolling over Windows is boring, take it over to Reddit or something.
- 9y ago
- bshimmin 9y agoBrilliant. 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.
- baron816 9y agoTechnophobe or technophile?
- bshimmin 9y agoTechnophobe. Just acquiring the necessary Google skills to find out what the proper regex rules are will probably take him till Christmas. But hey, the man loves a challenge.
- sergiosgc 9y agoTechnophobe, probably. A technophile crossword aficionado should have this solved by dinner time.
- IanCal 9y agoFun! I made a few mistakes by writing letters sideways which was then confusing (C vs U, for example), but this was a nice puzzle.
- deleted 9y ago[deleted]
- hokkos 9y agoI'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/symbolic-automata-the-toolkit/ https://www.microsoft.com/en-us/research/publication/symboli... https://www.microsoft.com/en-us/download/details.aspx?id=52302 https://www.microsoft.com/en-us/download/details.aspx?id=523... It now seems to be Open Source (MIT): https://github.com/AutomataDotNet/Automata https://github.com/AutomataDotNet/Automata
- jfries 9y agoHow did you solve backreferences with that approach?
- eru 9y agoThere's also redgrep (https://github.com/google/redgrep https://github.com/google/redgrep) that supports intersection and complements of regular expressions. I am toying the idea of writing a little game where player A thinks of a regular expression, and player B tries to guess. If B guesses right, they win. If B guesses wrong, A has to provide a false positive and a false negative (if they exist), and B gets to guess again. Can you think of ways to automate the roles of A and/or B?
- jwilk 9y agoDirect link to the crossword: https://ichef.bbci.co.uk/images/ic/976xn/p057t19t.jpg https://ichef.bbci.co.uk/images/ic/976xn/p057t19t.jpg
- mcbobbington 9y agoI love regexes. In addition to doing cool things and saving time, I feel like I'm a "real programmer" whenever I write a good one.
- gargarplex 9y agoThis comic artistically renders that feeling. I, too, know it well. https://xkcd.com/208/ https://xkcd.com/208/
- shabble 9y agoDoes any common regex format/dialect require '\-' for a literal hyphen? AFAIK it's only special inside character classes, and escaping it doesn't necessarily work there if it would form a valid range identifier.
- okdana 9y agoI don't know of any that require it. But it's common to see punctuation characters escaped like that because Perl (and PCRE and its various cousins/descendants) allows you to escape any non-meta-character and have it treated as a literal. I suppose the two main benefits are (a) neither the writer nor the reader has to remember which punctuation characters are meta-characters (you just have to remember that it's always a literal if it's escaped), and (b) in implementations like PHP's which try to replicate the Perl-style 'delimited' syntax (e.g., /foo/), it prevents characters in the pattern from conflicting with the delimiters. Maybe there's some other advantage but i can't think of what.
- timdierks 9y agoI believe column E is under-constrained; a solution with column E = "YYYY " or "OOOO " passes the tests, but is clearly not what's intended.
- angry_albatross 9y agoIn the expression in the second row, the 5th character must match the 12th character, which must be R.
- timdierks 9y agoNever mind, this was an error in the https://regexcrossword.com/playerpuzzles/595e5542d2433 https://regexcrossword.com/playerpuzzles/595e5542d2433 version, which has a (.) where it should have a \1 in row 2 (thanks to @angry_albatross).
- gumby 9y agoNice! 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.
- tzakrajs 9y agoCould I stop by this afternoon and expect it to be in stock or was this a temporary offering?
- gumby 9y agoIt wasn't a short-term item, but poor Kepler's has shrunk so much who knows if it's in stock or not. I would call them. It wasn't described as using regexes of course, so you'll have to say something like that special version of scrabble. The designer is local so if they no longer stock it you could look online...but it's better to get it from the shop if you can.
- eutectic 9y agoCan you please expand a bit on how it worked?
- gumby 9y agoNever played it, but from looking at the box of talking to the inventor it was just that The set of letters included regex operators and those The set of letters included regex operators and those you could put on the board as well. Meaning other people could use him as well To make words.
- gozur88 9y agoThat's a very odd thing to see in a mainstream publication.
- Xophmeister 9y agoThat wasn't as hard as I thought it would be. I was worried that, without stard/end of string anchors, things could get quite hairy, but the biggest stretch of logic was just, "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."