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

Python code to solve xkcd 1313 by Peter Norvig

nbviewer.ipython.org

Post reply on HN
Print view View original

61–70 of 75 posts

Re: Python code to solve xkcd 1313 by Peter Norvig

#61

Post by algorias »

drdeca wrote: post #23
Laremere wrote: post #14

Earlier quoted context omitted.

Such a regex cannot exist: 1. Take an existing solution to finding the shortest regex given a list of inclusions an exclusions. 2. Take another unrelated arbitrary program. 3. Combine the two, when the arbitrary program terminates, use the existing solution to solve the problem. 4. Such a regex would have to solve the halting problem to know if the arbitrary program terminates and the existing solution solves the pro…

If a regex is required to only match x if p(x), is the regex required to match ALL x such that p(x)? Although this is probably just pointless nitpicking on my part.

It's required to match all such x, otherwise the empty regex "" trivially satisfies the requirement.

Re: Python code to solve xkcd 1313 by Peter Norvig

#62

Post by jameshart »

xentronium wrote: post #26
joyofpi wrote: post #17

I think it fails for: findregex(set(['abc']), set(['abcd']))

Pretty sure that's impossible within given constraints (only disjunction positive regexes allowed).

trivially fixable by including start-of-string and end-of-string as tokens in the initial string breakdown, so instead of analyzing {abc, ab, bc, a, b, c} as candidate regexes, you start out analyzing {^abc, abc$, ^ab, abc, bc$, ^a, ab, bc, c$, ^, a, b, c, $}; would rapidly home in on c$ as an optimal solution.

Thus would fail against a 'must fail' target of abcabc, but then you fix that by extending the maximum allowable regex fragment length from 4 to 5 and it'll find ^abc$. More generally, you extend the maximum allowable regex count to the longest 'must match string' plus 2, and it'll always succeed, even if it has to create a regex consisting of ^word1$|^word2$|^word3$...

Re: Python code to solve xkcd 1313 by Peter Norvig

#63

Post by dded »

magicalist wrote: post #27
natch wrote: post #18

Earlier quoted context omitted.

IMHO, sadly, that part is serving as a shibboleth. The clue is how he explains all the simple parts of the script with comments, but leaves this part unexplained, making some of us feel left out of the cool club. Implying: if you don't grasp it immediately you must not be up to it. Overall it's a great post, but as to the cryptic parts of it, it's disappointing to see this kind of thing on the part of someone we all…

First, it is explained in the text above it. Second, seriously? A line of code that isn't as clear as it could be in an ipython notebook he probably dashed off in an hour is somehow a reflection on his generosity of spirit? I think you need to recheck your expectations.

> First, it is explained in the text above it.

A minor correction: the explanation for this heuristic was added later. (I first opened this in a tab, and then didn't read the tab till much later. I also wondered about the heuristic and didn't think to hit reload till I saw your reply.)

But you're right, there is certainly nothing ungenerous from Norvig here. Quite the opposite.

Re: Python code to solve xkcd 1313 by Peter Norvig

#64

Post by e12e »

mikeash wrote: post #59
echion wrote: post #56

Earlier quoted context omitted.

Was that in an earlier version? I can't find that in the article now.

Yep, he originally threw out all names that appeared on both lists, while he's now arbitrarily assigning them to the winners' set. Not sure about the reasoning behind the change, but there it is. The quoted line computed new winning and losing sets that excluded all commonalities.

I actually also really liked that line, it helped flesh the article out to be an impromptu tutorial on using sets in python (which it still is, to a certain extent). I remember reading that sets overloaded some sensible operators a while back, but I really appreciated this reminder.

In other words, very nice of you to highlight it in a comment, as new readers wouldn't have seen it otherwise (as it turns out).

Re: Python code to solve xkcd 1313 by Peter Norvig

#65

Post by Groxx »

tlarkworthy wrote: post #34

Exercise for the reader, write a regex to distinguish random noise from English EDIT: possibly down-voted because someone though it was sarcastic??? I was actually thinking of this problem before the XKCD comic, for detecting hashes on hardrives efficiently...

For detecting hashes? As in, SHA, or {key: value}?

If the former, you're possibly better just looking for high-entropy chunks of data of the right size. Of course, that'll match all kinds of encrypted data, but there may not be much you can do there.

Re: Python code to solve xkcd 1313 by Peter Norvig

#69

Post by chao_xu »

gwern wrote: post #48

It's too bad he didn't try to tackle the optimal regexp problem and settled for approximations - it may be a NP-hard problem, but all the example solutions are short enough that the instances might be still tractable. Would've been nice to know for sure.

I asked the problem for regular expression(the theoretical kind) for a finite set on cstheory a while ago.

http://cstheory.stackexchange.com/questions/16860/minimizing...

Apparently this problem is still open.

Post reply on HN