750 Words to org-mode converter

The past few days, I’ve been using a site called 750 Words. The concept is simple: each day (preferably in the morning), write at least 750 words (preferably all at once). It’s just a simple writing exercise, but it’s really a nice way to start the day–750 words is enough to force you to think of some things to write; you can’t just write 750 words about your morning coffee, at least not without working at it. Coming up with and writing down some ideas at a burst in the morning helps to get you started making progress on your mental tasks, and helps you get your thoughts organized, too.

Now, writing my 750 words on the site is nice and all, and I appreciate the push to actually do it that the site provides, but I like to have all my writings kept locally, too. I usually use emacs org-mode to keep track of… basically, everything. I’m a big fan of it. So, I wrote a little python script to take the exported files containing a month’s writing that you can get from 750 Words and convert them into a simple structured org-mode file. It creates files that look like this:

* 2011
** 2011-06 June
*** 2011-06-14 Tuesday
  ROPERTIES:
:WORD_COUNT: 771
:MINUTES: 13.3774
:END:
Today I've been looking...
*** 2011-06-15 Wednesday
  ROPERTIES:
...

It currently just appends whatever entries are in the file ’750′ to the file ’750.org’, so you’ll want to process the export files in order. It’ll create the year heading if it’s processing a January dump, or if the file ’750.org’ doesn’t yet exist. Otherwise, it just makes a new month heading and populates it with the entries in the file, with one entry per day.  I have only tested it against my own exports, of course, so I can’t guarantee it’ll work in all cases. In particular, if 750 Words sticks metadata lines at the top of entries like it does with the word count and time, then my script won’t insert those into the properties drawer like it does with the other two. It will probably just ignore them and proceed as though they didn’t exist, though. I’ll have to try using some metadata in an entry and see how (and if) it affects the export file, but for now, caveat emptor.

If this sounds useful to you, you can get it from the bitbucket repository. I’d be happy to hear any comments, suggestions, or bug reports.

LETTER, a simple guessing game

Recently, I’ve been looking through a book called Basic Computer Games: Microcomputer Edition, edited by David H. Ahl. The book contains lots of type-in computer games written in Microsoft BASIC for the Altair. A fair number of these ‘games’ are more like toys, and some aren’t even interactive, but a few look like real fun, and they’re all little pieces of computing history, which I find very interesting.

I thought I’d port a few of the more interesting games to a more modern language so people could check them out and see how far we’ve come (or, in some cases, how far we haven’t come). Of course, I thought I’d start by doing exactly what I didn’t set out to do, and port a very simple and not very interesting game, just to get a feel for it. Even this gave me a little pause, as I’ll get into. First, the game: Letter, by Bob Albrecht. That link leads to a scan of (a different edition of) the book I got the game from, so you can see the original BASIC code I was porting. Programmers among us will recognize that it’s extraordinarily simple, and, for a BASIC program, quite clean and readable. One thing gave me a little trouble:

510 FOR N=1 TO 15: PRINT CHR$(7);: NEXT N

This line didn’t seem to affect the output in the printed sample run of the game, so I got an Altair emulator, just to be sure. Indeed, it doesn’t actually print, though I have no idea why. Whatever the reason, I left it out so as to faithfully reproduce the game as it was on the original system, whatever the code says.

A part of my intention in porting these is to provide sample code for people who may be interested in learning to program; these simple games should prove to be pretty easy to understand for anyone who cares to look. Having just read through quite a lot of BASIC code, I wasn’t in a very pythonic frame of mind when writing this, but I think it’ll be clear enough.

Enough about my troubles, though. You can find the game here. If you have python installed, you can just get the tiny python source file. If not, or if you’re not sure, you can get a ZIP with a Windows executable, instead, which should run on anything from Windows 95 through Vista. If it won’t run, or complains of missing files, you may need this.

I’ll port something more interesting, and hopefully more fun, next time. Until then, I HAVE A LETTER. START GUESSING.

A Fast Algorithm for Computing Fibonacci Numbers

I came across an algorithm for computing Fibonacci numbers in a paper by Takahashi Daisuke; the paper’s in Japanese, but the pseudocode of the algorithm is plain enough that it’s easy to understand, even if I can’t read any of the explanation. I’ve implemented it in python, and it’s decidedly slower than the Fibonacci function in Mathematica, though that’s to be expected. My implementation takes quite a few seconds to compute F(2^20) but is quick for numbers below about F(2^15), with the additional benefits of not computing absurdly huge floats or recursing a million times.

The algorithm is apparently a refinement of another (perhaps well-known?) algorithm, which computes Fibonacci numbers from the product of Lucas numbers. I’ll have to look into it to see just how it works.

Edit: After some investigation, a large part of Mathematica’s apparent advantage is in its faster display, rather than faster computation, though Mathematica does still beat my python program by a rather huge amount–Mathematica computes Fibonacci[2^23] in about 0.2 seconds, while my program takes just over five seconds. This disparity increases as the argument grows larger. Also, found an English version of that paper. Neat.

Things I Learned About Python

Sometimes dictionaries are better than lists.

I had a huge list of numbers, and I was generating new numbers which I needed to check for membership in the list. So, I was doing lots of item in list. However this proved to be very slow. So slow that the program would have run for several days before completing.

So, I stuck all of the list items in a dictionary and did dictionary.has_key(item). The program ran in about a second.

Lesson: Use the right tool for the job.