Disappointing that this otherwise excellent discussion does not include the teleporting turtle, which is known to be more efficient (only in the constant - it's still O(n)) than his last solution as presented. You can find a discussion here:
http://news.ycombinator.com/item?id=1068715