Tetris is Hard, Even to Approximate
Abstract: In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled squares; any completely filled row of the gameboard is cleared and all pieces above it drop by one row. We prove that in the offline version of Tetris, it is NP-complete to maximize the number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously filled and cleared), minimize the maximum height of an occupied square, or maximize the number of pieces placed before the game ends. We furthermore show the extreme inapproximability of the first and last of these objectives to within a factor of p^(1-epsilon), when given a sequence of p pieces, and the inapproximability of the third objective to within a factor of (2 – epsilon), for any epsilon>0. Our results hold under several variations on the rules of Tetris, including different models of rotation, limitations on player agility, and restricted piece sets.
head-mounted-display homebrew nerd-mounted-display wearable
by Wayne
leave a comment
Eyeglass Mounted Display in Ordinary Sunglasses
AE Innovations – Wearable Computing and Eyeglass mounted displays
Fairly sleek nerd-mounted display. It’s from a while ago. I’m linking to the Wayback Machine because he lost the images on his real site.
Restrict Google Image Search Results to Human Faces Only
Anyone need a bunch of face images? Fake ID makers? Looking to populate your facial recognition database?
With the imgtype=face parameter, Google Image Search restricts results to human faces only.
Example:
Search for Joe without imgtype=face
Search for Joe with imgtype=face
Now look way down in the results, like page 9. Imgtype=face is still faces, while the regular search includes things like coffee and beaches.
There’s more information at
Google Blogoscoped
american-express black-card centurion-card link wikipedia
by Wayne
leave a comment
American Express Centurion Card
Urban legends of a special, black-colored card offering dignitaries and celebrities unlimited spending power and after-hours access to high-end stores circulated in the 1980s. While the rumors were false, American Express decided to capitalize on them by launching the Centurion Card.
In the 2006 film Casino Royale, James Bond walks into The Ocean Club (an exclusive Bahamian resort), goes to the concierge, requests a room without a reservation, and simply hands the concierge a black credit card. This is likely a reference to the Amex Centurion.
Esoteric Programming Language Wiki
This is a wiki about esoteric programming languages.
This is a beaut. My personal favorite is only an idea, but it’s a Magic: The Gathering programming language.
(All the cards here are currently tournament-legal, and the decks are also legal (although not very strong)). The powers of the Phytohydras here form the Fibonacci sequence. I haven’t yet been able to make this produce output, however.
Hardware Random Bit Generator
Johnny von Neumann once said that anybody who contemplates arithmetic methods for the generation of random numbers is in a state of sin.
These are the notes and Usenet post about hardware random number generators.
Bicycle Powered Generator
Frequently posters on [misc.survivalism and alt.energy.homepower] will inquire about generating electricity using a stationary bike coupled to some sort of generator. Most replies are to the effect that while it’s possible to do this, the amount of power output by such a rig when pedaled by the average person wouldn’t be worth the effort. I wasn’t convinced that this idea was a lost cause. I decided to build one and see how well it worked.
I like that. Mythbuster-style, “Let’s try it” science makes for some pretty sweet reading.
xkcd » Blog Archive » Tools for dream typing
While I’m not a huge fan of posting “Hey guys! Look at xkcd!” I’m going to give in this time. You may not know this, but the author of xkcd also runs a blag. It’s pretty low-traffic, but usually a sidenote about the cartoon.
For example, tonight he posted a picture of a sleep keyboard meant for typing from your dreams. What does it look like? You’ll just have to click through . . .
Vim: Seven habits of effective text editing
I often times want to increase my Vim knowledge, but the main problem with most vim documentation that I find is there is too much of it! A good article with only a few new things in it actually ends up being incorporated into my vim spellbook more than a list of ten thousand incantations with little expository text.
This piece is written by the main author of vim, Bram Moolenaar. It focuses on coders.
On Sasquatch
“As far as I am concerned, the existence of hominids of this sort is a very real probability.”
– Jane Goodall