Category Archives: Computers

Free Stuff! Come ‘n Git It! (Part 2)

I’ve created a couple more git depots with some rather old code that has been written and open sourced for quite some time… but just never shared.

One is a simple C-based command-line utility to quickly fix line endings for text files. It can read and write text files that have DOS, UNIX or Mac line endings. It’s very simple and quite peppy, and does a simple check for binary files before proceeding, so you can use it with confidence. It’s called “fixle”… very quick to type, fast to use. It replaces files in place. Developed on Mac OS X, it should work on any UNIX.

http://github.com/richardkiss/fixle/tree/

Another is a pair of Core Audio utilities for Mac OS X that provide a sort of “device” for audio: speakerpipe (which lets you dump data to the speaker) and mikepipe (which dumps data from the mike).

http://github.com/richardkiss/speakerpipe-osx/tree

Ideally, the functionality in speakerpipe should be integrated into the Mac OS X build of the very useful command-line utility sox so it can play sounds on the Mac. (Hmm, some browsing of the project seems to indicate that this functionality is coming.)

Both of these were written years ago and just never released into the wild. I release them, with BSD-style licenses, with the hope that they will be useful. No warranties though suckah!

Google Code (Peanut Butter and) Jam

Last Friday, I participated in the Google Code Jam, a programming puzzle contest sponsored by Google. It was the first qualification round, and I was very happy with how I did, coming in 74th in my heat (there were three heats, and mine had almost 3000 participants).

There were three problems, each with two data sets. The last problem was really more of a math problem, which I figured would have given me more of an edge because most of the time when I cheat on my second love, computers, it’s with my first love, math. However, I couldn’t complete it in the time allotted. But I also couldn’t stop thinking about it. I eventually came up with a solution which I’ll share here.

It’s problem C in round 1A (start here), but essentially, you have to find the last three digits before the decimal point for the number (3 + √5)n where n is a whole number that can be very large (up to two billion).

This means you cannot calculate the whole thing; it would contain several hundred million digits, which would use most of RAM just to hold the representation. So you have to figure out a trick.

Here’s what I came up with (too late to submit). Let An = (3 + √5)n and Bn = (3 – √5)n. Observe that An = Xn + Yn√5 for some series X0, X1, … and Y0, Y1, … where each of Xn and Yn are whole numbers. You can show this easily by induction. You can show a similar thing for Bn; in fact, Bn = Xn – Yn√5.

This means that An+Bn = 2Xn.

Notice that (3 – √5) < 1, so Bn < 1 for n>1, and goes towards 0 very quickly. Since An = 2Xn – Bn, we can calculate An by calculating 2Xn and subtracting a “small” number… that is, the last three digits of An are the same as the last three digits of 2Xn-1.

So all we need to do is figure out Xn!

We know that X0 = 1, Y0 = 0. An+1 = An(3 + √5), so

Xn+1 + Yn+1√5 = An+1 = An(3 + √5) = (Xn + Yn√5)(3 + √5) = (3Xn+5Yn)+√5(Xn+3Yn)

so separating rational and irrational parts yields the pretty recurrence relation Xn+1 = 3Xn + 5Yn and Yn+1 = Xn+3Yn.

That means Xn+1 and Yn+1 depend only upon Xn and Yn. Since we only care about the last three digits, that means that there are only 1000*1000=a million different combinations of Xn, Yn, and thus, the series must repeat in fewer than a million iterations. It shouldn’t be too hard to find a repeat.

Here’s the Python code to find the cycle length:

def _a_b_n(n):
    if n == 0:
        return 3,1
    a,b = a_b_n(n-1)
    return ((3*a+5*b) % 1000, (a+3*b) % 1000)

CACHE={}
def a_b_n(n):
    if not CACHE.has_key(n):
    CACHE[n] = _a_b_n(n)
    return CACHE[n]

F={}
for i in xrange(int(1e6)):
    k = (Xn, Yn) = a_b_n(i)
    #print i, a, b, (2*a-1)%1000
    if F.has_key(k):
    #print "repeat: %d, %d" % (i,F[k])
    break
    F[k] = i

cycle_length = i-F[k]
print "cycle length is", cycle_length

When you run this, it takes less than a tenth of a second to figure out that the cycle length is 500, and A503, B503 = A3, B3. So now it’s easy! Calculating the first 503 terms is enough.

Here is the rest of the code:

def do_trial(f):
    n = int(f.readline())
    if n>cycle_length:
        n %= cycle_length
        n += cycle_length
    t = a_b_n(n-1)
    return (2*t[0]-1) % 1000

f = sys.stdin
count = int(f.readline())
for i in xrange(count):
v = do_trial(f)
print "Case #%d: %03d" % (i+1, v)

It runs in pretty much no time at all, thanks to the excessive caching.

Big Park Dot Com

Our corporate web finally went live this week. I have been at this company for over six months, joining shortly after its inception.

So what took so long? Well, for one thing, we didn’t have a name until very recently. We were going by the temporary name “Funny Fox Games”, but didn’t want to waste any time branding us by the temporary name. We struggled over a final name for quite a while, and just a few weeks ago settled on BigPark, Inc. I actually think the name is quite good (kind of a relief… I thought some of the ideas were not that great).

So check out our quite pretty (and vague) web site at http://bigpark.com/ and see what you think. We have a few jobs openings, so if you like computers and/or games, take a look!

With a little luck, we will release our first game Real Soon Nowâ„¢.

“Rock Band” Makes You Feel Cool

An invariant in my personality is an obsession with precision, pedantry, and pedagogy. This perfect storm is responsible for my unusual interest and aptitude for math and computers. But this was not a conscious choice, and with the good fortune of being able to breeze through math course came the curse of nerd-dom ostricization. My tendencies in this direction are too strong to ever hope to not be a nerd. I’ve always refused to “celebrate” the nerd way. Some of it is overcompensation, some of it surprising. For example, I’ve never seen an episode of Star Trek. As I like to say, I don’t trust anyone too much into anything. I’m a nerd, but I’m not a geek. (OK, I have a blog. Sue me.)

This repudiation of the geek lifestyle has caused me to drift away from video games that interested me when I was younger. My current job has brought me back into that world though, because… well, it’s that industry. So the office has XBOX 360, Wii, a giant TV. We got the game “Rock Band” pretty much as soon as it was available.

“Rock Band” comes with a guitar controller (with buttons instead of frets), a microphone, and a drum kit. You play and sing along with real songs that you’ve probably heard on the radio, like Weezer’s “Say It Ain’t So”, and it scores you based on how accurately you follow along to the score that scrolls by. If a tone is assigned to you and you botch it, that note doesn’t play in the song, and the discordance socks a body blow to your musical memory (and makes the virtual crowd more likely to start booing).

It doesn’t take long before you actually start to get the hang of it, and surprisingly, feel like you are contributing to the songs. You really do learn certain musical skills, especially timing.

If the difficulty level is appropriate — not too easy that you get bored, but not too hard that you get frustrated (see also this Wikipedia article) — you really start to get into it, and become one with the music. You begin to understand what it might be like to be a real rock star. It’s a coolness simulator.

These effects are real. After I’ve played the game for a while, I really do feel more at ease. I feel more confident. I am more chatty with strangers.

Of course, the irony is that playing video games is kind of dorky. One might claim this it’s just a fantasy world, where people pretend to be something they’re not. But there’s no denying that it does have an immersive coolness effect on its participants’ mood. So how to reconcile this apparent contradiction?

Who cares? Cool people don’t care what other people think.

Math Jesus

Today I got multiple copies of a “pump-and-dump” spam. You know, the kind where they tell you about a stock that is “going to go through the roof” which then does because enough people believe it, so it becomes a self-fullfilling prophecy. The best part is, no one even has to be convinced about the fundamentals of the stock — they just have to believe that enough other people are going to buy. Thus, the pump. Alas, the dump is a tough one. Good luck with the timing on that. But I digress.

Somehow, many copies of this spam made it through Gmail’s normally excellent spam filter. Each was from a different, made-up sender, with first and last names probably independently chosen from some list. What was cool was the name on one of the spams: “Math Jesus”.

How wonderful. I immediately claim ownership of this moniker, since the spammer is probably not aware that this pairing was made. And how fitting. I am very good at math — not the best mathematician the world has ever seen, but definitely way up there. Not a math god. But, yes, dare I say, a Math Jesus.

Thus my new screen name/nickname/band name. Math Jesus.

Gödel showed that we need an infinite number of axioms for a system that can embed the natural numbers to be complete (that is, for every statement to be provably true or false). Something along those lines.

So let me say right now: ten commandments ain’t gonna cut it. That’s just gonna be the tip of the infinite iceberg.

Lazy Bones

I’ve always been proud about how lazy I am. I often say that I will do an incredible amount of work just so I can be lazy. Something along those lines happened today, and I realize that what it is is that I hate is routine busywork; so much so that I would rather do a certain quantity of creative work to avoid an equal quantity of busywork.

At my company, we have used Apple’s deprecated WebObjects 4.5, which uses Objective-C and WebScript. Years ago, WO4.5 was the most fun web development environment, but since it turned 5.0 and substituted Java for Objective-C, it’s been much less fun and it’s not used very widely outside Apple, and it’s not really admired as much as it used to be. It’s gotten worse (Java over WebScript? Get real) and other environments have gotten better (I like Django a lot right now).

Anyway, we have a specific application that has been bothering us for a long time, and it’s time to port it.

I’ve been looking at “SQLAlchemy”, a Python-based object-relational modeling tool that works with Oracle (which I hate, but that’s a story for another time). It seems using this tool will make the port from WO4.5 to Python a fair bit easier.

The first step seemed to be to create new model files that describe the object-relational mapping. Of course, the syntax for these files (pure Python, it turns out) is quite different from the syntax used in WO’s EOF object-relational mapping layer. We have a lot of objects, so rather than do it by hand, I thought I would write a tool to do it.

EOF uses a plist file format. There are Objective-C routines to read these files, but I couldn’t find any libraries to do so in Python. So I installed pyobjc so I could use one particular Objective-C call from Python. This made parsing very easy, and creating the Python model file was a piece of cake.

It’s not 100% yet, but I was quite amazed not only how quickly I could produce the translation tool, but what great lengths I would go to to be lazy.

I Went To Hack Day and It Was Pretty Good

I just got back from “Yahoo! Hack Day”, an ultra-nerdy convention of sorts put on at Yahoo! in Sunnyvale. It was sort of reminiscent of the now-defunct MacHack conventions I went to in the early naughties (2000 and 2001 I think) except it was free, more conveniently located here in Silicon Valley instead of Detroit (?!?!? I know there is a perfectly logical story behind why MacHack was in Detroit that I would knowingly nod my head at while I was hearing, but I repeat: ?!?!?), and more focused on web technologies (Yahoo! APIs, specifically).

I went there right after work on Friday, checked in, and put my name on the “looking for teammates” whiteboard. There was free pizza, and then a concert outside by Beck. The concert was fine — there were a lot of hangers-on (hanger-ons?), folks who were there just for the concert — but I was distracted by brainstorming about what I would do for the veritable hack contest that was about to start. By the way, Beck seems to really be into marionettes. I do love a good puppet show.

I met up with a clever young whippersnapper by the name of Sandro who was also interested in using the web development tools that I have been using lately (“Django” — see http://djangoproject.com/) and we went through some ideas and finally settled on what he cleverly called Flick Rel8. It’s sort a license-platey name. It’s a game: we download pointers to a bunch of Flickr images that are labeled with popular tags. Then we show three images with tag A is a row, followed by a stack of four images with tags A, B, C, D in some random order. The user has to guess which of the four images has the same tag as the first three.

The tag is not displayed (although it is available as a hint). So you have to look at the images and figure out what they have in common… and then find a fourth image that has the same thing. It’s like the SAT, Flickr-style.

We spent a lot of time developing and not a lot trying it, so I still don’t know if it ends up being fun. I don’t think it was that fun with the data set we had, but I think you could make it fun, especially if you limited the tag list to a certain class of tags — maybe concrete nouns and adjectives. For example, “2006” is a pretty lame tag for this purpose.

The conference staff showed us clips from that indicated that every local news channel had a story about the conference.. Yahoo! must have some killer publicists. One dorky reporter disclosed the difference between “hackers” who are talented computer folk who mean no harm and “crackers” who try to break into computers. The irony was that he was the biggest cracker of them all.

Then at 3 PM, our hours of manic work came to an end. The 55-some odd teams took turns displaying their hacks. We were number 32. I started off with a joke that I knew would work with that audience, and indeed, it got a big laugh. It’s interested being able to not appear nervous in front of a crowd and to be able to be confident about getting a laugh.

All the stories had this spin that seemed to try to make the conference seem elite, or cool, or possibly even hip. I think Beck being there added to that sheen. I dunno, I think nerds are by definition not very cool. See Paul Graham’s essay on this. But so what? Why can’t things just be what they are?

All in all, a good time. I am exhausted, and I did not even stay up all night, as some people did (many camped out on the lawn). I met some good people. And I got to hack on computers, a thing I’ve been enjoying a lot more of lately.

MySpace Dot Count

Being a computer hacker and software guy, I pay attention. As you may know, I think as far as software goes, MySpace is the web equivalent of Microsoft Windows: ugly, cluttered with awkward functionality, bug-ridden, but everyone uses it because everyone else does. Well, except I don’t use Microsoft Windows. If only Friendster were compatible with MySpace.

An example of the just plain stupidity of MySpace struck me today as I looked at my comments list. At the top of the list was the notation

“Display 37 of 36 Comments”

I didn’t bother to count if I had 36 or 37 comments (or who knows, maybe some other number), but how do you manage to get the “page count” of comments larger than the “total number” of comments? That’s a special kind of carelessness.