Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Regex Puzzle

bbc.co.uk

Post reply on HN
Print view View original

91–97 of 97 posts

Re: Regex Puzzle

#91

Post by fapjacks »

dahart wrote: post #70
fapjacks wrote: post #65

Earlier quoted context omitted.

If, however, you're into judging and/or trolling over Linux, then welcome to HN! There are tons of upvotes to be had in comments disparaging Linux.

I'm sorry you feel that way, that sounds like maybe you've had some bad experiences here and are turning pessimistic about HN. Just because it happens doesn't mean it's universally accepted. Personally I would say exactly the same thing in response to the above comment if it was talking about Linux instead of windows and had nothing substantive to support it. Yes, you can find people who agree with any insults you wa…

This pipe dream is what drew me to HN ten years ago. And while there are specifically rules against drawing comparisons between HN and reddit, years ago, the parallel made sense. These days, being totally honest, I find reddit to be more approachable and friendly and informative in the types of subreddits I read than HN, the vast majority of times. The reason I keep coming back to HN is for the once-in-a-blue-moon comments which blow your mind. If those comments stopped happening, or if they started happening on reddit, I'd never come back. There is absolutely a creed which is the centerline of HN, and deviation from it -- even totally reasonable, level-headed deviation -- is often punished with downvotes into invisibility. I've specifically created a Chrome browser extension to remove all point/color information from post comments -- and recently uploaded it to Github [0] -- just to keep my own voting habits from being influenced by this brutal kraken of sameness that exists on HN. My post above is a little bit tongue-in-cheek, but in my experience, one of the subjects you can most find downvotes with is the classic win/*nix flamewar. Even something totally reasonable and said in a straightforward, matter-of-fact way which promotes something about Linux in a thread about Windows is annihilated. Unwanted facts and differing viewpoints are erased from existence. That's HN, even if there's some silver lining in there occasionally.

[0] https://github.com/fapjacks/antihnbs

Re: Regex Puzzle

#92

Post by hokkos »

eru wrote: post #79
hokkos wrote: post #22

I'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…

There's also 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 t…

I think AutomataDotNet can do all that :

Automation of regular expression generation, it seems easy : use RE fragments and aggregate them, or walk the type hierarchy of the RE AST and generate them randomly.

B needs to guess A's RE so we need to generate examples of strings belonging to it to gives hints : this is exactly the use case of AutomataDotNet.

Also if B guess a RE that is equivalent to A's RE it seems unfair to not attribute a win, so we need to tell if 2 RE belong to the same equivalence class. AutomataDotNet does have a AreEquivalent method.

You can automate the generation of false positive and a false negative with the method Minus to creates an automaton that accepts A-B or B-A and generate an example.

Re: Regex Puzzle

#93

Post by eru »

hokkos wrote: post #92
eru wrote: post #79

Earlier quoted context omitted.

There's also 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 t…

I think AutomataDotNet can do all that : Automation of regular expression generation, it seems easy : use RE fragments and aggregate them, or walk the type hierarchy of the RE AST and generate them randomly. B needs to guess A's RE so we need to generate examples of strings belonging to it to gives hints : this is exactly the use case of AutomataDotNet. Also if B guess a RE that is equivalent to A's RE it seems unfai…

Thanks, I'll have a look.

You are right about the equivalence classes: for that you want to talk about the corresponding DFA (which have a unique normal form in the shape of the minimum DFA).

I am not sure about the rest of what you are saying: in general even just minimizing regular expressions is EXP-SPACE complete, if I remember right.

Yes, generation of false negative and false positive ain't so hard---theory agrees with you. But automating the guesser is, as far as I know.

Re: Regex Puzzle

#94

Post by mtharrison »

hermanschaaf wrote: post #23
ape4 wrote: post #13

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

Will your tool work on this puzzle though? I don't think so because it has backreferences.

Re: Regex Puzzle

#95

Post by hokkos »

eru wrote: post #93
hokkos wrote: post #92

Earlier quoted context omitted.

I think AutomataDotNet can do all that : Automation of regular expression generation, it seems easy : use RE fragments and aggregate them, or walk the type hierarchy of the RE AST and generate them randomly. B needs to guess A's RE so we need to generate examples of strings belonging to it to gives hints : this is exactly the use case of AutomataDotNet. Also if B guess a RE that is equivalent to A's RE it seems unfai…

Thanks, I'll have a look. You are right about the equivalence classes: for that you want to talk about the corresponding DFA (which have a unique normal form in the shape of the minimum DFA). I am not sure about the rest of what you are saying: in general even just minimizing regular expressions is EXP-SPACE complete, if I remember right. Yes, generation of false negative and false positive ain't so hard---theory agr…

I was talking about generating hints to give an opportunity to the RE guesser to find the secret RE. You seem to talk about automating the RE generation based on the pattern of the hints, yeah I didn't thought about that, the other answer seem to talk about it.

Re: Regex Puzzle

#96

Post by Emyr42 »

Column 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".

Post reply on HN