Poked.net

In some of my spare time, I am writing a program to automagically recognize text in one of those "prove you are human" confirmation steps for the game I am playing with Lauren. I am currently at the stage shown above. I can remove the lines exclusively, remove the dashes between the letters, detect the bounds of the word, and rotate the image so that the word is horizontal. Almost to the training step where I have a live person tell the computer the right answer a whole bunch of times to give the computer a bunch of examples to learn from. Fun stuff. Made possible by linux.

Problem of the day. You have some random binary matrix (a 2-D array of ones and zeroes) like the following:
10101
10110
00101
11111
10010

Now, the goal is to get all the 1's in every row to be consecutive. The only operation you can perform however is to rearrange the columns. The obvious solution is to try every arrangement of columns - but there are n! arrangements of n columns. In other words, after about 20 columns your problem takes a long time to solve. So thats no good. The solution is using a data structure called a pq-tree which lets you solve this problem in linear time. Except, there are no GPL pq-tree implementations available anywhere - despite the algorithm being over 40 years old. Grr. Well, after a week of working on the problem, there soon will be one.
The solution btw is:
01110
11100
00110
11111
11000

The next step is an extension of the problem. Not all matrices can actually be manipulated like this to achieve the wonderful consecutive one's property. You can you manipulate them instead by adding columns. Consider each row to be a set of colors(columns) that have to be consecutive in a drawing. As long as the colors are consecutive somewhere in that row, its ok - even if you have to repeat colors to make sure they are consecutive. The problem is now always solvable, but we want to repeat the smallest number of rows. Thats tricky. In fact, it is impossible to do without the factorial effort mentioned above. So, how can you get a really good approximation instead - fast. Thats what I'm trying to figure out.

Since Ed and I now communicate via my blog, to Ed:

I think I remember you telling me about a relative who collected the various periodic table elements. If that story was yours, you definitely need to read this great recount of just that:
Iridium

To anyone else interested in short, entertaining essays - click the link above.

Road Trip 2004: Andrew has been working in Phoenix at Honeywell all summer. They gave him two choices - fly out there free, or drive out there and get reimbursed for mileage/food/hotel both ways. I decided to join him for the return trip. Caught a 1-way ticket out to phoenix, and rode all the way home on his tab. We took the scenic route of course, but it was alot of fun.

Check out the photos. I found a new gallery type software thingy on my computer that will make browsing better than my previous approaches. Enjoy.

Its interesting looking through the logs to this site. Im bright enough to figure out who most of the people are who visit my blog. For example, my own ip address - when queried against nameservers, reveals very clearly that I am an NTC user in roankoe street apartments in blacksburg. It resolves to:
something.rs-brn-apthts.blacksburg.ntc-com.net (left the "something" part off intentionally). Anyway, many of my friends in the area I can pick out based on their apartment complex, or from emails they have sent in the past. Same goes for many people in greenville, as charter (the major cable internet provider there) does a similar thing with their nameservers. Its definitely interesting. I can see how often individuals look at my blog, and at what pages. Scary, huh? Sometimes I can even reason out pages that people have bookmarked from the patterns.

For the fun of it, I have rigged up a cute little thing to notify me when certain people view my blog. My blog will text message me when it happens. Mmm.