11–20 of 75 posts
I thought it was going to be meta-meta-regex golf, and couldn't imagine how that would be possible. But meta-regex golf is an interesting exercise, and is far more tractable. :)
I am not sure why Norvig omits president Obama. That said, "[mtg]a" does match him, so at least Munroe tries.
His source page doesn't list Obama, for whatever reason. http://www.anesi.com/presname.htm
key=lambda c: 3*len(matches(c, uncovered)) - len(c)I thought it was going to be meta-meta-regex golf, and couldn't imagine how that would be possible. But meta-regex golf is an interesting exercise, and is far more tractable. :)
"Write the shortest regex that only matches programs that successfully generate the shortest regex given lists of inclusions and exclusions."
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.
Can someone explain what does this line mean and why does he use it as heuristic? 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.
Earlier quoted context omitted.
"Write the shortest regex that only matches programs that successfully generate the shortest regex given lists of inclusions and exclusions."
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 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).
Can someone explain what does this line mean and why does he use it as heuristic? key=lambda c: 3*len(matches(c, uncovered)) - len(c)
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"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…
However I think the most interesting result is mine :P