« Archives in April, 2008

Programming Pearls: A solution to Exercise 2-2

Using binary search to find a duplicate number in an overstuffed file.

The book’s description:

Given a sequential file containing 4,300,000,000 32-bit integers, how can you find one that appears at least twice?

There are obvious parallels here to exercise 2A. Instead of doing the whole thing over in OCaml again, I went to the complete opposite end of the abstraction scale and did this one in plain C. The description of how it works is in the documentation of the source file.

Check out the code if you’d like: find_duplicate_number.c.

Programming Pearls: A solution to Exercise 2-1

More anagramming, this time in Python. I’m not quite sure why Bentley put this exercise in the book, because it’s really similar to intro problem C in the same column. Maybe he didn’t expect people to work through a full solution to the intro exercises.

There’s a bit of a difference, though. In this exercise, you’re given a specific word to find anagrams for, instead of just having to organize the entire dictionary into anagram groups. This is done in two different ways: In the first part, you’re not allowed to preprocess the dictionary. In the second, you are.

I wrote this one in Python: anagrams_of_word.py.

Super-cool stuff happening in OCaml-land!

Some things I tripped over in the past couple of months that I was surprised and stoked about:

  • Jason Hickey has been improving his OCaml textbook, and it’s going to be published soon. I’ve been through most of the present draft, and the book has really gotten a lot better. It’s a great reference and learning aid. The draft is currently available on his homepage..
  • Jane’s Street Capital is sponsoring some hella cool OCaml projects, two of which I’ve wanted to see forever. The first is a Dr-Schemish environment and learning progression for OCaml, which I think would be a fantastic way to introduce people to the language, to functional programming, and to computer science in general. And of course, the concurrent GC would potentially be stellar as well, although I have to admit I seriously doubt that this one will ever fly. If they pull it off, I will certainly send the team some small token of my astonished respect for them.

An interesting thing to note is that several of these projects, if successful, would probably result in a fork of OCaml, given that new stuff from outside groups tends not to be included in the official distro. My opinion only, of course, and I’m hardly an expert on OCaml politics.

If even one of those Jane’s Capital projects works out, I will be extremely happy. This is my official wish of good luck to all of the teams involved.

Rock.

Programming Pearls: Solutions to Exercises 2A-C

Column 2 presents three problems that you’re supposed to think about before reading through the rest of the chapter. I’ve implemented solutions to those problems here.

It has been a while since I played with OCaml, so I decided to go back to it for these three exercises. I’m experimenting with using a restricted subset of OCaml language features (in the same vein of the approach used with DrScheme in many CS1 courses), so you won’t see anything super-fancy in these solutions.

Exercise 1: Find a missing integer from a (potentially huge) file, with tight memory constraints.

Exercise 2: Rotating arrays in style.

Exercise 3: Grouping a dictionary of words into collections of anagrams.

Thoughts on The Crying of Lot 49 by Thomas Pynchon

Back in January I started doing research for a novel I am writing that was initially inspired by the Jimi Hendrix song “House Burning Down”. After digging a little, I discovered that this song was likely a commentary on the Watts Street Riots. While investigating the riots further, I found an essay written by Thomas Pynchon on the whole affair that was absolutely incredible. So, I decided that I would have to read some Pynchon.

Little did I know what I was in for.

I started with “The Crying of Lot 49″ because it is apparently the most “accessible” of his novels. I think that I am going to need a greater breadth of literary experience before I try to tackle one of his less accessible works, because this one was beyond me.

The basic plot involves a woman named Oedipa Maas investigating the possible existence of a strange secret postal service called “Trystero”. However, she is constantly unsure of whether the conspiracy she is unearthing was completely fabricated by her ex-boyfriend (now deceased), or whether she has actually stumbled across something genuinely disturbing.

However, I felt like the actual thrust of the book was to demonstrate how Oedipa was struggling to find a life of her own, outside the influence of the men that she had been romantically involved with. This is alluded to in one of my favorite scenes in the book, when she is remembering a painting she once saw called “Bordando el Manto Terrestre”:

She had looked down at her feet and known, then, because of a painting, that what she stood on had only been woven together a couple thousand miles away in her own tower, was only by accident known as Mexico, and so Pierce had taken her away from nothing, there’d been no escape.

The Wikipedia article on the novel postulates:

Oedipa’s reaction to the tapestry gives us some insight into her difficulty in determining what is real and what is a fiction created by Inverarity for her benefit.

However, I believe that this scene has a greater significance than that. In my opinion, Oedipa feels that her entire life is being played out in some small, confined window that she has somehow placed herself in, and she is unsure of how to escape it. I think that this is what drives her to expose the Trystero “conspiracy”. Before Trystero, she had this vague notion that there were things out there that she was totally unaware of. Trystero is a concrete instance of something that she has been oblivious to for her entire life, and maybe she feels that, by understanding it, she can somehow bridge the gap between her narrow plane of existence and the “rest of the world” that she thinks might be out there.

Basically, I think Oedipa is unsure of whether she really is “missing out” on life.

The quest itself plays out in some of the most bizarre scenes you can imagine. Almost every linking event between scenes borders on the completely unbelievable. As an example: At the beginning of the novel, Oedipa travels to the town where her ex-boyfriend died in order to learn more about his estate. She decides to stop early on the first night in a trashy motel. Shortly after she arrives, the co-executor shows up and knocks on her door, saying that he’d been looking for her in motels all day. Why on earth was he looking for her if she never announced that she was coming? And even if she did, what are the odds that he would actually find her? At no point does he sound like he had any doubt that he would.

The novel is absolutely rife with moments like this, where some random character is mentioned and then, improbably, appears out of nowhere to join the literary fray. It certainly forced me to pay careful attention to what was going on.

The Crying of Lot 49 was only 150 pages long, but Pynchon managed to cram enough weirdness into those pages that it would have been almost impossible for me to keep track of what was happening if I had put the book down more than twice. After trying to read it at a normal pace (20-30 pages a day) and getting nowhere with it, I finally gave up and read the whole thing from cover to cover in one night. It was certainly worth the effort.

However, now I am wondering what do with this other Pynchon novel, “Mason and Dixon”, that is currently serving as a bookend on one of my shelves. It is a giant hardcover tome of well over eight hundred pages, and if the prose is even half as dense or erratic as what I found in “The Crying of Lot 49″, it is going to be a major undertaking to attack it.

Hrrm.