Regex Puzzle • Hacker News Board

Re: Regex Puzzle

#11

Post by IanCal » Thu, Jul 06, 2017, 1:29 PM UTC

andyjohnson0 wrote: post #7

I 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?

It 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).

Re: Regex Puzzle

#12

Post by eutectic » Thu, Jul 06, 2017, 1:49 PM UTC

andyjohnson0 wrote: post #7

I 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?

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

Re: Regex Puzzle

#13

Post by ape4 » Thu, Jul 06, 2017, 1:51 PM UTC

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

Re: Regex Puzzle

#14

Post by simias » Thu, Jul 06, 2017, 1:54 PM UTC

jgrahamc wrote: post #6

Worth doing this by hand to exercise your knowledge of regular expressions. My solution (SPOILER): http://imgur.com/a/9iK9J

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

Re: Regex Puzzle

#15

Post by canada_dry » Thu, Jul 06, 2017, 1:57 PM UTC

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

Re: Regex Puzzle

#16

Post by [deleted] » Thu, Jul 06, 2017, 2:01 PM UTC

eutectic wrote: post #12

andyjohnson0 wrote: post #7

I 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?

You 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]

Re: Regex Puzzle

#17

Post by arien » Thu, Jul 06, 2017, 2:05 PM UTC

KineticLensman wrote: post #9

This 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!

Re: Regex Puzzle

#18

Post by jgrahamc » Thu, Jul 06, 2017, 2:06 PM UTC

simias wrote: post #14

jgrahamc wrote: post #6

Worth doing this by hand to exercise your knowledge of regular expressions. My solution (SPOILER): http://imgur.com/a/9iK9J

Well 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…

I thought it was pretty easy given that the character classes meant that it was pretty easy to take a row/column and eliminate possibilities.

Re: Regex Puzzle

#19

Post by bshimmin » Thu, Jul 06, 2017, 2:09 PM UTC

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.

Re: Regex Puzzle

#20

Post by IanCal » Thu, Jul 06, 2017, 2:09 PM UTC

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.