Python code to solve xkcd 1313 by Peter Norvig(nbviewer.ipython.org) |
Python code to solve xkcd 1313 by Peter Norvig(nbviewer.ipython.org) |
lambda c: 3*len(matches(c, uncovered)) - len(c)
H(a,b) = lambda c: a*len(matches(c, uncovered)) - b*len(c)
def findregex_lambda(winners, losers, a, b):
"Find a regex that matches all winners but no losers (sets of strings)."
# Make a pool of candidate components, then pick from them to cover winners.
# On each iteration, add the best component to 'cover'; finally disjoin them together.
pool = candidate_components(winners, losers)
cover = []
while winners:
best = max(pool, key=lambda c: a*len(matches(c, winners)) - b*len(c))
cover.append(best)
pool.remove(best)
winners = winners - matches(best, winners)
return '|'.join(cover)
>>> findregex_lambda(starwars, startrek, 3, 1)
' T|E.P| N'
>>> findregex_lambda(starwars, startrek, 3, 2)
' T|B| N| M'
def best_H_heuristic(winners, losers):
d = {(a,b) : len(findregex_lambda(winners, losers, a,b)) for a in range(0,4) for b in range(0,4)}
return min(d, key=d.get)
>>> best_H_heuristic(starwars, startrek):
(3,1)
>>> best_H_heuristic(nfl_in, nfl_out)
(3, 2)
>>> findregex_lambda(nfl_in, nfl_out, 3, 1)
'pa|g..s|4|fs|sa|se|lt|os'
>>> findregex_lambda(nfl_in, nfl_out, 3, 2)
'pa|ch|4|e.g|sa|se|lt|os'
You could also explore heuristics of different forms:
M(a,b,d,e) = lambda c: a*len(matches(c, uncovered))^b - d*len(c)^e
L(a,b) = lambda c: a*log(len(matches(c, uncovered))) - b*len(c)1. The greedy algorithm has an O(log(n)) approximation ratio, meaning it produces a regex guaranteed to use a number of terms within a multiplicative O(log(n)) factor of the optimal regex.
2. Unless P != NP, set cover cannot be approximated better than the greedy algorithm. In other words, the only general solutions you'll find (unless you're using some special insight about how regular expressions cover sets of strings) will be no better than a constant factor improvement in produced regex size than the greedy algorithm.
That being said, regexes (esp disjunctions of small regexes) are not arbitrary sets. So this problem is a subset of set cover, and certainly may have efficient exact solutions.
winners, losers = (winners - losers), (losers - winners)http://codegolf.stackexchange.com/questions/17718/meta-regex...
That link includes a perl 10-liner to do the same.
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 problem.
5. Since the halting problem cannot be solved, no such regex can exist.
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...
(note the inspiration was a nefarious regex scanner for finding bitcoin hashes. I have no intention of building such a thing, but the idea of a random detector regex intrigued me. Is it possible?)
My idea was more like calculate the statistics of character n-grams in english (all of which exist in random noise too), but count the most unlikely occurrences until you hit some probabilistic threshold that indicates some well thought out decision boundary.
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.
key=lambda c: 3*len(matches(c, uncovered)) - len(c)Why the "3" bit, good question. Would be interesting to see what happens with other relative weights of number of matches and length.
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 look up to. It would be more generous of spirit if he were to have written this in a readable, self explanatory way, like the rest of the code... as python should be written.
Sigh. Norvig has a posse, but I thought it had to be said.
>>> import this
...
"Readability matters"
...
"Sparse is better than dense"
...
"If the implementation is hard to explain, it's a bad idea"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.
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$...
practical tradeoffs, but yes, his preferred language is Python.
Though it cares about the size of the AST rather than the concrete syntax. I can't try running it now, I'm on an iPad.
http://cstheory.stackexchange.com/questions/16860/minimizing...
Apparently this problem is still open.
I'm still not happy with my 214 on Alphabetical including one false match (I was 202 or something with everything correctly matched).
If so, yes, that's what a saved ipython notebook is. See: http://ipython.org/notebook.html for an overview of ipython notebooks.
You can export it to html, latex, etc using "ipython nbconvert --to <format_you_want>". See: http://ipython.org/ipython-doc/dev/interactive/notebook.html...
Basically, the website you're seeing (nbviewer) hosts ipython notebooks (json files) and converts them to static html for viewing.
Is there any nice bundle of everything you need for ipython, for the Mac, that's both easy to install and uninstall?
/M | [TN]|B/
/ [TMN]|B/
Judging by the amount of fawning here, this guy must be a HN celebrity. Interesting post nevertheless!
I can only hope, one day, I'd be writing and publishing joyful little hacks like this, to such general applause, instead of eking out a living. I have to say I'm a bit envious here!
Well done to the dude. An inspirational post, in many ways.
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.
Seeing as how you already have a functioning install of ipython and a setup you're otherwise happy with, this is probably the easiest route.
Also, just so it's clear what's going on, ipython notebooks and (especially) format conversion are optional (but very useful) parts of ipython. They're not part of the core functionality, so `pandoc` isn't a strict requirement to build ipython.
Otherwise, as long as you don't mind switching the python interpreter, etc as well, look into Anaconda or Canopy. I'm not 100% sure if either comes with pandoc, but they're stand-alone scientific python distributions that make it a good bit easier to get ipython, numpy, matplotlib, etc set up.
But I've just recently installed all this, and have only kicked it around a little. Mostly, I wanted plotting.
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).
1. Parse the full text of some long book available on Project Gutenberg. Record every trigram that occurs. Frequency is irrelevant; we just want to know whether a trigram occurs or not.
2. Go through your text, counting the number of trigrams that didn't exist in the sample text. If the number of strange trigrams exceeds a threshold (for my project I used a threshold of 3, but you can tune this), reject the text as non-English.
Given the constant finite threshold I used, that does amount to a regex, but I don't recommend trying to write it out explicitly.
Presumably it would false-negative texts with neologisms and spelling errors and such.
There must be trigrams which simply don't appear in dictionary-English? Do you have results posted somewhere.
might be interesting to see how that stacks up against the other idea thread.
So as long as you can show that a program that is not finite in length will not halt in a finite amount of time (I think this is the case, but am not actually positive), I think that a rexex-finding-program-finding-regex should be possible to write, at least in principle (though not in practice).
However I think the most interesting result is mine :P
Although this is probably just pointless nitpicking on my part.
If p(x) means 'x is an integer', you could use the regex /^1$/ since it matches integers only (in particular, the integer 1). That's not sufficient, you need to match all integers.
edited:format