51–60 of 75 posts
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.
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…
So long as the unrelated arbitrary program is of finite length, and the regex golfer / arbitrary program composite is running on a machine with a finite amount of state, the halting problem can be solved by running each program for 2^(bits of state) steps or until a state is repeated. 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 c…
I am not sure why Norvig omits president Obama. That said, "[mtg]a" does match him, so at least Munroe tries.
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.
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.
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.
What tool does Norvig use to create this json file? Does iPython have this as a feature (somehow allowing formatted text)?
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 ". 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.
Earlier quoted context omitted.
Yes, I love expressions as this one: winners, losers = (winners - losers), (losers - winners)
Was that in an earlier version? I can't find that in the article now.
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.
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