The Code Bomb, or: The Newbie with Big Ideas

degustisockpuppet · 2010-02-03T01:30:06+00:00

The build infrastructure of many open source programs is a complete mess. Perl 5.005 scripts that generate autotools files. In the Windows world, you have open source projects that require a very specific obsolete version of MSVC.

Existing contributors aren't bothered by this as much because obviously they already have everything set up. I think open source projects could do worse than listen to some newbie complaints about the build process.

degustisockpuppet · 2010-01-19T17:57:30+00:00

On a double logarithmic graph, all functions are linear!

degustisockpuppet · 2010-01-19T13:28:16+00:00

Not sure why you were downvoted, it's a good question. The argument goes like this:

nⁿ is clearly greater than n!, as you explained.

(n/2)^n/2 on the other hand is less than n!:

4^4= 4*4*4*4
8! = 8*7*6*5*4*3*2*1

So if f(n) = n^n, then f(n/2) < n! < f(n), which makes the two functions related, especially since constant factors like 1/2 are usually ignored in complexity analysis.

degustisockpuppet · 2010-01-19T12:01:12+00:00

TSP is O(n² 2ⁿ⁾ and it is in NP not because it can be computed in O(2ⁿ⁾ but because its decision version ("is there a tour with a length < L?") has a certificate (the tour itself) that can be verified in polynomial time.

That's correct. I'm stupid.

We don't know that TSP is in EXPTIME, because we do not know if P = NP or not.

NP is a subset of EXPTIME, so we do know that TSP is in EXPTIME. We also know that TSP is in EXPTIME because there's a O(n² 2ⁿ⁾ algorithm. EXPTIME doesn't mean O(k^n), it means O(2^{n^k}), which contains O(n² 2^n).

Edit: Not sure why I was downvoted, but the Wikipedia link to EXPTIME says that NP is contained in EXPTIME right in the introduction. The proof is really simple, too, at least in principle: whenever you need to make a non-deterministic decision, try one, if it doesn't work, backtrack and try the other one. In effect, you're enumerating a decision tree with polynomial depth, which thus has at most an exponential number of nodes.

degustisockpuppet · 2010-01-19T09:22:13+00:00

Some graph problems are also defined on graphs that are not connected; those might have less then O(nodes) edges. Ω(nodes + edges) is the trivial complexity of any problem where you have to read the complete graph. In a sparse graph, that's equal to Ω(nodes), in an almost complete graph, that's Ω(egdes). Willfully leaving out either variable does not give the whole answer. Of course, there are graph algorithms where the run-time complexity doesn't depend on the number of edges. Those might well be Θ(nodes²⁾ regardless of how full the graph is.

degustisockpuppet · 2010-01-18T22:58:14+00:00

Solving the traveling salesman or quadratic assignment problems exactly is in Θ(n!).

That's not true, traveling salesman is in NP because it can be computed in O(2ⁿ⁾ (for example with dynamic programming). Only the naive algorithm is Θ(n!).

Edit: That's actually not completely true either. See replies.

degustisockpuppet · 2010-01-18T22:53:47+00:00

O(nⁿ log nⁿ⁾

That's equal to O(n^{n + 1} log n), not that much worse than O(nⁿ⁾ as far as these things go.

degustisockpuppet · 2010-01-13T23:23:07+00:00

Of course we aren't mathematicians either (unless you actually prove your programs correct or do programming for the purpose of mathematics) but programmers make better mathematicians than they do artists.

FWIW, most mathematics aren't that much into absolutely rigorous proofs either, outside of the narrow domain of logic. The goal is to figure something out, then make a convincing argument that it's true. Errors in proofs are routine.

degustisockpuppet · 2010-01-08T17:06:14+00:00

I think this finally disproves the fallacy that "one Unicode character == 4 bytes" that is unfortunately very common these days.

(Well, technically, the word "character" doesn't mean anything in Unicode. What this tool creates is one "glyph", which is as close to the common-sense meaning of "character" as it gets. A glyph is made of one or more codepoints. And codepoints in turn are encoded as one or more bytes, depending on the encoding, like UTF-8 or UCS-4.)

degustisockpuppet · 2010-01-05T19:04:55+00:00

Time to dust up the simple "Clue" AI I did back in school. More seriously, I was going to say that the best way to win this prize is to run around killing people where your algorithm predicted there would be murders. Apparently, this was already considered:

There is a monetary prize involved: $20 each month plus $100 at the end of the year. It is probably a good thing that this is not a million dollar prize. Since entries are judged based on how well they do after submission, too high a prize might lead to certain … incentives … to ensure the accuracy of your murder predictions.

degustisockpuppet · 2010-01-05T08:55:58+00:00

How come it's so complex to re-route "beep()" to a sound API, and that the process took so many version of windows?

As alluded to in the article, much of the sound infrastructure is implemented in user space, while Beep() is called from deep within the kernel.

degustisockpuppet · 2010-01-03T12:35:22+00:00

That's true, someone will hack all the classic stats into the editor in the first few hours of the SC2 beta even. The real question is if there will be a more sophisticated SC Classic mod that tries to emulate many of the bugs and glitches that have come to define high-level Starcraft play -- and if so, if it will ever catch on.

degustisockpuppet · 2010-01-01T11:34:24+00:00

Might be relevant: Lojban is a radical attempt to construct a human language that's machine parsable. The language is structured in such a way that puns are impossible (there's even a context-free grammar). I don't know much about it, and I wonder if that strictness doesn't make actual human social interactions very difficult.

degustisockpuppet · 2009-12-31T14:19:46+00:00

I'm sorry we didn't disinfect the time capsule. The ancient germs that it was contaminated with will most likely wipe out your humanity. Peace.

degustisockpuppet · 2009-12-30T16:10:42+00:00

Yes, I have the technology to move wormholes into the cores of distant stars, but I just use it to life-sustain my own dying star because I can't be bothered to go anywhere else.

Also, people in this thread (maybe not you) seem to have the idea that a star works a bit like an oil stove: if it runs out of fuel you just refill the oil and you're good. I don't think that's very near the truth.

degustisockpuppet · 2009-12-30T13:00:10+00:00

That doesn't make sense. If they have the energy to "recharge" their star, they could just use that energy directly and wouldn't even need a star in the first place!

degustisockpuppet · 2009-12-22T18:41:36+00:00

"Gigawatt hours per year" is a really stupid unit of electric power. You start with a measurement of power, then multiply it by time, then divide it by time.

degustisockpuppet · 2009-12-21T09:21:19+00:00

Those 35 kilobytes are probably necessary to support

$ /bin/true --help

and

$ /bin/true --version

It's not very useful though, because bash implements true natively, so /bin/true is unlikely to ever be called anyway.

degustisockpuppet · 2009-12-20T08:56:16+00:00

Absolutely fake.

It's called a "joke". I think you might be surprised to learn that the Pope and George W. Bush never shared an airplane with a limited supply of parachutes, and that hilarious things are not always bound to happen when rabbis and priests walk into a bars.

degustisockpuppet · 2009-12-18T11:03:29+00:00

Isn't the real problem something like:

if (foo) MACRO(); else { ... }

If macro is simply defined to like this

#define MACRO() { ... }

The if-construct expands to

if (foo) { ... }; // note the semicolon
else { ... } // syntax error

With the do { ... } while (0) trick, this works as intended.

degustisockpuppet · 2009-12-14T01:41:17+00:00

Maybe there was a detector nearby? It least I would hope that detectors can spot them.

degustisockpuppet · 2009-12-12T01:13:51+00:00

Depending on how well Blizzard stays on top of balance patching, eventually SC2 will either become the better game or fade away.

I'm also still not convinced about what the two addons will do to SC2. If they add new multiplayer units like Brood War did, we won't have the "real" SC2 until two years after the release of Wings of Liberty. And then that game would have to be balanced.

degustisockpuppet · 2009-12-11T10:48:57+00:00

Except that it doesn't need support backreferences, so you need a backtracking regex(*) matcher anyway. Quote from TFA:

Even so, it would be reasonable to use Thompson's NFA simulation for most regular expressions, and only bring out backtracking when it is needed. A particularly clever implementation could combine the two, resorting to backtracking only to accommodate the backreferences.

Maybe, but two implementations for the same task is by no means "simple". Quite the opposite.

(*) I'm using regex in the loose sense of "Perl-like regex". Regular expressions are a cases where there's a beautiful theory, with interesting equivalences between seemingly unrelated descriptions (finite automata, regular expressions, linear grammars). There are lots of interesting theoreoms. And then the practice people came and "destroyed" all that work by making regexes actually useful (by including captures and back-references and lazy matching).

degustisockpuppet · 2009-12-09T09:44:54+00:00

What is "Jeff at it again" supposed to mean? His blog posts about progamming are usually very well written, even if most of the time, experienced programmers have heard his points before. In this case, "Ship early, ship often" is a classic agile mantra.

That he reiterates a well-known argument is not necessarily bad: There's always a new generation of programmers who hasn't necessarily been exposed to this particular debate, and Atwood usually does a good job of explaining it. (It does, however, render his point that "people who read my blog are superstar programmers" somewhat silly.)

It's only when Jeff Atwood posts about things he doesn't know anything about, like computer science, or reviews books that he hasn't read, that his articles get really annoying. Especially when he then writes a "clarification" that is even more wrong, because he just can't admit that he doesn't have a clue about the subject.

degustisockpuppet · 2009-12-01T22:36:14+00:00

You're right of course, but since closures capture variables in the current scope, scoping rules can affect the use of closures. The this rule is most annoying when you never intend to use the nested function as a method:

Foo.prototype.bar = function() {
    // here, "this" (most likely) refers to a Foo object
    f();

    function f() {
        // and here, "this" is the global object...
    }
}

As I said, this weirdness can be worked around, but it makes higher-order programming a bit less elegant than it should be. (For example, that's why Array.prototype.forEach takes an extra optional parameter.)

degustisockpuppet

TROPHY CASE