Blackmoor Vituperative

I stumbled across Movies in Fifteen Minutes earlier today. It is really quite funny.

I took some time and wrote up a recommendation for people who still use Microsoft Office. It’s easy to criticize people still using Microsoft Office, but perhaps they really don’t know why they should migrate to OpenOffice.org. I hope that this detailed recommendation helps them make the best decision.

It is imperative that businesses eliminate all unlicensed software. Migrating from Microsoft Office to OpenOffice.org offers a cost-effective alternative to purchasing additional licenses of Microsoft Office. In addition, migration to OpenOffice.org offers significant benefits, such as cross-platform compatibility, increased security, and more reliable access to archived documents. Migrating to OpenOffice.org also provides a more user-friendly upgrade path than migrating to Microsoft Office 2007, because OpenOffice.org uses a standard, familiar user interface.

(from Recommendation to migrate from Microsoft Office to OpenOffice.org [PDF])

Penguin Pete is far more optimistic than I am. The history of media (words, music, images, etc.) in the USA and elsewhere is one of increasing layers of restrictions on consumers, and ever-expanding protections for the media robber barons and the Digital Rights Mafia (DRM).

It will get worse before it gets better. Or, as my grandmother once said, “You can’t get blood out of a turnip, but you can sure ruin the turnip trying.”

A group of students took over a food court at NYU, for reasons which I don’t fully understand. I suspect the people who took over the food court do not understand what they were doing either. Eventually, the administration got tired of waiting for the “revolutionaries” to give up, and kicked them out of the food court.

This is what happens when you buy your kids Macs and pay for them to get liberal arts degrees.

Ray Breckerman brings us another horror story from the war being waged on us by the Digital Rights Mafia (DRM): the story of Brittany Kruger, a Michigan college student who has been targeted by the RIAA extortion machine. Brittany’s story is better than most: as a result of her fight, the lies and crimes of RIAA and their MediaSentry stooges are being dragged into the light, hopefully to burn to ash like the blood-sucking monsters they are.

Brittany has written an open letter describing her experiences, and P2Pnet has granted permission to reprint it:

My name is Brittany Kruger. I’m not a criminal. I’m not a tough person. I cry almost every night these days, and I’m scared to death of what is going to happen to me in the future. Most of all I’m not a pirate, I don’t have a peg leg or a hook for a hand, and I don’t raid ships on the high seas looking for booty.I was a regular kid (I may be 22 years old now, but I still rely on my parents for almost everything!). I’ve no real knowledge of the world at this point in life other than how hard it is to establish credit or get a loan.

Today, February 3rd, I had a lovely conversation with one Morgan Schwartzlander [the ‘lead’ at the RIAA settlement extortion centre], and let me just tell you, it was outstanding, so great in fact I got off the phone in tears. My suggested settlement of $2,000 was “ridiculous” compared to their (“not negotiable”) $8,100 settlement.

Morgan will tell you that she is “not legal counsel” but she’ll tell you what she would do if she were in your situation, she’ll give you some statistics about how motions to quash are almost never granted, and then she’ll tell you that whoever suggested your motion to quash is an idiot (I don’t think she knew that was my dad).

I make about $4,500 in a YEAR working at Dairy Queen, and they want a lump sum of $8,000+? I don’t know how that’s going to work. When I buy a song from iTunes, it only cost $.99. Not every college student can have mommy and daddy pay for all their problems to go away.

I was looking through my journal to refresh my bad memory of how everything happened, then I decided that I didn’t want to bore you with dates. So I’m going to tell what I’ve learned about myself these past 2 years.

Today I realized that I cry a lot! Over and over I question myself “am I a bad person?” I’ve never killed anyone, I’m a very sympathetic and forgiving person, I volunteer, and I go to church.

But these people at the RIAA still have a way of making me question myself. Are some people just programmed to be bad no matter how hard they try to be good? That’s exactly how it seems to go for me, one step forward two steps back (or that seems to be how it is for my one person pity party).

Then my mom assures me that it’s not me. The jobs (I call them jobs because I would assume that a career is something that makes you feel good about what you do) these people hold are there to make people feel bad because they don’t have the monetary funds to make all their problems just go away. They are bullies!

I wonder how people like Ms Schwartzlander or Mr Kelso sleep at night, I wonder if they go to church every Sunday and think “I’m a good person”.

[Note: Kelso is Donald J, a Holmes Roberts & Owen attack lawyer acting for the Big 4’s RIAA as it extorts American students such as Brittany.]

I think all the time about how something that I love so much could get me into so much trouble?

I never sold copyrighted music for profit; I used it [P2P] to find new music or to figure out if I liked a band enough to buy their CD (because I hate buying a CD for just one song)! I didn’t think I was hurting the bands that I love by finding more of their music, listening to it, and then buying their CD. That makes no sense.

I didn’t even know what copyright was until got called to the Dean’s Office.

I don’t know how everyone else spends their college life, but for me a large portion consists of printing off endless amounts of documents that use language I don’t understand, making pleasant phone calls to settlement agencies, and racing papers to the local court house.

That’s precious time I could be using (studying or hanging out with friends) that’s wasted because of money.

I wonder how many college students have had to go to the police station to file a complaint about a “private investigator” invading my privacy, and have had the police look at them as if they were totally incompetent?

How many students have had their university hand them over like a piece of meat to hungry billion dollar corporate wolves?

I know that the University of Michigan didn’t do that, and Harvard University didn’t do that.

I feel bad for my roommates and friends too, because I know they get pulled into a lot of the problems that I have. They get caught answering the phone when it’s a settlement agency and have no idea what to do or say.

How are they supposed to comfort me when I’m having a bad day? I know that hundreds of kids at NMU, at one point or another, downloaded music, but they didn’t get their computers hacked into, and get accused like me of being a pirate like me, and they’re lucky for that. I think they know that.

I’m not a regular college student. I’m an example for everyone to stop and look at, with a giant stamp on my forehead that says, “Don’t be like me, because I made one mistake as a teenager that will ruin the rest of my life”.

You might not see my face or name plastered everywhere, but I can guarantee you that I’m in every statistic, you see a poster on the wall warning you against “illegal downloading”.

I’m the person they’re talking about. I might even be one of the “stupid” ones fighting the RIAA.

I’m Doe # 5, but I prefer to be called Brittany, because that’s who I am.

I’m a person, not an IP address or a case number.

I’m a person and no one will ever change that about me. I’m me and no one else will ever tell me different. I need to believe in that. Everyone makes mistakes, and the people who are doing this to me are no different.

I’m scared, and now I worry all the time about what is going to happen to me.

I don’t know if it has made me a stronger person or a weaker person. I have problems sleeping, my hair is falling out in ungodly amounts, I’m having a hard time concentrating in class, but most of all I hate the fact that I’ve pulled my entire family into this.

My dad helps me all the time figuring out what I should do, my mom listens to me when I’m having a bad day and need someone to cry to, my brothers and sister, I’m sure get jipped on the time my parents spend with them, and there’s always that perpetual question “hey isn’t your sister being sued or something for downloading music?”.

Right now it doesn’t seem like this is ever going to end, I’m just now entering the tunnel and the light is miles away.

I know it will end. I just don’t know how long it will take to get there.

I guess Murder by Death was right when they said “Sometimes the line walks you”.

I was recently shown an interesting programming puzzle. After reading it, I recognized it as a variation on the classic “doublet” game (I read a lot of Lewis Carroll as a kid, as well as being a huge fan of Alice in her various guises).

The Rules

1. Call two words “adjacent” if you can change one word into the other by adding, deleting, or changing a single letter.
2. Using the computer language of your choice, write a program which takes two words as inputs and creates an ordered list of unique words where each word in the sequence is adjacent to the previous and next words in the sequence.
3. If you know Perl, a Perl solution is preferred.

The puzzle suggests using Perl to solve the puzzle, but I do not care for Perl (despite having worked with it longer than any other language I know — or perhaps because of that). I have been learning more about Python (and liking it more the more I use it, unlike Perl), so I decided to give a Python based solution a go.

I started with a basic plan for the script:

• Input the two starting words
• Load the dictionary
• Filter the dictionary to words of the appropriate length
• Find every variation of every word in the filtered dictionary.
• Find variations of the starting word
• If none of them are the ending word, find variations of those variations
• Repeat until the ending word is found

(This was not the best way to start. More on that later.)

A couple of things immediately occurred to me. First, that removing letters would be easier than adding them, if the two end words are of different length. Second, I decided that I wanted to be able to pass arguments and options to the script on the command line: the two words, obviously, but I also wanted to be able to specify a dictionary file of valid words, as well as being able to pass an option that would show me every word tried while the script was running.

I am relatively new to Python, so I did not know how to handle command-line parameters gracefully. My first thought was to test each argument for a leading dash “-” character, and then split them up into arrays. Fortunately, I stumbled across a site with a sample script demonstrating the Python “getopt” module, which does just what I needed. While reading up on that, I then discovered another Python goodie called “doc strings“. I was really rolling now!

My next task was to load the dictionary, and filter out words of an inappropriate length. My initial idea was to build a cross-reference table where the first column would be all of the words of an appropriate length, and the other columns would be every possible single-step variation on those words. For example, for “dog” there would be “cog”, “log”, “dogs”, and so on.

But then I hit a hurdle. When reading in the dictionary file, I only wanted words which are no longer than the longer of the two starting words, and no shorter than the shorter of the two starting words. So naturally, after reading each line, I would test for that, but it seemed that Python was not automatically stripping off the newline characters. But then, why would it, since it does not know which style of newline I happen to be using (I am working on this project on a Windows laptop, but I usually use Unix line endings because I do most of my real work on Linux machines). How does Python treat newline characters when doing readline? And how do I strip them off?

There are two steps to that answer. First, open the file with the U option, for “universal newline support” (e.g., dictionary_file = open(dictionary,"rU")). Second, use strip() to remove whitespace (e.g., line = line.strip()).

Now for my next problem: as far as I know, Python’s arrays (aka, “lists”) are only able to use integers as indexes. For my initial dictionary idea to work, I needed some way of using strings as indexes (aka, “associative arrays”), the way PHP can. As it turns out, the Python feature that offers this functionality is actually called a dictionary. Go figure. Python’s dictionaries aren’t treated like normal (normal for PHP, that is) associative arrays: it does not have the same syntax or methods, and personally, this is an area where I think PHP is superior to Python. Of course, after learning all of this, I went back and thought of a simpler way of building the dictionary that did not use “dictionaries” (aka associative arrays), and simply used lists (aka arrays).

(Why do people insist on renaming everything? Why not call something the name by which it is nigh-universally known? “Arrays” and “associative arrays”. Is that so difficult?)

Before too long, I ran into another problem: how backslashes are treated in strings. I wanted to insert “\b” (for a word boundary) into a string, but Python interprets this to mean something special. So I needed to add an “r” before the opening quotation mark to indicate that this is a “raw string”. This is the first time I have encountered something in Python which reminds me of Perl (which is littered with bizarre, nonintuitive things like this).

These hurdles overcome, I tested my script using a small set of sample data (a dictionary of about twenty words), and it worked great. The problem came with larger dictionaries. When using a dictionary with thousands of words, creating the initial cross-reference index took forever. I also soon learned that my first idea, which was to try every possible variation of a word before giving up and going to the next word resulted in ridiculously long word paths. It soon dawned on me that it would probably be faster to search one letter-layer at a time (what people in computer science classes call a “breadth-first search“) than going down the full path of a particular word path (aka, a “depth-first search“). Amusingly enough, the code to do so was actually simpler than my initial “build a massive cross-reference table” approach.

(By the way, while refreshing my memory on breadth-first searches, I also ran across an algorithm for finding shortest paths called Dijkstra’s algorithm. That looks really interesting, and I want to play with that some day, but I figured I would have enough on my plate just implementing the search in Python, so Dijkstra’s algorithm will have to wait for another day.)

The final hitch I ran into was getting the recursive function to return its value. I must have banged my head against that for three hours before realizing I had made a stupid mistake. I was only returning the value when the function was successful, not when it was calling itself recursively. Since it’s recursive, it needed a return statement for every step of the recursion. A silly mistake on my part, but hey, it happens.

So here is a link to the script, for anyone who might find it educational (rename it to doublet.py in order to run it), and the official Scrabble word list (you will need to unzip it, of course).

For instructions on how to use the script, run doublet.pl -h.

Here is some typical output:

doublet.py -d scrabble_dictionary.txt beginning end
Fail: could not find a path between words
2 potential paths were examined, taking 1.5630 seconds

doublet.py -d scrabble_dictionary.txt begin end
707 potential paths were examined, taking 5.8280 seconds
begin >> began >> bean >> bead >> bend >> end


And here are my answers to the “bonus questions” asked by the original puzzle:

• What is the shortest path between “crawl” and “run”?
  In theory, the shortest path would be five (including the two words at the ends). As it happens, that is also the shortest path when using the dictionary I used.
• What is the shortest path between “mouse” and “elephant”?
  In theory, the shortest path would be eight (including the two words at the ends). However, I could not find a path using the dictionary I used, possibly due to one of the assumptions I used (see below).
• Does your program necessarily return the shortest path?
  Yes.
• What assumptions did you make in your program?
  Other than the parameters provided by the puzzle, I set a limitation that the words which would be examined when trying to make a path would be no shorter than one character less than the shorter of the two words, and no longer than one character more than the longer of the two words. I realize that this will, in some cases, result in not finding a path where one may actually exist.
• How did you test your program?
  Using the words given in the puzzle, as well as a few words that I did not think had a path between them. I also tested the various failure conditions.
• What is the Big-O complexity of your program?
  I think it’s O(n^2), but it’s been a number of years since I studied big-O notation, so I could be wrong.
• Suppose each letter had a point value (for example, as in Scrabble). Discuss (but don’t code) how your algorithm would change if you wanted to find the the path with the lowest possible point total.
  I would have had to continue the script after it finds a path, rather than immediately ending. Then I would have had to contemplate its point value. Finally, when all of the paths are found, or some arbitrary limit is reached, the script would return the found path with the lowest point value.
• Sometimes the shortest path isn’t unique. Discuss (but don’t code) how your algorithm would change if you needed to return all of the shortest paths between two words.
  I would have had to continue the script after it finds a path, rather than immediately ending. Finally, when all of the paths of that length are found, the script would return the found paths.
• Discuss (don’t code) how you might change your program if your concern was minimizing memory usage.
  I would probably replace the search path array with files for each path.
• Discuss (don’t code) how you might change your program if your concern was minimizing CPU time.
  I could be wrong, but I think it already minimizes CPU time. Slicing up the dictionary file by word length would probably help, though.
• Discuss (don’t code) how you might change your program if your concern was minimizing programmer time.
  If conserving my time was important, I would not have added the various optional parameters or tested for so many error conditions.
• Discuss (but don’t code) how your algorithm would change if you wanted to find the longest path between two words.
  I would have had to continue the script after it finds a path, rather than immediately ending. Then, when all of the paths are found, or some arbitrary limit is reached, the script would return the last path found.

Final thoughts:

Just thinking about this took about three days. I wasn’t even sure how to approach the problem at first. Once I had a plan, though, things progressed pretty quickly. I would say that writing the actual code took about four days (an hour here, an hour there). Much of this time was simply spent learning how Python does things, but a good chunk was spent redesigning the script after I realized the problems with my first design.

The script works, and I do not think I will refine it any further. However, I am not entirely satisfied with it, and I can see several things I would like to do differently next time. I did not even attempt to make this object oriented, and that is something that I want to tackle in Python soon. Also, I am not entirely pleased with how I handled the global variables in this script: there are far too many of them for my taste. I am also slightly disillusioned about Python itself. While I think it is a significant improvement over Perl, it still has some peculiar deficiencies. However, I do consider it a significant improvement over Perl, and considering how much time I spent writing and modifying scripts, I think learning Python will be time well spent.

Ray Beckerman is calling for new legislation to protect investors in tech companies from frivolous RIAA lawsuits. Why should investors get special treatment? The problem is not that investors are being sued. The problem is that anyone is being sued.

What we need is not additional legislation to protect investors. What we need is the arrest and conviction of RIAA’s board of directors under federal Rico statues.

I just stumbled across this earlier today: Treehouse Games. They look really fun!

“If this crisis proves nothing else, it proves you cannot help people by lending them more money than they can pay back. […] it should give us pause in responding to the financial crisis of today to realize that this crisis itself was in part an unintended consequence of the monetary policy we employed to deal with the previous recession.”

read more…

This is the funniest thing I have read this week.