P = NP doesn't matter

For the last half-century, every practicing programmer has explored the space of efficient algorithms, trying to find ways to make computers be useful, faster. In the United States, there were about 450000 programmers (excluding managers and educators) in 2002. Assuming each works 40 hours a week, and that the number of programmers has not decreased in the subsequent decade, that's (conservatively) 12 billion man-hours spent programming in the last decade, in the United States alone.

That's a lot of time spent experimenting with low-order polynomial-time algorithms. It's tempting to take this as evidence that \(\text{P} \ne \text{NP}\), but this is fallacious: none of this activity has looked at algorithms with excessively large constant factors, or ...

Read more

Wraith: A Bananagrams™ Variant

First, for those who haven't heard of Bananagrams: it's Scrabble without the board. At any time each person has an equal number of pieces as any other player, and the first player to finish using all their pieces with none left in the common pile, wins.

There's another game, "ghost", in which players construct a word one letter at a time, by appending one letter each turn. The player who completes the word loses; however, the more frequently invoked rule is that a player who suspects there is no word beginning with the given letters may "challenge" the previous player. If the previous player cannot produce such a word, she loses.

Wraith is the unholy stepchild of ...

Read more

Haskell functors versus "real" functors

Haskell's Functor type class is inspired by the notion of a functor from category theory, but expresses a rather more limited concept.

A category, conceptually, is a set of "objects" that are linked by "arrows". For our purposes, those objects are types, and those arrows are functions. Each function maps one type to another. (Tuples are types themselves, so this model handles functions with multiple arguments as well.) Note that the instances of types, like the number five and the string "Hello", are not included explicitly in this model: we're only concerned with the types and the relations between them.

In Haskell, the "universe" category is known as Hask. This is the category of all types, and therefore ...

Read more

Autodetecting correct quote direction in TeX

\(\small\TeX\) annoyingly lacks the ability to automatically detect whether a straight quote (") should be rendered as a left quote (“) or a right quote (”). Instead, it treats straight quotes in the input as right quotes, and requires backticks to be used to render left quotes.

Like ``this''. Or ``this".

This does not seem so bad; however, it does require a modicum of awareness on the part of the author, who has to remember to actually use backticks. That sounds a bit like effort, and in my case, that's just not reasonable. Much better if there was a way to make the quotes automatically detect which direction they should go.

Fortunately, \(\small\TeX\) provides a mechanism for changing the "class ...

Read more

Restoring Clipping Region in R Graphics

R's default graphics package (bundled with all installations) is a powerful enough low-level tool, but it's often not immediately obvious how to accomplish certain ends. In particular, although most graphics parameters can be gotten with par, there's no way (at least as far as I can tell) to get the current clipping region, which is set with a standalone function

clip(x1=0, x2=1, y1=0.1, y2=0.9)

rather than using par, which would arguably be more consistent.

par(clip=c(0, 1, 0.1, 0.9))

This means that there's no clear way to temporarily set, and then restore, the clipping region. It turns out, however, that the usr parameter contains the ...

Read more

Page 1 / 11 »