thraxil

It was fantastic, as always! Waes hail!

It's been a busy month. The NaGraNoWriMo was a success. I ruined my health, alienated my family, and none of my friends remember what I look like, but I made it all the way to 50 pages after all.

The result, "Error And Annihilation", is up on Flickr here. It's also available to order in dead tree format.

One book just wouldn't be enough for me this year though. So I also now have available Myopica, which is the sequel to last year's Nearsighted and Obsessive-Compulsive and contains pretty much everything I've done in 2007 (except what's in Error And Annihilation). There's also a corresponding (though not sorted) flickr set for convenient browsing.

As usual, those are both available as free PDF downloads and the books are for sale at cost (ie, I make no money on any of this). Happily, Lulu.com also now has an option for Public Domain licensing so that's what they are.

Again, thanks to Marc Raymond for laying them out and making everything look more professional than it is.

My NaGraNoWriMo shall now commence.

I've been convinced to scale back my ambitions to just 30 pages, or about three to four hours per day instead of my original goal of 50 pages.

I've got a fresh large Moleskine sketchbook with 30 pages pre-numbered, a pack of nonrepro blue leads for my mechanical pencil, a small collection of Sakura Micron pens, and I'm ready to go.

My working title for the book is "Error And Annihilation". I'll try to post an update now and then, but no guarantees.

The other day, I stumbled across Mark Nelson's blog post describing a fairly simple NPR word puzzle: "Take the names of two U.S. States, mix them all together, then rearrange the letters to form the names of two other U.S. States. What states are these?"

Mark Nelson is a programmer, so his first instinct of course was to write a small program to solve it. Mine too. I immediately stopped reading his post, opened a new emacs buffer and spent five minutes coming up with this:

#!/usr/bin/env python
states = ["alabama","alaska","arizona","arkansas","california","colorado",
          "connecticut","delaware","florida","georgia","hawaii","idaho",
          "illinois","indiana","iowa","kansas","kentucky","louisiana",
          "maine","maryland","massachusetts","michigan","minnesota",
          "mississippi","missouri","montana","nebraska","nevada",
          "newhampshire","newjersey","newmexico","newyork","northcarolina",
          "northdakota","ohio","oklahoma","oregon","pennsylvania","rhodeisland",
          "southcarolina","southdakota","tennessee","texas","utah","vermont",
          "virginia","washington","westvirginia","wisconsin","wyoming",]
seen = dict()
for state1 in states:
    for state2 in states:
        if state1 == state2:
            continue
        letters = list(state1 + state2)
        letters.sort()
        key = "".join(letters)
        if seen.has_key(key):
            (old1,old2) = seen[key]
            if old1 == state2 and old2 == state1:
                continue
            else:
                print "found it: %s + %s, %s + %s" % (state1,state2,old1,old2)
                exit(0)
        else:
            seen[key] = (state1,state2)

Sure enough, it gave me the answer (and like Mark Nelson, seeing it made me realize that it probably would have been even more productive to just think about it for a minute instead of writing the code).

To me, that Python code is about as simple and direct as it gets. There's nothing clever going on there. Just loop over the cartesian product of states x states, skip a couple obvious cases and then normalize the names of the states by sorting the letters and put them into a dictionary. As soon as you hit a combination that's already in the dictionary, you have your answer.

That approach to me would qualify as a "naive" or "brute force" approach. I figured there might be a more optimized approach, but with only 50 states it wasn't really worth optimizing any more. Running it took all of 18 milliseconds.

When I went back and read the rest of the blog post, my jaw dropped. His first pass, in C++ involved a quadruply nested loop, STL libraries, and was taking upwards of an hour to run. Looking at his code, he really took the notion of a "brute force" approach to a level I hadn't even considered. His second and third passes improved the runtime and even simplified the code, but they still run on the order of a few seconds. That's for a compiled, low level language. My Python code written without any particular thoughts toward efficiency running in an interpreter (so the time of starting up the python process, parsing the code, and interpreting it directly, line by line without compiler optimizations are all included in the running time) was beating it by a couple orders of magnitude.

The key, of course, is the algorithm. Python, like Ruby, Perl, and other relatively high level languages, has supports a dictionary (or hashtable if you prefer) data type at the syntax level. As a result, anyone programming in one of those languages quickly learns how to make the most of them and becomes familiar with a number of idioms, including the one I used of testing for uniqueness by keeping a 'seen' dictionary, inserting keys one by one and looking for a collision. It's dead simple, commonly used in scripting languages, and extremely efficient since inserting into a hashtable is O(1) and tends to be one of the most finely tuned parts of a scripting language's interpreter/VM.

There's nothing Python specific about the algorithm. In fact, in the comments on the post, Vince Huston submits a C++ solution that's basically identical to my approach (and probably outperforms everyone else handily). If I were forced to solve the same problem in C++, I would probably have come up with something similar. I would not be at all surprised if Vince Huston has had some experience coding in scripting languages and Mark Nelson hasn't.

The point isn't that Mark Nelson is a bad programmer. Far from it. Looking around at the rest of his site, at articles like his explanation of the The Byzantine Generals Problem (which was how I ended up on his site in the first place), and at the books he's written, I'd guess that overall, he has more breadth and depth to his understanding of algorithms and programming than I do.

My point is really just to repeat the tired, broken record cry of advocates of higher level languages that 1) using a faster, more appropriate algorithm will usually go much further in optimization than low level optimizations (using a compiled language, static types, fretting over clock cycles in an inner loop, etc) and 2) learning different programming paradigms, languages, and idioms will improve your programming even if you end up going back to a lower level language. In this case, some familiarity with dictionary idioms common in scripting languages helps immensely in producing a fast, simple solution.

Another comment on his post goes even further. Tom Moertel submits a solution implemented in Haskell. From a performance standpoint, it's pretty much the same approach as mine, using a dictionary (in this case, Haskell's Data.Map library) to do the comparisons on normalized strings. What makes it a really nice solution though, is that he approaches it by starting with a "clusterBy" higher order function that takes a signature function and a list and returns a list of groups clustered by the signature (my explanation is bad; his examples make it much more clear). Essentially, instead of directly solving the problem, he creates a general purpose tool which can then trivially be applied to the specific problem at hand. clusterBy is the kind of function that I could see being useful to other problems. So not only does he end up with the solution to this problem, he also ends up with a useful tool to make future programming tasks simpler. Haskell's smooth support of higher order functions makes this a natural approach and it seems to be the way that proficient Haskell programmers end up taking on most problems.

Python had the good taste to steal a few items from Haskell's bag of tricks though, so I was inspired to try a Python version. Here's a rough equivalent of clusterBy:

def cluster_by(f,lst):
    transformed = [f(x) for x in lst]
    d = dict()
    for t,i in zip(transformed,lst):
        d.setdefault(t,[]).append(i)
    return d.values()

Not as pretty as the Haskell, but works essentially the same way.

Then, to solve the original problem, we need a normalize function:

def normalize(t):
    letters = list(t[0] + t[1])
    letters.sort()
    return "".join(letters)

It takes the tuple of two state names, sorts all the letters in them and returns that as a string. The final piece is just to apply cluster_by with the normalize function to the cartesian product of states x states and find the resulting entries with multiple entries (and since I was going Haskell-style, I decided to use list comprehensions instead of for loops as well):

clustered = cluster_by(normalize,[(x,y) for x in states for y in states])
print [x for x in clustered if len(x) > 2]

It runs in 25 milliseconds on my machine, so slightly more overhead than the procedural approach, but close enough to not matter and, IMO, it's cleaner and would lend itself more to further reuse of the cluster_by or normalize functions.

So first knowing an idiom from a scripting language can produce better C++ code (see Vince Huston's solution), then taking a lesson from Haskell I'm able to come up with better Python code.

I'm waiting for a Prolog programmer to come along and smoke everyone next.

At some point a while back, my little meditational abstract doodles started occasionally getting boxes around them. When there were several of those on a page, I noticed that they sort of resembled the panel layout of a comic. I kind of liked that so I experimented more in that direction, playing with deliberate panel layouts and borrowing from the vocabulary of comics and sequential art while keeping my subject matter abstract. Now I've got a fairly large collection of these abstract comics and it's a style that I think is still interesting and rich for experimentation.

Lately I've found myself in several conversations with friends about National Novel Writing Month (NaNoWriMo). The executive summary if you're too lazy to click the link and aren't familiar with it: you give yourself the month of November (30 days) to write a 50,000 word novel. It doesn't have to be good or make much sense or anything, it just has to be started and finished within the month. I've always thought it was a cool idea. A bunch of my friends have attempted and at least one has even successfully completed a NaNoWriMo.

As a writer, I'm not really interested in writing fiction so it isn't something I'd be up for myself. The idea continues to intrigue me though so I've decided that this year I want to try to do an abstract graphic novel NaNoWriMo style. A "NaGraNoWriMo" I guess (calling it a "NaAbsGraNoWriMo" would just be taking it too far.)

Obviously, I can't use word count as a metric for my graphic novel. Laying out, drawing and inking a full page of panels I've found takes me about three to four hours with the level of detail that my style involves. The notion of "a picture is worth a thousand words" I think actually works out pretty well for my purposes. 50,000 words = 50 pages = 1.67 pages per day = about 6 hours per day of me drawing for 30 days. I think that's a similar magnitude of challenge to what other NaNoWriMo writers are attempting.

That's the goal, anyway. I've got a lot of other things going on in November so it's not going to be easy to find all that time. I'll try to post the pages to flickr as I go, but scanning and posting takes time that I could be drawing so that will be a lower priority than finishing.

If you don't see me outside my apartment or hear from me next month, now you'll know why.

[Yes, I know that someone else has used the term "NaGraNoWriMo" for something similar. Their approach was to write a "script" for a 175 page graphic novel. I honestly don't know quite what a script for a graphic novel is but I'm pretty sure that it wouldn't work for an abstract one. I like my idea better.]

I'm in the office now on a Saturday enjoying the free air conditioning and functioning ceiling, which, at the moment, my apartment is lacking. I don't have anything else pressing to do at the moment so I figured I would take this opportunity to post an all too rare update on the miscellaneous stuff going on in my life for those of you that I'm not in frequent contact with.

For the most part, it's been pretty quiet here. I work a lot, paint and draw obsessively (I think there should be enough material for a Volume 2 soon, in the meantime, it usually ends up on flickr), and occasionally go out for beers, movies, or concerts with my friends. I've even been running semi-regularly.

I currently have two plants which, by some miracle, I haven't managed to kill yet with my neglect.

In July, a couple coworkers and I went skydiving. I can not possibly recommend it highly enough if you've never done it. I liked it for a very different reason than I expected. When you jump out of the plane, there's about a minute of free fall which is pretty exhilarating. You don't know which way is up for a few seconds, then you're assaulted by 120mph wind and deafening noise. Your brain sort of shuts off because it can't handle the intensity of the sensations which it has absolutely nothing in memory to compare to. I actually kind of forgot how to breathe during free fall and had to consciously remind myself. That was fun in its way, but I'm not an adrenaline junky type so it wasn't the big draw for me. When your chute opens, you're suddenly thrown into a different universe. In a second or two, you go from free fall to absolute stillness and dead silence. You're far enough up that you have no sensation of movement at all and you can see for hundreds of miles to the horizon in all directions. You realize that there's basically no other solid matter anywhere within thousands of feet of you in any direction. It's an amazing sense of serenity and calm more powerful than anything I've ever experienced with yoga or meditation.

One thing I don't recommend is getting an ear infection. I was pretty much knocked out of commission last week with strep throat that turned into an ear infection. The strep was quite pleasant in comparison. The ear infection was several days of continuous, unrelenting, maddening pain. Pain killers seemed to have no effect. If you've never had one, it's basically like jabbing a pencil into your ear, sharp end first, then giving it a little tap with a ball peen hammer about once a second. For days. Antibiotics eventually were brought in and made short work of the infection, but it's not an experience I would ever like to repeat.

On the technical front, I've been continuing my climb up the Erlang learning curve. The recently published book by Joe Armstrong has been a big help. I'm particularly smitten with Mnesia at the moment and I also see the OTP framework being very useful to me in the future. I've prototyped some simple microapps with Erlang and Mnesia and am scheming on how I can sneak some of it into work.

Speaking of work, we've been up to some cool stuff. I spent a couple weeks converting our whole (modest) server infrastructure to virtual servers running on Xen. So far it's gone really smoothly and it should make things even more reliable and flexible in the future. I'm really impressed with Xen. We evaluated VMWare as well and it has some advantages, but for our situation, we found Xen to be more than adequate performance-wise and much simpler to deal with (I'm vastly more comfortable with arcane Unix commands than point and click stuff. YMMV).

We also recently got a nice grant from NIMH for a very worthwhile HIV prevention project. Sadly, I don't think most of the grant money is going directly into my salary. We've got more cool projects in development too.

I've also been psyched that we recently hired a new programmer to help out with our general world domination plans. She's been kicking ass and taking names, rapidly getting up to speed with the Python and TurboGears stuff we use, and she's an industrial fan to boot. I expect the orbital laser to be operational very soon.

With that addition, we're up to four desktop Linux users in the office now (all Ubuntu) with some others experimenting, which is a nice change from two years ago when it was just me.

Finally, it appears that the Japanese convenience store in my neighborhood is again carrying Choco Monaka Jumbo ice cream bars after months of being out of stock. I was beginning to panic.

For once, I have a good excuse for not posting anything here lately. Usually I don't post for months at a time and it's just out of laziness and a lack of anything interesting to write about. I'm not saying that wasn't also the case this time, but this time I can at least pretend it was something else preventing me from posting.

Many of you noticed that thraxil.org was offline for the last month or so.

The root cause was that registerfly.com, the registrar that I'd registered my domains through, lost their ICANN accreditation for generally being sleazy. They transferred the domains in their control to a couple other registrars. Last time I renewed thraxil.org, I paid for a couple years at once to minimize the chances that it would expire on me when I wasn't paying attention. Somehow, that got lost when they transfered it and the domain expired in June, a year before I was expecting it to.

Normally, a domain expiring isn't that big a deal. ICANN gives you a 40 day grace period where the original owner is allowed to renew their domain without penalty and domain squatters can't get it. This generally works pretty well to eliminate the really predatory domain squatting. However, you can only renew the domain through the original registrar. This obviously was a problem for me. I couldn't renew it through registerfly since they were no longer accredited. Registerfly couldn't give me the transfer authorization codes that I needed to transfer the domain to a different registrar because the domain was expired. As far as I can tell, there just isn't a clear procedure in place for how to deal with the situation of an expired domain on a defunct registrar.

I won't even bother going further into what I had to do to get everything back up. Obviously it involved a lot of bureaucratic nonsense that made me want to embrace violence as a problem solving technique. There was also a round of me having to prove my identity via several easily forged tokens (screenshots of my account page? emailing a scan of my photo id? ) that didn't exactly make me feel secure with the general process.

Anyway, we're back online now so I have no more excuses.

I've been drawing and painting a lot in the last couple years. Obsessively, perhaps.

A few months ago, I was looking at the shear volume of work I'd produced and realized that it was actually enough to fill a book. That idea kind of stuck with me and I became fascinated with the concept of having my own book. As an unknown, there was no way any publishing companies out there would bother with me, and I didn't really relish the thought of having to deal with a publisher anyway. So I did some research and found that technology has recently made a print on demand model actually pretty feasible.

Lulu.com looked like the best of what's out there so I ordered a couple of random books from their site to check the quality and I was pretty impressed. The prices are a little high, but considering that not too long ago it really wouldn't have been financially possible to publish a book without doing a print run of hundreds of copies, it's not too bad.

I don't really know jack about anything print related so I roped in some friends to help me photograph the paintings that were too big to scan, lay everything out and put it into a pdf with the right settings, and design a professional looking cover. They came through for me and put together a complete package that makes it look like I'm actually a real artist or something. Neat.

Anyway, it's now available. You can order a copy directly through lulu.com's online store.

The 158 page color printed 9x7 inch paperback version is $28.23. That's actually just the base manufacturing cost that lulu charges. I make no profit whatsoever on the book. This is purely a labor of love for me, not a money making venture. There's also a free PDF download available if you either want to preview it or if you have access to your own book printing equipment and want to print it yourself.

The license on the book according to the site is the Creative Commons Attribution License 2.5 but that's only because Lulu.com's publishing interface didn't include the option for the Public Domain which is what I prefer. In other words, do whatever the hell you want with the book. I don't care. I'm just happy that it exists. If you like it, you can buy me a beer some day.

Again, thanks to Catherine, Marc, and Jessica for helping me out on this, one of my more involved crazy schemes.

For the third year in a row, MFR has been nominated for a PLUG Award. This year, they created a new "Best Music Blog" category separate from the "Best Music Website" category. That means that our little operation consisting of a couple college friends with a Movable Type install and a bit of free time isn't competing directly against sites like Pitchfork or MySpace who have, like, budgets and employees and such.

We're always happy just to get nominated. This year maybe we might even win. At the very least, it'll be a pleasant change to lose to someone cool and deserving like brooklynvegan, MOKB, or stereogum instead of the mega-corporate MySpace like we did last year.