TextSaver addon tutorial

Although I’ve already entered CopyURL and Affiliator in the Extend Firefox 3 competition, I wanted to see what I could do with 3 days of intense coding. My wife always complains about writing long posts on YouTube, then losing them due to a session timeout. I’m always looking for a problem to fix, and this seemed like a perfect idea for the competition, so starting this past Monday, I created TextSaver.

When you load the addon and restart Firefox, you should see a little disk-and-paper icon in the statusbar. We’ll get to that in a minute. To start, go ahead and type something in a text input, whether it be a standard textbox, a textarea, or whatever magic Google uses in GMail (which do not appear to be standard textboxes according to Firebug). Click “Add this text to TextSaver”, and you should see a sidebar appear, along with a box prompting you for a name. Pick whatever name you’d like to remember this snippet of text by, and click “OK”. The text is now safely stored in the sidebar, ready to be dragged and dropped on any text input, even those outside of Firefox.

You can also drag and drop pretty much anything that has a text representation onto the sidebar, and the process will remain the same. Clicking the globe icon next to the item’s name will open a tab containing the page you were on when you saved the text. Clicking “(edit)” will pop up an edit dialog allowing you to modify the name, URL, or content of the saved text. Finally, clicking the close button in an item will allow you to delete it permanently.

You may have also noticed the search box above the saved text items. As you type in this box, it will rapidly search through the names, URLs, and contents of every piece of text you’ve saved with TextSaver, filtering out those that don’t match. This is a quick way, for example, of finding that post on YouTube out of the hundreds that have timed out. Hopefully you’ll have deleted some after you’re done using them, but if you’ve got the desire to keep them around, feel free to do so.

Clicking on the TextSaver icon in the status bar will pop up a menu giving you the option to show/hide the sidebar, as well as whether or not to show the context menu item for TextSaver. If you prefer dragging/dropping, and don’t want to lose valuable context menu real estate, get rid of it, and it’ll never bother you again.

Thanks for trying TextSaver. I welcome all feedback, critiques, and complaints. If you’ve found it helpful, donations are also gladly accepted, and greatly appreciated.

Switching hosts

Well, Dreamhost has informed me that my hosting costs for the next year are going to triple, so it’s time to find another host. As soon as I figure out who that host will be, I’ll move the blog and update the extensions on Mozilla’s site to point to the new homepage, or possibly even a dynamic redirect from DynDNS so I don’t have to do this again next year.

CopyURL 0.1 addon for Firefox released

An Affiliator user (who had just moved to Firefox 3 from Safari) requested some help with copying links formatted in HTML, which Affiliator does automatically, though only for Amazon, and which Safari apparently does natively. Not finding anything, I decided to rip out that portion of Affiliator, spruce it up a bit, and throw it in the toolbar.

CopyURL was the result.

Load up the addon in Firefox, then either go to View->Toolbars->Customize…, or right-click the toolbar and choose “Customize…”. Drag and drop the CopyURL icon anywhere you like on the toolbar, and you’re set. Click the button on any page or image on the web, and it will do one of two things:

1. If you’re on a webpage, it will create an anchor tag to the current page, using the page’s TITLE element text as the link text. If the TITLE element can’t be found, it will prompt you to enter the link text.
2. If you’re on an image, it will create an image tag.

No more having to remember HTML syntax when you want to post a link, or BBCode or Wiki syntax, either. Clicking the drop-down arrow next to the button will give you a list of formats to choose from, as well as the ability to add your own.

Hopefully this will make things a little easier for everyone.

Also, a new (minor) version of Affiliator is probably coming tomorrow, as the same user who prompted CopyURL informed me that right-click context menus are particularly difficult with one-button mice on OSX. In response to that, Affiliator’s getting a toolbar button as well, though it won’t be as full-featured as the context menu.

Lastly, I’m aware the icon sucks. Despite minoring in Art & Design in college, I can’t make icons for crap.

Affiliator 0.1.3 released

I apologize for the lack of updates recently. My real job has kept me very busy for the past few months. This is just a quick update to allow you to change the format of the generated HTML links, as requested by a user. The user who requested this needed his links in the following format:

[http://www.amazon.com/dp/B00000JRSB/?tag=doggettc-20][Buy Final Fantasy VII] (seriously, buy it from the third-party seller with the same name as me, so I can build a new non-slow computer)

The simplest solution was to allow you to specify your own link formats, so I’ve added a field to the Affiliator options page under Tools->Addons that allows just that. To help you get started, here are some common formats:

• Default HTML: <a href=”#{GENERATED_LINK}” target=”_blank”>#{PRODUCT_TITLE}</a>
• BBCode: [url=#{GENERATED_LINK}]#{PRODUCT_TITLE}[/url]
• User request from above: [#{GENERATED_LINK}][Buy #{PRODUCT_TITLE}]

It should be fairly easy to get your links into whatever format you (or your blog/site) prefer. Just make sure you set your generated links to auto-wrap after setting your format, and the work will be done for you.

I’ve also added a PayPal donation link to the sidebar, at the same user’s suggestion. If you’d like to support the development of Affiliator, all donations are greatly appreciated. They will mostly be used to buy turkey for the cat pictured in the sidebar, to keep him from crying and distracting me from writing code.

Lastly, I haven’t forgotten the users’ requests for multiple international affiliate link generation (with link status checking). That’s coming soon, I just haven’t had time to work on this lately, and I’m horribly sorry for the delay.

I lied, that wasn’t the last thing. Here’s the link for the new version on Mozilla Addons:

Affiliator 0.1.3

If you like Affiliator, please write a review on that page. The more reviews it gets, the sooner it goes public, which means it will automatically notify you of updates.

Thank you all again for your support of this project.

Half-assed Functional Programming in .NET 2.0

Ever since reading Joel’s Can Your Programming Language Do This?, I’ve been obsessed with Functional Programming, and with my shiny new hammer, everything looks like a nail. A few months ago, I got it into my head that it’d be a good idea to implement Map, Filter, and Reduce in .NET 1.1. It was actually simple enough to do, albeit in no way type-safe, and still vulnerable to side effects. Naturally, I named the library QAFP (Quarter-Assed Functional Programming), since it was half-half-assed. As an example, here was my Map function:

public delegate object MapFunction(object obj);

public static IList Map(IList list, MapFunction func)
{
    if (null == list || null == func)
    {
        return null;
    }

    IList mappedList = new ArrayList(list.Count);

    foreach (object o in list)
    {
        mappedList.Add(func(o));
    }

    return mappedList;
}

public object Square(object obj)
{
    int i = (int) obj;

    return i * i;
}

public void MapTest()
{
    IList numbers = new ArrayList(5);

    for(int i = 1; i <= 5; i++)
    {
        numbers.Add(i);
    }

    numbers = Map(numbers, Square);
    // list should now contain [1,4,9,16,25]
}

It was ugly, but it worked. Pass it a list of mixed items and forget to do your type checking, and you’re boned. It wound up being very useful, and cut down on some of our development time, until we finally moved up to .NET 2.0. I know all of this stuff is old news to those of you using .NET 3.5 and LINQ, but given that we’ve just updated to 2.0, 3.5 is a long way off for us, so bear with me. If you’re stuck using .NET 2.0, you may enjoy this.

The upgrade to half-assed functional programming came with generics and anonymous delegates. Since side-effects are still possible, it’s not pure functional programming, but it’s close enough to be very useful, as long as you’re careful with it. The new code doesn’t look all that different, but it’s much safer, and any type errors should be caught by the compiler. Here’s the new Map function:

public delegate TOutput MapFunction<TInput, TOutput>(TInput obj);

public static void Map<TInput, TOutput>(List<TInput> inputList, MapFunction<TInput, TOutput> func, out List<TOutput> outputList)
{
    outputList = new List<TOutput>();

    if (null == inputList || null == func)
    {
        return;
    }

    outputList.Capacity = inputList.Count;

    foreach (TInput obj in inputList)
    {
        outputList.Add(func(obj));
    }
}

public int Square(int i)
{
    return i * i;
}

public void MapTest()
{
    List<int> numbers = new List<int>(5);
    List<int> squaredNumbers;

    for(int i = 1; i <= 5; i++)
    {
        numbers.Add(i);
    }

    Map(numbers, Square, out squaredNumbers);
    // list should now contain [1,4,9,16,25]
}

Filtering a list is also needed quite a bit, and the generic List<T> in .NET 2.0 already has this covered, through the use of Predicates. A Predicate is basically a function that takes an object of type T, and returns true or false if it matches some criteria. Combine that with List<T>’s FindAll function, and it’s easy to return a list of Ts matching that criteria. I still wrapped everything in a filter function, just to ensure no empty lists or missing predicates. As an example, to strip out all odd numbers from a list:

public static List<TInput> Filter<TInput>(List<TInput> inputList, Predicate<TInput> func)
{
    if (null == inputList || null == func)
    {
        return null;
    }

    return inputList.FindAll(func);
}

public List<int> GetEvenNumbers(List<int> numbers)
{
    return Filter(numbers, delegate(int i){ return (i % 2) == 1; });
}

Last, but certainly not least, is Reduce, also known as foldr to those of you who speak with a LISP. For those not in the know, it performs an operation on each item in the list and the total (or aggregate) of every item before it, starting with an initial value for the total. The way this total is implemented is completely up to you, as you can see below:

public delegate TAggregate ReduceFunction<TInput, TAggregate>(TAggregate aggregate, TInput obj);

public static TAggregate Reduce<TInput, TAggregate>(List<TInput> inputList, ReduceFunction<TInput, TAggregate> func, TAggregate initialValue)
{
    TAggregate aggregate = initialValue;

    inputList.ForEach(delegate(TInput input) {
        aggregate = func(aggregate, input);
    });

    return aggregate;
}

public int Sum(int total, int i)
{
    return total + i;
}

public int Product(int total, int i)
{
    return total * i;
}

public StringBuilder Concatenate(StringBuilder sb, string s)
{
    return sb.AppendFormat("{0}", s);
}

public void TestReduce()
{
    List<int> numbers = new List<int>(5);

    for(int i = 1; i <= 5; i++)
    {
        numbers.Add(i);
    }

    int sum = Reduce(numbers, Sum, 0);
    int product = Reduce(numbers, Product, 1);

    List<string> strings = GetListOfStringsToConcatenate();

    StringBuilder sb = new StringBuilder();

    sb = Reduce(strings, Concatenate, sb);
}

Now, where and why would you use this? Functional Programming is usually used for math-intensive applications, but like I said, everything looks like a nail. To improve network performance, when making remote function calls, we don’t send entire objects if we only need their ID number. So, given a list of patients, let’s say we want to find those with fatal allergies, to keep them from falling into our strategically placed peanut, grass, and pet dander bins (let’s also say we’re witch doctors).

public List<int> GetAllergiesForPatientsAboveSeverity(List<int> patientIDs, Severity severity)
{
    List<Patient> patients;
    List<int> allergyIDs;

    Map(patientIDs, GetPatientObjectFromID, out patients);

    List<Allergy> allergies =
        GetAllAllergiesForPatients(patients)
        .Filter(delegate(Allergy allergy) {
            return allergy.Severity >= severity;
        });

    Map(allergies, GetAllergyIDFromObject, out allergyIDs);

    return allergyIDs;
}

public List<Allergy> GetAllAllergiesForPatients(List<Patient> patients)
{
    // Grab the allergies for the given patients…
}

public Patient GetPatientObjectFromID(int patientID)
{
    return PatientCache.Find(delegate(Patient p) { return p.ID == patientID; };
}

public int GetAllergyIDFromObject(Allergy allergy)
{
    return allergy.ID;
}

We’d end up only sending a few ints to the server, and getting a few ints in return. Why is this important? Hell if I know, I just think it’s elegant code, if a contrived example. So, if you’re stuck with .NET 2.0 for the moment, like I am, and you’re into Functional Programming, give this a shot. I’m sure you’ll find all sorts of nails you never noticed before.

Affiliator 0.1.2 released

This is just a maxVersion bump to allow Affiliator to work with the Firefox nightly builds. There are no new features, so if you’re happy with 0.1.1, stick with it.

I won’t bother to host it here since it’s such a small change, so you can grab it at the Mozilla Addons Directory here: Affiliator 0.1.2.

Affiliator 0.1.1 released

Ann Zeise over at the Amazon Associates discussion boards pointed out to me that the link format I was using was outdated, and the preferred format is:

http://www.amazon.com/dp/ASIN/?tag=YourID

I’ve updated the addon to not only reflect the proper link format, but also to add it as a preference, so if Amazon changes the preferred format, you can update the string yourself until I get a fix out. Currently, it defaults to:

http://www.amazon.com/dp/#{ASIN}/?tag=#{AFFILIATE_CODE}

All you have to do is update the URL, and put the #{ASIN} and #{AFFILIATE_CODE} markers in the proper place, and it’ll work like it should.

I also added the ability to click on any product link on Amazon and have it generate the affiliate link. You no longer have to be on the actual product page. From what I’ve found, Amazon provides three link formats on their pages:

• http://www.amazon.com/gp/product/#{ASIN}/blah
• http://www.amazon.com/#{PRODUCT_TITLE}/dp/#{ASIN}/blah
• http://www.amazon.com/dp/#{ASIN}/blah

If the link clicked doesn’t contain the product title, it will attempt to get it from the link text, unless the link is an image, in which case you will be prompted for the product name. If it does contain the product title, it will use that for the product name. All of these cases, of course, depend on you having set Affiliator to automatically wrap your link in an HTML tag. If you’re just generating the link, it skips this whole process.

I’m going to continue to use this blog for Affiliator update notifications, and you can always find the latest news here:

http://www.theantichris.dreamhosters.com/category/firefox-addons/affiliator/

I’ve also submitted Affiliator to the Mozilla Addons Directory, but it won’t be public until a few people have submitted reviews, so if you like it, head over there and submit a review. The benefit to that is, whenever Affiliator is updated, Firefox will notify you automatically.

Until then, you can get Affiliator 0.1.1 here:

Affiliator 0.1.1
Mozilla Addons Directory page for Affiliator

Affiliator addon released for Firefox

I’ve always found it a bit of a pain to generate Amazon affiliate links. Once you’ve found the page you want to link to, you have to go to the affiliate site, log in, pick what type of link you want, enter the address and what you want the link to say. Then, after all that, you get a page with your link and a tracker image. The whole process usually takes me about a minute per link, sometimes less depending on how the network’s behaving.

Like any decent 20-percenter, I’ll gladly spend a day building a tool to save myself minutes. It’ll pay itself off in a few thousand links. Anyway, the current method of generating affiliate links has two problems:

• The generated link is long and cumbersome, filled with GET parameters.
• It’s slow.

The first problem has been solved by a variety of people, but I first saw it on Coding Horror. You can greatly shorten the URLs, from this:

http://www.amazon.com/gp/redirect.html?ie=UTF8&location=http%3A%2F
2Fwww.amazon.com %2FSamsung-SyncMaster-226BW-LCD-Monitor
%2Fdp%2FB000NBBWNU%3Fie%3DUTF8%26s%3Delectronics%26qid%3D1207233586%26sr
%3D8-1&tag=doggettc-20&linkCode=ur2 &camp=1789&creative=9325

to this:

http://www.amazon.com/exec/obidos/ASIN/B000NBBWNU/doggettc-20

All you need is the ASIN (Amazon Standard Item Number) and your affiliate code, which make up the last two segments of the URL.

First problem solved, but you still have to hunt through the page for the ASIN. I hunted around, and found that nobody had made a Firefox addon to build affiliate links, so I took on the task myself. The result is Affiliator, a one-click solution. OK, three clicks.

All you need to do now is find the product you want to link to, right-click the page, and:

The affiliate link is generated and copied to the clipboard. If you’re super lazy, like myself, you can choose to have your links automatically wrapped in an HTML anchor tag with the title of the item on the page. With three quick clicks, the item I showed above becomes this:

Samsung SyncMaster 226BW 22″ LCD Monitor
(A great monitor that has unfortunately gone back up in price since I bought it a year ago.)

Hopefully someone will find it useful. If not, it’ll be worth my time after 1,439 more links.

In case you missed the link above, you can download the addon here:

Affiliator 0.1

Patterns of set bits in a byte

When I was searching for my current job, I got a lot of help from Joel Spolsky’s Guerrilla Guide to Interviewing. I found that a few of my phone interviewers were readers of Joel’s when one (who was not affiliated with Fog Creek Software) asked me:

“How many gas stations are in Los Angeles?”

Right out of the article, and the only one with an answer below it in said article, which I happened to have laid out in front of me at the time. I had to add a few candidate categories to Joel’s list:

• Not-so-smart candidates will get flustered and upset.
• Smart candidates will realize you aren’t quizzing them on their knowledge, but on their problem-solving abilities.
• Smart-ass candidates will say “I’d just go to Joel on Software and look up the answer.”
• Smart smart-ass candidates will read the answer off of JoS and wing it. No sense in letting them know you’ve figured out they’re a lazy interviewer.

I’ve always enjoyed a good challenge, and hadn’t written any C code in awhile, so I decided to tackle a few of his coding questions, like reversing a string in place:

void revstr(TCHAR *str)
{
    if( *str == '' )
    {
        return;
    }

    TCHAR *start = str;
    TCHAR *end = start + strlen(str) - 1;

    while(start < end)
    {
        *start ^= *end;
        *end ^= *start;
        *start ^= *end;
        *start++;
        *end–;
        /*

        could also use *start ^= *end ^= *start++ ^= *end–; if you want to get fancy
        */
    }
}

That led me to try my hand at a function to check if a string was a palindrome:

bool isAlphaNumeric(char c)
{
    return (iswalpha(c) || iswdigit(c));
}

bool isPalindrome(char *str)
{
    /* A man, a plan, Anal Panama!!! */
    if(*str == ”)
    {
        return false;
    }

    int len = strlen(str);
    if(len <= 1) return true;

    char *start = str;
    char *end = start + len - 1;

    while(start < end)
    {
        if(!isAlphaNumeric(*start))
        {
            *start++;
            continue;
        }
        if(!isAlphaNumeric(*end))
        {
            *end–;
            continue;
        }
        if(towlower(*start) != towlower(*end))
        {
            return false;
        }
        *start++;
        *end–;
    }
    return true;
}

Nothing too special for either of those. Feel free to use them if they’re useful to you, just don’t pretend you wrote them if you didn’t. I’m personally stealing them from the 2005 version of myself, but to be fair, he slept with my wife, so we’re even.

The point of all this code dick-waving has been what I thought was the really interesting question on Joel’s test: Count all the bits that are on in a byte.

A simple, but inefficient method is to just use a bitwise AND to see if the lowest bit is set, then shift the number one place to the right, and repeat until it’s zero, incrementing a counter each time you come across a set bit. However, unless you’re storing it in a lookup table of some sort, you’ll have to run that code each time you need it. With a lookup table, you can cache it the first time it’s needed, and do a simple lookup every time after that. If you’re willing to get even fancier and think about the problem, you can save a hell of a lot of space.

As a disclaimer, my method is far from the best. The best I’ve seen comes from a few mathematical geniuses and can be found here. Even though I failed CALC 166 in college (who schedules Calculus at 7:30 in the morning?), I’ve always been fascinated with math and numbers, and the odd patterns that show up in them. For example, both my zip code and cell phone number (including the area code) are prime numbers, and my office phone number is made up entirely of different powers of two.

So, when Joel said “Really, really brilliant candidates will try to devise a way to compute the table using some kind of a shortcut taking advantage of the patterns that occur.,” I took that as a challenge to find the patterns, and I believe I have. To start, here are the number of bits set for each number that can be represented in a byte. I went ahead and displayed them as NxN grids, where N is a power of two representing the maximum number of bits in the given number, so these represent 2-, 4-, and 8-bit numbers, respectively.

0-3 in 2x2 grid

0 	1
1 	2

0-15 in 4×4 grid

0 	1 	1 	2
1 	2 	2 	3
1 	2 	2 	3
2 	3 	3 	4

0-255 in 16×16 grid

0 	1 	1 	2 	1 	2 	2 	3 	1 	2 	2 	3 	2 	3 	3 	4
1 	2 	2 	3 	2 	3 	3 	4 	2 	3 	3 	4 	3 	4 	4 	5
1 	2 	2 	3 	2 	3 	3 	4 	2 	3 	3 	4 	3 	4 	4 	5
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
1 	2 	2 	3 	2 	3 	3 	4 	2 	3 	3 	4 	3 	4 	4 	5
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
3 	4 	4 	5 	4 	5 	5 	6 	4 	5 	5 	6 	5 	6 	6 	7
1 	2 	2 	3 	2 	3 	3 	4 	2 	3 	3 	4 	3 	4 	4 	5
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
3 	4 	4 	5 	4 	5 	5 	6 	4 	5 	5 	6 	5 	6 	6 	7
2 	3 	3 	4 	3 	4 	4 	5 	3 	4 	4 	5 	4 	5 	5 	6
3 	4 	4 	5 	4 	5 	5 	6 	4 	5 	5 	6 	5 	6 	6 	7
3 	4 	4 	5 	4 	5 	5 	6 	4 	5 	5 	6 	5 	6 	6 	7
4 	5 	5 	6 	5 	6 	6 	7 	5 	6 	6 	7 	6 	7 	7 	8

Notice anything in particular about the numbers when they’re laid out like this? The first row and column have exactly the same numbers, and if you pick a row and column, and add the first number of each together, it’s the exact number you’ll find at the point that row and column intersect. I’m also showing them as 2D arrays, but if you lay out the 2×2 grid as a 1D array, compare it to the first row and column of the 4×4 grid, and then do the same with that grid compared to the 16×16 grid. Each grid, if treated as a one-dimensional array, forms the basis of the next one. There are also some other cool patterns I will mention, but won’t go into.

So, now that we know that we can take the row and column and use that to figure out how many bits are set, we can just divide and mod the number we want by the square root of the size of the array to get our coordinates, like so:

# say we’re looking for the number of bits in 243

x = 243 / 16 => 15 (int)
y = 243 % 16 => 3

# or, if you’re using Ruby
x,y = 243.divmod(16) => [15,3]

Since we’re going to use these coordinates as indices into arrays, and the arrays are the same, we can just use the same array for both, the first row of the grid:

# 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

# Let's call the array "a" add the two indices we got earlier together

a[3] + a[15] = 2 + 4 = 6

# Are there six bits set in the number 243?
243 = 11110011 # Indeed there are

So, your lookup table for an N-bit number requires only 2^(N/2) entries (thanks for the correction, nico). Instead of 256 bytes to cache the number of bits in an 8-bit number, you need at most only 16 bytes. Given that I showed how each grid formed the first row of the next grid, and depending on how you decide to trade off between speed and storage, you could get away with only storing the base array of [0,1,1,2] and computing each successive grid from there. I actually did this in the Ruby code I used to generate the grid tables above, which you can see here:

class Fixnum

    @@bits_base = [0,1,1,2]

    def bits
        self.divmod(@@bits_base.length).inject(0){|sum, i| sum += @@bits_base[i]}
    end

    def update_bits_base(new_bits_base)
        @@bits_base = new_bits_base
    end
end

class Array

    def in_groups_of(n)
      list=[]
      i = 0

      while(i < length) do
        list << slice(i, n)
        i += n
      end

      list
    end

    def print_table(size, col_sep_begin = nil, col_sep_end = “\t“, row_sep_begin = nil, row_sep_end = “\n“, prefix = nil, suffix = nil)
        row_arr = self.in_groups_of(size).inject(“”){|row, row_item| col_arr = row_item.inject(“”){|col, col_item| col + “#{col_sep_begin}#{col_item}#{col_sep_end}“}; row + “#{row_sep_begin}#{col_arr}#{row_sep_end}“}
        puts “#{prefix}#{row_arr}#{suffix}“

    end

    def print_html_table(size)
        print_table(size, “<td>“, “</td>“, “<tr>“, “</tr>“, “<table>“, “</table>“)
    end

end

def bits_on_test(size)
    sqrt_size = Math.sqrt(size).to_i

    puts “<p>0-#{size-1} in #{sqrt_size}x#{sqrt_size} grid<hr /></p>“

    bits = (0..(size-1)).map{|i| i.bits}
    bits.print_table(sqrt_size)

    bits
end

[1,2,4].each { |i|
    i.update_bits_base(bits_on_test(2**(2*i)))
}

The important part is the Fixnum::bits method, which just does the divmod outlined above and sums the array values at those indices. @@bits_base is the lookup table, which is re-computed using itself as the first row and column.

Now, for the other cool pattern I noticed, but won’t go into too much detail on. It might help to have a pen and paper.

# Make a 4x4 grid on the paper, and fill in the upper left quadrant with the values of the 2x2 grid.
# For each quadrant, add the value from that same quadrant in the 2x2 grid to the array.

# Upper left quad add 0 to each number from 2x2
0 	1 	* 	*
1 	2 	* 	*
* 	* 	* 	*
* 	* 	* 	*

# Upper right quad add 1 to each number from 2×2
0 	1 	1 	2
1 	2 	2 	3
* 	* 	* 	*
* 	* 	* 	*

# Lower left quad add 1 to each number from 2×2
0 	1 	1 	2
1 	2 	2 	3
1 	2 	* 	*
2 	3 	* 	*

# Lower right quad add 2 to each number from 2×2
0 	1 	1 	2
1 	2 	2 	3
1 	2 	2 	3
2 	3 	3 	4

Does the final grid look familiar? Compare it to the 4×4 grid I computed earlier. Now applying the same principle to this 4×4 grid to make an 8×8, and then a 16×16 grid, and you’ll come up with the 16×16 grid I came up with above. If you’re clever enough, you may come up with some sort of quadtree algorithm to determine what additions you’d have to make to the base [0,1,1,2] array for a given number.

I hope this has made at least some sense to you. If it does, then Wooo! Independent verification from Joel that I’m really, really brilliant. If not, then my secret fear that I’m actually retarded and everyone is just humoring me may be true. Personally, I’d put my money on idiot savant.

Ruby is my timewaster, part 2 (Alienware contest)

Alienware is running a contest to win a trip for 2 to New York. All you have to do is decipher an alien message using clues from this page:

Alienware Declassified

It’s actually a pretty simple substitution cipher, and it took me about 10 minutes to figure it out.

What does this have to do with Ruby? Well, I was able to rewrite a few lines of my word finder from Ruby is my timewaster to search for words where you know the length of the word, a few letters, and their positions, like in a crossword puzzle.

Here’s the revised code:

def get_possible_words(dictionary, required_letters)
    re_required_letters = Regexp.new(required_letters)
    possible_words = []

    File.readlines(dictionary).each { |line|
        possible_words << line if line.strip! =~ re_required_letters
    }
    possible_words

end

def list_possible_words(dictionary, required_letters)
    get_possible_words(dictionary, required_letters).each{ |word| puts word }
end

dictionary = “words“ #  /usr/share/dict/words stripped of proper nouns and punctuation

required_letters = “^.ut..e$“ # default just for an example
required_letters = ARGV[0] unless ARGV.length == 0

list_possible_words(dictionary, required_letters)

For example, I needed a 6-letter word that matched the pattern “^.ut..e$”. Running the code against it brought back the following words:

• butane
• butene
• cuttle
• futile
• future
• guttae
• guttle
• mutase
• mutate
• mutine
• mutule
• nutate
• outage
• outate
• outbye
• outlie
• outsee
• outvie
• puttee
• rutile
• suttee
• suture

Maybe 3 or 4 of those could reasonably be used in a sentence related to aliens that would be readable by someone without an English degree. The more symbols you figure out, the easier it gets, because you can refine your regular expression and figure out which letters it couldn’t be.

The first page of clues (dated July 8, 1947) gives you enough to figure out all but two letters. If you know Alienware’s naming conventions, one of the two letters should be simple to guess. The second page of clues doesn’t give you any letters you couldn’t have guessed from the first, but it eliminates 3 of the possible letters that could be the last symbol. They’re also the least-frequently used letters of the alphabet, so it’s just a guessing game. I took a shot with the one I thought was most likely.

Hint: Look for the numbers first, and think about why Alienware would use them. That’ll get you the most frequently used letters, and it should only get easier from there.

Second hint: Hey Alienware, I have a fondness for review hardware.