Archive for September, 2009

Best. Spam. Ever.

Good morning. Realize that true happiness lies within you. Waste no time and effort searching for peace and contentment and joy in the world outside. Remember that there is no happiness in having or in getting, but only in giving. Reach out. Share. Smile. Hug. Happiness is a perfume you cannot pour on others without getting a few drops on yourself.

I am from Samoa and learning to read in English, please tell me right I wrote the following sentence: “Infrastructure is a nordic holding member financing reflected by mastercard.”

No comments

Captchapot

Seems like the font change to the CAPTCHA wasn’t enough to hold off the spambots.

Now that I’m thinking about this clearly, the spam doesn’t actually annoy me much. What annoys me is not knowing how they’re doing it. So, instead of trying to stop them, I’ve started logging CAPTCHA attempts. Updates to come if and when I learn anything new.

No comments

CAPTCHA fail

In the last few days I’ve been getting spam comments!

This is vaguely surprising, because I have a home-made CAPTCHA (more of an interesting programming exercise than something I desperately needed, but still). My vague understanding of these things is that CAPTCHA-aware spambots are usually narrowly targeted at a particular class of them that are either widely used, or guarding a particularly lucrative high-traffic site. So the fact that spam has been getting through means that one or more of the following is true:

  • My blog is far more popular than the number of real comments I get would seem to suggest.
  • My CAPTCHA resembles a widely-used class of CAPTCHAs closely enough that a generic attack on them is working against mine.
  • There’s some security hole in the CAPTCHA plugin, or WordPress, or some other means I don’t know about to post a WordPress comment that’s allowing spambots to bypass the CAPTCHA.
  • A wide range of different people have recently taken an interest in my blog, all of whom have a peculiarly similar tendency to make comments that are irrelevant to the post in question (but would like to draw my attention to various services to earn me money, enhance my manliness, or provide me with downloads of varying legality).
  • Somewhere, a spambot has gained sentience.

I’ve changed the font in the CAPTCHA to test the first two hypotheses.

4 comments

Sorting cards

For a while now I’ve had my own manual sorting algorithm that I use for, for example, sorting cards.

Actually the thing I most often end up sorting is card sleeves. Our Magic drafting group, being a highly distilled collection of nerds, draft into sleeves that are marked with the pack (A-C) and pick order (1-15), so that we can reconstruct and analyse the draft afterwards. So at some point before every draft I need to un-sleeve the previous draft, then sort the sleeves from A1 to C15.

Now… there’s a whole branch of computer science devoted to sorting algorithms (and by “branch” I mean “volume of the Knuth books”), but I’ve never come across any kind of systematic advice for sorting manually, i.e. without the convenience of having a computer instead of a brain and a bunch of digital artifacts instead of some physical pieces of plastic or cardboard. Most people just tend to sort in an ad-hoc way that vaguely resembles an insertion or selection sort. Occasionally I’ve seen someone attempt a radix sort with playing cards (into numbers, then into suits). If you watch this lecture you’ll see someone try to do a bubble sort with a bag over his head.

My manual sorting algorithm isn’t, as far as I know, a well-known programmatic sorting algorithm. You probably wouldn’t want it to be. It involves a variable number of variable-length lists, and doesn’t perform obviously better than a whole class of O(n2) algorithms that are in-place and much easier to implement. But it has the advantage that, for input that’s approximately O(a deck of cards), its space complexity is roughly O(a small area on my desk).

Here’s the algorithm. It’s in two passes.

  1. Take a card from the deck. Look for a pile on the table (initially there are none) whose top card is lower than the card you’re holding. Put the card on face-up top of that pile. If there’s no such pile, put the card in a new pile. Repeat until the deck is empty.
  2. Find the highest card among the top cards of the piles on the table. Move that card to the deck. Repeat until there are no piles left.

That’s a pretty sparse explanation. I might take a shot at making a video with actual cards – not that I expect it to be very useful, but it would also serve the purpose of playing with the 5D Mk II’s video mode.

One interesting thing is that the algorithm sort of takes advantage of the fact that a human can pick one from a handful of cards or piles at a glance in roughly constant time – or, at least, it doesn’t quite feel like a linear search because you quickly pick up ad-hoc shortcuts to find the right pile. (Also, the overhead of physically moving the cards around, which you can’t get away from using any technique, outweights the time it takes you to find the right pile.)

Even if you do end up doing a linear search for the right pile, the time complexity isn’t too bad. Worst case is quadratic, where the cards start in reverse order and each card ends up in its own pile. Best case is linear, where the cards start in order and all the cards go in one pile. The expected complexity for shuffled cards is… I dunno, I haven’t worked it out. The important factor is the average number of piles you end up with, which is complicated. I’d guess it works out to something like √n, which would make the whole thing O(n3/2), maybe. You could look at it as a selection sort with a probabilistic speedup for the “selection” bit.

Anyway, that’s how I’ve been sorting card sleeves for a while. I hope someone found that interesting. And if this is acutally a well-known algorithm, let me know what it’s called. (Haven’t really looked for it myself yet. My Knuth books are at work at the moment, so I might check there on Monday.)

No comments

Wonder Boy in Monster Land; or, How The Hobbit Should have Ended

dragonwasrobot

No comments

Cate Blanchett injured on stage

Well it’s not every night you get to see Owen Lars hit Galadriel in the head with a radio.

We saw a preview performance of A Streetcar Named Desire tonight… well, some of it anyway. As near as we can tell, Stanley (Joel Edgerton) was supposed to throw a radio through a window, but fumbled it and hit Blanche (Cate Blanchett) in the head before picking it up and taking another swing. (Edit: At the window.) The show went on for a couple of minutes – it was the start of a brawl, so she was supposed to run off stage anyway (or if she wasn’t, they covered it really well) – before they called a break, and later announced that they wouldn’t be able to continue. There were already cameras outside the theatre by the time we left.

This will be a more memorable night than it would have been otherwise. Arguably I even found it more engaging. Not sure what that says about me. Hmm.

No comments

Prediction

Within ten years, GPGPUs and general processing will converge to the point where you can boot Linux on a graphics card.

No comments

Rubikry

Conversation I just had at work:

Me: “If they held a convention for fans and makers of Rubik’s Cube-related puzzles, would they call it Rubicon?”

Him: “I’d be cross if they didn’t.”

Groan.

Anyway, here are two cube-related items of interest that I’ve come across in the last 24 hours.

Item the first:

Item the second:

No comments

« Previous Page