Here's my CoffeeScript solution. It's a depth-first search of board states (placing a queen in the next available position in the next unoccupied row for each new state), and it returns an array of "solutions". Each solution is an array of indices representing the column in each row where a queen is to be placed (so [1, 3] represents queens at (row 0, column 1) and (row 1, column 3)):

getPlacements = (n) ->
    fill = (b, r, c) ->
        valid = (row, col) -> 0 <= row < n and 0 <= col < n
        newBoard = (row[..] for row in b)
        newBoard[r] = (no for _ in [0..n-1])
        row[c] = no for row in newBoard
        for i in [0..n-1]
            newBoard[r+i][c+i] = no if valid r+i, c+i
            newBoard[r-i][c+i] = no if valid r-i, c+i
            newBoard[r+i][c-i] = no if valid r+i, c-i
            newBoard[r-i][c-i] = no if valid r-i, c-i
        newBoard

    openPositions = (b, r) ->
        ((if b[r]?[c] then c else -1) for c in [0..n-1]).filter (c) -> c >= 0

    result = []
    queue = [[[], ((yes for _ in [0..n-1]) for _ in [0..n-1])]]

    while queue.length
        [placement, board] = queue.pop()
        result.push placement if placement.length is n
        for c in openPositions(board, placement.length).reverse()
            newPlacement = placement[..]
            newPlacement.push c
            queue.push [newPlacement, fill(board, placement.length, c)]
    result

Just like last time, I spent a few hours refining my answer, so it's probably a lot more polished and succinct than one I'd come up with in an interview environment. The basic strategy is the same either way, though: explore all of the possible "next moves" until you hit a point where there are no safe places for the next queen or you've placed all N queens.

I also wrote a handy little printing function for calculating the solutions to an NxN board with N queens and printing them to a console in a readable format:

printPlacements = (n) ->
    placements = getPlacements n
    console.log ((((if p?[r] == c then 'X' else '-') \
        for c in [0..n-1]).join '' \
            for r in [0..n-1]).join '\n' \
                for p in placements).join '\n\n'
    console.log "\nFound #{placements.length} solutions"

The (snipped) output looks something like this:

...

-------X
--X-----
X-------
-----X--
-X------
----X---
------X-
---X----

-------X
---X----
X-------
--X-----
-----X--
-X------
------X-
----X---

Found 92 solutions

And finally, a visualization of what the search actually looks like (slowed down about 10,000 times):

I do have to say that as someone who sometimes conducts technical interviews, I'm not sure I would actually give this question to an interviewee, unless I was leaving him or her alone to work for a couple of hours, because of how long it would probably take to reach an answer.

Doing the problem on a whiteboard would definitely help, because it would remove all of the tedious debugging, but even then the only candidates who would finish in a reasonable amount of time would be the ones who were already familiar with searching algorithms. That said, it's definitely a fun puzzle to solve, it would make a great homework problem in an algorithms class, and I had a lot of fun solving it myself.

Cheers!

In the meantime, I've become interested in learning more about CoffeeScript (a language that transcompiles to JavaScript), but have never found the time to sit down and really learn about it. So, in an effort to kill two birds with one stone, I'm using CoffeeScript to solve last Friday's interview question:

This week's question is to print a binary tree of integers in level order. Level-order printing means printing each row of the tree from left to right, from root row to the deepest row. After each row, print a newline. For example:

I honestly picked this question because it's one I already know the answer to (and probably so does everyone else who's taken an intro-level data structures class), so I knew I wouldn't spend a bunch of time just figuring out the algorithm.

Anyway, here's my eight-line solution in CoffeeScript:

levelOrder = (rootNode) ->
    queue = [[rootNode, 0]]
    (while queue.length
        [node, level] = queue.pop()
        queue.unshift [node.left, level + 1] if node.left?
        queue.unshift [node.right, level + 1] if node.right?
        node.val + if queue[0]?[1] > level then '\n' else ''
    ).join(' ').replace(/\n\ /g, '\n')

Some of the language features used here include while loops as expressions, conditionals as expressions, destructuring assignment, and the existential operator.

For anyone who's interested, here's the 20 or so lines of JavaScript my code transcompiles to (slightly reformatted):

var levelOrder = function(rootNode) {
    var level, node, queue;
    queue = [[rootNode, 0]];
    return ((function() {
        var _ref, _ref1, _results;
        _results = [];
        while (queue.length) {
            _ref = queue.pop(), node = _ref[0], level = _ref[1];
            if (node.left != null) {
                queue.unshift([node.left, level + 1]);
            }
            if (node.right != null) {
                queue.unshift([node.right, level + 1]);
            }
            _results.push(node.val + (((_ref1 = queue[0]) != null ?
                _ref1[1] : void 0) > level ? '\n' : ''));
        }
        return _results;
    })()).join(' ').replace(/\n\ /g, '\n');
};

I was surprised to see how readable the output code was, which further enforces the idea that CoffeeScript really is just "better" JavaScript (or as the website puts it, "an attempt to expose the good parts of JavaScript in a simple way").

I had a lot of fun using a new language to solve an interview question, and I think I learned a lot about CoffeeScript in the process. I'm not sure if I'll make a habit of this or not; I guess we'll see when the next interview question email comes out.

Cheers!

I actually came to this conclusion a few weeks ago, but the current look-and-feel of my blog bothered me so much that I felt like I had to change it before I started writing again. I started by attempting to create a new, super-simplified theme for Octopress (the static blog framework I had been using for a couple of years), but the more I customized, the more I felt like I was just making a theme to turn an Octopress blog into a non-Octopress blog.

I eventually decided to start a blog "from scratch," using just Jekyll (the static site generator that Octopress is built on). I'm really glad I made that decision, because the last couple of weeks have been an awesome experience of building my blog from the ground up and having control over every last detail of it without having to make weird hacks in other people's code. Because I stuck with more or less the same site engine, and because my posts are still written in Markdown, it was pretty easy to migrate my old posts over, too.

A few more things I changed, for those who are interested:

• I stopped hosting my site on GitHub Pages. Instead, I'm now using pure Amazon S3, which lets me control things like gzip compression, redirects, etc.
• Since I'm hosting an S3 site from my root domain, I've also started using Amazon Route 53 for my DNS, instead of NameCheap's built-in DNS. This was more a technical requirement of moving to S3, but I thought I'd mention it anyway.
• I now host all of my images from img.jetheis.com, which is a Amazon CloudFront site, backed by an S3 bucket.
• Because I stopped using GitHub pages, I don't need a private GitHub repo anymore, so I switched to BitBucket. I know it's always been a second-class citizen to GitHub, but we use a lot of Atlassian products at my work and love all of them. I've been similarly impressed by BitBucket, and have even started using SourceTree for managing my commits and pushes.
• I'm looking at moving away from Google Apps for my email hosting, since they're phasing out free accounts. Right now the front-runner is Zoho Mail Lite, which looks like it has all the features I use from Google Apps. If I do end up switching, I'll post about it.

As always, thanks for reading.

Cheers!

I started the power-saving measures around January 10, 2013. Since then, I have received my power bills for 12/23 - 1/21 (29 days) and 1/21 - 2/21 (31 days). The first covers 1095 degree days, and the second 1092. This is a surprisingly close comparison (better than I thought I'd get) between two months, even though one month contained the end of a holiday season and the other one is a little longer.

Anyway, here are the results:

• 12/23 - 1/21 (29 days, 1095 degree days): $188.77
• 1/21 - 2/21 (31 days, 1092 degree days): $178.17

So at the very surface level, it seems safe to say that the steps I took did in fact save me money. I honestly expected that, because it would be very hard to believe that:

• a cold apartment loses more heat energy than a warm apartment, or
• light bulbs that require 22% as much power as their predecessors would somehow use more power.

With that said, the one thing that's really hard to actually quantify is how much power this is saving.

We can look at the number above and say I saved about $10.00 from January to February, and since I implemented the saving measures two-thirds of the way through the January billing cycle, that number should be more like $15.00, but that involves too many assumptions to really say with any confidence.

The problem is that I don't spend a consistent amount of time in my apartment each month, and neither does Emilie. If there's someone in the apartment during the day, that's 8 or more additional hours the heat is turned on, and probably some lights along with it. So the number of vacation days, weekends in Bloomington, visits from Emilie, and pretty much any other disruptions to a "normal" schedule significantly change the amount of power I use day to day. The same is true for water, where I've also seen a $10-$15 savings month-to-month, with a similarly wide variance in usage.

Even with my pretty unscientific findings, I'd like to add some closure to this whole thing, so here goes:

The Nest thermostat is a pretty cool gadget, and I'd recommend it for anyone who thinks it's neat and wants to try it out. If you just want to save money, there are plenty of cheaper options that give you comparable control over your schedule.

Replacing your light bulbs is kind of a no-brainer in my opinion. After just a day or two with the new CFL bulbs, I honestly couldn't tell the difference (the color seemed a little redder initially). The only caveat with the standard issue CFL bulbs is that they tend not to support dimmers, so if you're a fan of dimmers, you'll have a slightly harder choice to make between the more expensive CFL bulbs and standard incandescents (or an even bigger investment in LED bulbs).

Taking shorter showers is another no-brainer. It gives you more time in the morning, saves hot water for others, and saves money. It's not even really worth talking much about.

Anyway, that concludes the update I feel I owed to anyone who read the initial post. If the Nest performs surprisingly well or poorly during the summer months, I may update again with that information, but I imagine the results will be more of the same: a more managed heating and cooling schedule is a little better at keeping costs down.

Cheers!

GitHub has now become the preferred way to manage source code for programming projects. There's good reason for this: it's a really wonderful site with a great following. However, there are times when it's really not desirable to have a project completely public. GitHub provides some paid options for this, as well as educational accounts (which you should really check out if you're a student or instructor). If you've used up your free repositories or simply don't think the project at hand warrants spending money on, you need another option.

That's where Dropbox comes in. Dropbox is a really great backup/sync/file sharing service that pretty seamlessly syncs files between computers. Some time ago, Dropbox added the ability to restore old versions of files. For really simple projects, this may very well be all the version control you need. If that's the case, by all means stop reading this post and start, uh, "drop-box-ing".

For programming projects, this level of version tracking more often than not isn't enough. That's why we use GitHub. My proposal for situations where neither GitHub nor Dropbox is a good fit (and what many people are already doing) is this: let's set up bare Git repositories in our Dropbox folders and use them as our Git remotes.

Let me explain. A "bare" Git repository is one that doesn't actually have any of the repository's files shown. Instead, it just contains the guts/mechanics of the repository (the stuff that's usually in the .git directory). This is the type of repository GitHub and others use, as it's only meant to be a place to push and pull from, not to do any direct file edits or commits from.

So let's go through the process of setting up what I'm talking about. First, in your Dropbox folder, create a place for all your repositories to live (mine is a top-level folder named "Git"):

Now, in a Terminal, cd into that folder and create a bare repository:

$ cd ~/Dropbox/Git
$ git init --bare mytestrepo.git
  Initialized empty Git repository in /Users/jetheis/Dropbox/Git/mytestrepo.git/

You should see the new repository (it's just a folder) show up now:

Inside, you'll see the guts of the repo:

That's really all you need to do to get the bare repository set up. Let's try using it now. First let's make a sample project with a couple of commits:

$ cd ~
$ mkdir testrepo
$ cd testrepo
$ git init
  Initialized empty Git repository in /Users/jetheis/testrepo/.git/
$ echo "Some Text" > testfile.txt
$ git add testfile.txt
$ git commit -m "Add a test file"
  [master (root-commit) 0220f05] Add a test file
   1 file changed, 1 insertion(+)
   create mode 100644 testfile.txt
$ echo "More text" >> testfile.txt
$ git commit testfile.txt -m "Add more text"
  [master f014b59] Add more text
   1 file changed, 1 insertion(+)

We'll check out the log and file content (to verify against in a second):

$ cat testfile.txt
  Some Text
  More text
$ git log
  commit f014b59d8d3af6e20bd5d671bd98f86e26fba743
  Author: Jimmy Theis
  Date:   Sun Feb 17 12:10:19 2013 -0500

      Add more text

  commit 0220f050e087d92ad96a549c2b913363f551b7fc
  Author: Jimmy Theis
  Date:   Sun Feb 17 12:08:50 2013 -0500

      Add a test file

Now we can hook up our new bare repository as an upstream for this one:

$ git remote add origin ~/Dropbox/Git/mytestrepo.git

And push to it:

$ git push -u origin master
  Counting objects: 6, done.
  Delta compression using up to 4 threads.
  Compressing objects: 100% (2/2), done.
  Writing objects: 100% (6/6), 458 bytes, done.
  Total 6 (delta 0), reused 0 (delta 0)
  Unpacking objects: 100% (6/6), done.
  To /Users/jetheis/Dropbox/Git/mytestrepo.git
   * [new branch]      master -> master
  Branch master set up to track remote branch master from origin.

You should see your Dropbox icon spin for a second while it syncs the files for you, though you'll still notice that inside your Dropbox version of the repository, you still don't see any testfile.txt, because again, only the guts of the repository appear here.

Let's try cloning from the bare repository to make sure our files and content are actually stored there. On the same computer (or another one that Dropbox syncs to), clone the repository:

$ cd ~
$ git clone ~/Dropbox/Git/mytestrepo.git testrepo2
  Cloning into 'testrepo2'...
  done.

Now we'll make sure we have both our current files and our history:

$ cd testrepo2
$ ls
  testfile.txt      
$ cat testfile.txt
  Some Text
  More text
$ git log
  commit f014b59d8d3af6e20bd5d671bd98f86e26fba743
  Author: Jimmy Theis
  Date:   Sun Feb 17 12:10:19 2013 -0500

      Add more text

  commit 0220f050e087d92ad96a549c2b913363f551b7fc
  Author: Jimmy Theis
  Date:   Sun Feb 17 12:08:50 2013 -0500

      Add a test file

No surprise, everything is reflected, just like we expected. We can now push and pull (the origin remote will already be hooked up since we cloned from the bare repository, so git pull and git push are all we need to run) and have those changes synced to all Dropbox-connected computers. Pretty cool, huh?

The really cool part is using Dropbox's sharing features with these repositories. Using the Dropbox website, you can either share your whole "Git" folder with others, or, because each repository is a folder, just share a single project:

A quick note about problems before we go:

If you try to pull or push while files are still syncing, or if something gets messed up in the repository, you may see an error message like this:

error: unable to find ea2ae105b8955b3f73d79065bc52ee3126cd2e4f
error: refs/heads/master does not point to a valid object!
Your configuration specifies to merge with the ref 'master'
from the remote, but no such ref was fetched.

The error may vary depending on what's gone wrong, but the solution in any case is the same: wait until Dropbox finishes syncing to make sure it's not just out-of-date files, then if the problem still exists, delete your Dropbox repository (mytestrepo.git) and create a new bare repository with the same name in its place:

$ cd ~/Dropbox/Git
$ rm -rf mytestrepo.git
$ git init --bare mytestrepo.git
  Initialized empty Git repository in /Users/jetheis/Dropbox/Git/mytestrepo.git/

Then push to it from the most up-to-date copy of the code:

$ git push origin master
  Counting objects: 9, done.
  Delta compression using up to 4 threads.
  Compressing objects: 100% (4/4), done.
  Writing objects: 100% (9/9), 706 bytes, done.
  Total 9 (delta 0), reused 0 (delta 0)
  Unpacking objects: 100% (9/9), done.
  To /Users/jetheis/Dropbox/Git/mytestrepo.git
   * [new branch]      master -> master

That should restore your repository state (as long as the pushing copy of the code was entirely up-to-date).

Again, this is probably old news for some, but it's definitely worth some lip service for anyone it hasn't occurred to yet.

Cheers!

When I lived in an off-campus apartment during my senior year, this tightness of money motivated some sort of extreme behavior, including my roommate unscrewing several of his vanity lights and the apartment reaching pretty uncomfortable temperatures before any heating or air conditioning was turned on.

I was unhappy living with such present reminders of my own lack of funds, so after graduation I reacted to my new full-time job and nice apartment by doing basically the opposite: making my apartment as comfortable as possible, and just budgeting a higher amount of money for utilities. After all, it would be sort of silly to be shivering in my own apartment when I can easily afford to heat the place.

After about seven months of this style of living, I noticed that my utilities budget has been bumped up several times and has nearly grown to the size of my grocery budget.

This bothered me for a while, so I started considering energy saving options to possibly cut down that cost and free up some more funds. Still in the "new job" mindset perhaps, I did hold on to a sort of prime directive, which is this:

Since I can afford to pay for my utilities, and since I value my comfort at least as much as the money high utilities would cost me, any energy saving ideas I implement are not allowed to make my life any less comfortable.

It seems selfish, and it is, but it also seems pretty fair. I value my comfort as least as high as my current utility bills, so it doesn't make sense to sacrifice it to make them lower. So with that background, let me explain what I've done to try to save some clams behind the scenes.

The Thermostat

My first purchase, which was really the one that kick-started my interest in cutting these energy costs, was a Nest Thermostat. It was a total impulse buy at Lowe's, but I'm really glad I did it. It is still just a thermostat, but it does bring some pretty sweet features to the table, some of which are aimed at saving money.

To start with, Nest connects itself to your home wifi, allowing you to control your thermostat through the Nest.com web app, or through the Nest iOS or Android apps. Being able to control the thermostat remotely may be one of the biggest cost savers, at least to someone like me, because I'm happy to turn down the heat in my apartment when I'm gone; I just don't want to have to sit in a cold apartment for an hour while it warms back up.

The other big advantages Nest has are its easy-to-design schedule and its Auto-Away mode. Between the two of these, it's very difficult for me to actually leave the heat on when I'm out of my apartment for any significant length of time.

I'm very hopeful that this gadget will save me some money, though it's yet to be determined how long it will take to pay for itself.

Here's what it looks like in my apartment (you can see it cooling down for the night here):

The Lights

As I considered how much money my new thermostat would save me, it occurred to that there may be other optimizable things about my apartment, namely the lights. I had always thought (and still do) that living in near darkness was sort of silly for the small amount of money it saves, but I hadn't considered what sort of difference it would make to make my existing lights more efficient, regardless of their usage.

A quick count around my apartment gives me 26 60-watt light bulbs that are almost always turned on, 3 more that are rarely turned on, and 2 in the laundry room that are almost never turned on. Twenty-six lights seems like a ton, but when each light fixture hold multiple bulbs and your apartment has lots of nooks and crevices, having the main areas lit means having lots of lights on.

Anyway, if we just look at the 26 bulbs that are on when I'm home in the evening (from about 5:30 to about 10:30, 5 hours), those bulbs use around 7.8 kWh per day, at $0.108662 per kWh (I know, Boone REMC is expensive), my regular lights cost me something like $0.85 per day, and that's just on weekdays when I'm only home in the evening.

Now, let's consider replacing each 60-watt bulb with its 13-watt CFL equivalent. Using the same math, such a replacement set of bulbs would only cost me about $0.18 per weekday, a $0.67 savings. That doesn't seem like much, but over the 22 or so weekdays per month, that's $14.70 in monthly savings, not even considering weekends.

As the above math shows, it seemed totally worth it to spend some money replacing the lights in my apartment. After a little research (and admittedly buying the wrong ones), I realized that it's really important to buy the Soft White CFL bulbs. Otherwise they look blue and your home looks like a hospital. With this new knowledge, I ended up buying these lights from Lowe's, though I also had to buy a smaller half-pack to go with it, as well as few with smaller bases for my ceiling fans.

All in all, I spent about $50 replacing the light bulbs in my apartment. I can hardly tell the difference in how my lighting looks (if anything, it's brighter in here), so I'm very excited to see what kind of money this ends up saving me.

(Oh yeah, I also ended up throwing away a ton of old light bulbs and making quite a racket in the dumpster)

The Water

The final change I made is technically breaking the rules I set for myself, but I'm really okay with it.

For a long time, I've just taken as long of a shower as I wanted, turning the water off basically when I got too bored or too hot. It's a great time to think, and I valued that along with the comfort of the hot water.

My shower head is marked as a 2.5 GPM (gallons per minute), so if we consider reducing a 30-minute shower to a 10-minute shower, once per day, that could possibly reduce my water usage by up to 1500 gallons (I use something like 2500 gallons most months).

Now in practice, I'm sure it won't be quite that much, especially if the shower head isn't outputting its full volume every minute, but the numbers above are at least interesting enough to warrant giving it a try.

So, for the last couple of weeks I've been trying to keep my showers to around 10 minutes, which is actually harder than I thought since I so naturally slide into a daydreaming mindset while I'm in there. I'm very interested to see what a difference making a conscious effort has. If it does significantly reduce my water costs (which are pretty high since my water and sewer are provided my the neighboring town of Whitestown, not Zionsville), I'm sure it will motivate me to be even stricter about my shower times.

The main reason I'm okay with this change even though it does introduce some discomfort is because I now really value the extra time taking a short shower allows me in the morning. This makes it less an issue of being afraid to take showers and more an issue of good time management with a side-effect of saving money.

Conclusion

I do somewhat regret how unscientific I've been about implementing these new practices and hardware, because my doing them all at once will pretty much make it impossible to tell which ones work and which ones don't, because all of the changes in power usage will happen in the same month. My water bill should be easier to interpret, so at least I'll be able to report on just how useful shower shortening is.

The other bummer here is that I won't be able to report any results for at least a few weeks. Even then, my bills may be a little inconclusive since I made these changes about a third of the way into each billing cycle. Hopefully, if nothing else, I'll be able to report whether or not it's working in a few weeks, even if I can't very well quantify just how well it's working.

If anyone is curious about any of the things I've talked about here, just let me know. I plan on writing a more substantial review of the Nest by itself after I've had it for a little longer, so stay tuned for that if you're interested but hesitant to spend the money.

Cheers!

If you haven't seen them before, the cards look something like this (image from American Express):

I do most of my shopping online, so I have often tried to use these cards on web stores (specifically Amazon), with very little success.

Because online stores require you to enter so much information (billing address, billing phone, name on card, etc.), it seems almost impossible to get the right combination of data that will let the card go through. Sometimes, the billing address needs to be that of the person who originally ordered the card; sometimes the name does too.

Amazon (and probably other stores) often authorize the card at a later time, so I've ended up in this weird crisis situation where my order is being processed, but my payment hasn't gone through, and I get an alarming email from Amazon with a deadline, like this:

We're having trouble completing the payment for the above order. The issuing bank may have declined the charge if the name, expiration date, or ZIP Code you entered at Amazon.com does not exactly match the bank's information.

Valid payment information must be received within 3 days, otherwise your order will be canceled.

Now I've got three days to try to figure this out (by trying random combinations of billing information), or I'll have to decide to just pay from my bank account. That sucks. So what do we do about it?

Most of the gift cards I've been given have listed in their rules that they can't be used to buy other gift cards. From experience, though, that rule does not seem to be very widely enforced, so here's what an Amazon purchase from a prepaid card looks like for me now:

Walk into a brick-and-mortar grocery store (Kroger), buy an Amazon gift card with my prepaid card, then use the Amazon gift card to make my actual purchase. Sometimes I've gotten a weird look from the grocery store cashier when he or she has asked to see my ID and realized the name on the card was "A Gift For You", but it's never prevented the purchase from going through.

For best results, it stands to reason that buying a gift card at the least technologically advanced store would have the highest chance of success, since they probably don't have a system that checks for gift card purchases. To find a suitable store near you, check out Amazon's list of gift card retailers, many of which are gas stations and grocery stores.

Hopefully this helps someone who's struggling with the same problem of being unable to actually use the money locked inside a prepaid card. At the very least, I'd encourage anyone thinking about buying one of these cards to reconsider and maybe just buy a store-specific card.

Cheers, and Happy New Year!

What's the project, you ask? Well, let me tell you.

The two most popular NPR programs, Morning Edition and All Things Considered, don't have official podcasts on NPR's website. You can listen to the stories with their online player, and you can even get the content and audio of the stories through their API, but there just isn't a podcast for either one of them.

That's where this project comes in.

First, though, a note. The main reason there isn't a podcast for either program is because NPR makes a lot of its money from licensing Morning Edition and All Things Considered to member stations, who in turn pay based on how many listeners the programs get.

This means that if you use this website (or listen only on NPR's site, or consume the API on some other device yourself), and don't listen to your local member station, you are essentially taking away their business. Please don't do that. I made this project because I really like NPR and I want others to be able to enjoy it too and see it be successful. If you truly are an online-only listener, or if you depend on NPR for your daily news, please remember to donate to your local member station.

Alright, back to the project.

It seems simple now compared to all the introduction and caveats above, but I suppose it is pretty simple: I made a website that allows you to subscribe to a Morning Edition or All Things Considered podcast. If you're interested, check it out (you'll find more complete instructions on the actual site):

http://www.missingnprpodcasts.com

Let me know if you have any questions or problems using the site, and happy listening!

Cheers,

This isn't intended necessarily to be a guide for others, because I'm no expert, have only done it once, and can't possibly account for any problems that may arise in someone else's attempt to do the same. However, I've found posts like this to be really helpful in my own experimenting. All I aim to do here is to record the steps I took, in order, to accomplish a really specific goal: get rid of the ads. I've embedded any files I used here, just in case they happen to be unavailable at a future date. Hopefully this will serve as a second reference for anyone who gets stuck following an official guide, or who's unsure of where to start in all of this.

So that's what this post is. It's a long one, and I'll randomly be switching between narrating and instructing, and I'm sorry for that, but it's just easier to write that way. This post specifically applies to Kindle Touch (4th Generation Kindle) with firmware version 5.1.2. Anything after that I can make no promises for (heck, I can't make promises for this), but hopefully it's still in some way helpful. If you're interested, read on.

First, how I got started. I found seriously every bit of the information I needed to accomplish this ad removal on this MobileRead page, though I've taken some of the steps that involve installing lots of packages replaced them with doing the same things the packages do by hand. Please please please start there. It's very likely you'll also find everything you need on that page, and it's obviously kept much more up-to-date than this post ever will be. Before you do anything, though, make sure you read all you can. If you're using a MacBook (or a Linux machine, or anything really), you'll hopefully get some benefit reading this post before you start. I'm not trying to scare you into reading my ramblings or anything, but I really would like to encourage you to get as much input as possible before you go doing things you can't undo. Also before using any files hosted here, make sure you check for a newer version on the wiki page.

Step 1: The Jailbreak

The actual jailbreaking of the Kindle is about the simplest thing in the world. I just plugged the Kindle into my MacBook with the MicroUSB cable, putting it in USB Drive Mode, then copied data.stgz into the root of the Kindle:

After that, I ejected the Kindle, unplugged it from the computer, then selected Menu -> Settings -> Menu -> Restart. While the Kindle was restarting, this new loading screen was visible:

After the Kindle was finished restarting, I saw the confirmation placeholder book, which I deleted (and you can too):

And... that's it. We're jailbroken.

Step 2: Connecting

Alright, now the Kindle's jailbroken. That's all well and good, but what does that actually get us? Well, jailbreaking simply installs another developer key that can be used to put custom apps on the Kindle. We're going to use it to install a package that enables USB Networking, a service that allows us to connect directly to the Kindle through a command line.

To do this, I copied update_simple_usbnet_1.1_install.bin into the root of the Kindle:

Then I ejected the Kindle, unplugged it, and installed the update by choosing Menu -> Settings -> Menu -> Update Your Kindle from the Kindle.

Once the Kindle has finished updating, I set the password (needed for login) by entering the following in the search bar:

;un password somepassword

Obviously using something besides somepassword for the password. Then I turned on USB Networking by entering the following in the search bar:

;un

Now, before you do anything else, open up Terminal.app (under "Utilities" in the Applications folder), and enter the following command (without the $):

$ ifconfig | egrep -o "^[[:alnum:]]+"

Leave the results of that command on the screen. Those are the networking devices your MacBook can currently see. Now connect the MacBook to the Kindle with the MicroUSB cable. It shouldn't go into USB Drive Mode like it usually does. If that's the case, we're in business. If not, eject the Kindle, enter ;un again, and try again.

Now for a slightly complicated part. We need to figure out which device the MacBook thinks the Kindle is. Run the previous command again (by hitting the up arrow, then Enter), and compare the results. There should be one extra device listed (probably at the bottom). In my case, this device was en3.

Once you've figured out the name of your Kindle (maybe it's the same one), run the following command to configure it (you'll be prompted for your computer's administrative password):

$ sudo ifconfig en3 192.168.15.201

Obviously use something besides en3 if you found your Kindle to have a different name, but make sure you use the same IP address. The Kindle relies on a really specific IP address belonging to it (192.168.15.244), so we configure it to have one somewhat close to that.

If all went well, we should be able to connect to the Kindle now. Enter the following command:

$ ssh root@192.168.15.244

You'll be prompted for a password. This time, it'll be the one you set up in the search bar of the Kindle. If your login succeeds, you should see a notice and prompt like this:

#################################################
#  N O T I C E  *  N O T I C E  *  N O T I C E  # 
#################################################
Rootfs is mounted read-only. Invoke mntroot rw to
switch back to a writable rootfs.
#################################################
[root@kindle root]# 

That's the command line prompt of the Kindle, and that means we're in.

Step 3: Breaking The Ads

Now that we've got administrator command line access to the Kindle, all we need to do is disrupt the way the Kindle downloads and stores its ads enough that it will fail back to just displaying the standard screensavers. To do this, we'll first do exactly what the giant notice says, remount the root file system (just like the $s, don't type the #):

# mntroot rw

Now let's go find those ads.

# cd /var/local
# ls adunits

You should see something like this:

1314512564245     4947350798237     7905915218628     8863644723128 9772216502999
2248931205866     5179523322443     8060227834200     8982827228459 admgr.json
3254245097874     5480504762067     8565874945799     9114782852577 admgr.seenactive

Those are all the sub-folders within the adunits folder, and that's where each ad's data is (for the most part), stored. What we're going to do, simply put, is turn off the main Java framework, rename the adunits folder (in case we ever want to restore it), replace it with just an empty file, remove all permissions to that file, then restart the main Java framework again. This way, adunits still exists if the framework checks for it (and all folders are really just special kinds of files), but the Kindle will fail to read or write any information to or from it, causing it to fail back to regular screensavers. Anyway, here we go. Careful not to mess these up.

# stop framework
# mv adunits adunits.bkp
# touch adunits
# chmod 000 adunits
# start framework

That's it; we're done. If you're interested in unjailbreaking your Kindle but leaving the ads turned off, skip down to the next section.

Otherwise, exit the shell with the exit command (you should see your prompt return to the one from your MacBook (ending in a $)), then restart your Kindle for posterity's sake. At this point, our mission is complete. No more ads.

Step 4: Covering Our Tracks

Now, even though we've managed to disable the Kindle ads, our Kindle is in sort of a weird state. There's an extra developer key installed, a set of applications that allows direct connection and command line access, and the ad storage files and folders mixed around. We can actually undo all but the last one to put our Kindle back in a sort of a non-jailbroken but still ad-free state, and that's exactly what I did with mine (though I actually left the USB Networking stuff in just in case I wanted access later the first time).

These steps are entirely optional, but they do provide a little peace of mind in our knowing that our Kindle is nearly normal after its surgery.

Removing USB Networking

This is the step I didn't actually do at first, but then thought better of it. To remove USB Networking, exit the Kindle shell with the exit command, unplug it, run the ;un command in the search bar to turn off USB Networking, then plug it back in to enter USB Drive Mode. Copy update_simple_usbnet_1.1_uninstall.bin into the root of the Kindle:

Eject it, unplug it, then from the Kindle select Menu -> Settings -> Menu -> Update Your Kindle. If the update is successful, USB Networking has been uninstalled. To test it, no amount of entering ;un at the search bar should be able to prevent the Kindle from going into USB Drive Mode when plugged in.

Unjailbreaking

To unjailbreak the Kindle, we just need to delete the new developer key. We can do this by hand (if you haven't logged out of your Kindle shell yet and uninstalled USB Networking), or by running the uninstaller. To do it by hand, just run the following commands:

# cd /etc/uks
# ls

You should see the following:

pubdevkey01.pem   pubprodkey01.pem  pubprodkey02.pem

The first one is the new developer key. Just delete it:

# rm -f pubdevkey01.pem
# ls

You should now see it missing from the list.

If you'd rather (or must because you've removed USB Networking) do it with the official uninstaller (that does the same thing, just with a fancy status bar), exit the shell, turn off USB Networking with ;un in the search bar, then plug the Kindle back in so it goes into USB Drive Mode. Copy update_jailbreak_1.2.N_uninstall.bin into the root of the Kindle:

Eject it, then from the Kindle select Menu -> Settings -> Menu -> Update Your Kindle. If the update was successful, your Kindle is unjailbroken.

I'm quite happy with my ad-free, unjailbroken, inaccessible-through-command-line-interface Kindle Touch. I hope this post was helpful to you; I enjoyed writing it.

Cheers,

I kept happily exploring my cool new toy, including connecting it to the wifi in Emilie's apartment. I noticed that after connecting, banner ads started appearing at the bottom of the home screen (mostly advertising other Kindle books, but also including a few annoying ones from Intel (I think?) and AT&T).

I wasn't really bothered by this, and a little bit of reading in the included manual told me that I actually owned the "Special Offers" edition of the Kindle Touch, which gives buyers about a $40 price break in return for having ads appear on the menu screens.

To me, this is no big deal (actually, I sort of like the idea, especially since the ads seem pretty relevant a lot of the time). However, I got a lot less cheerful when I put the Kindle to sleep again and was presented with a whole new set of background, including these (actual images extracted from the device):

Suddenly this "Special Offers" thing seems a lot less tolerable. In fact, this is enough to make me want to leave my Kindle in a drawer when people come over instead of out on a table, just because these ads are so unsightly.

So What's The Big Deal?

If you've opened a web browser in the past few years, you've come to realize that internet advertising has very seriously become part of our lives. Think about it: when's the last time you saw a "punch the monkey for an iPod" or "you're the 1,000,000th visitor!"? Probably not for a while. Instead, you see ads that are relevant to either your (perceived) interests or to the content you're reading. This is largely because advertisers (led in no small part by Google and its AdSense) have formed a much more mature, symbiotic relationship with users than ever existed in years past. We use free services, knowing they're being paid for by ads, but we don't mind because the ads aren't intrusive or offensive most of the time, and sometimes they're halfway relevant.

Now let's evaluate the case of Amazon and its Kindle "Special Offers" program. First, despite any original good intentions or origins for the pricing model, as it stands now, the "Special Offers" version of the Kindle Touch is the only one displayed on the Amazon web site, and the product page has this to say about it:

What I don't gather from reading this is that whenever I put my Kindle down, I'm going to see a giant, tasteless ad for AT&T, not some pretty wood finish with a note at the bottom about a product. (I actually found myself cycling in and out of the screensaver until I at least got to an advertisement for a book before I put it down.)

What I also don't gather is that this is a price-subsidized model. Nowhere on this page am I told that I'm actually being paid $40 to replace the gorgeous screensavers on my Kindle with ads.

What I really don't gather, and what I've really had to wrap my head around for the past few days, is that because this screen never turns off, I'm actually being paid $40 to install a permanent billboard in my apartment whenever I'm not actively reading. Consider that. What if a cell phone provider put banner ads in every text you sent, or if your car played audio commercials from external speakers whenever it was parked. I wouldn't accept $200 to have guests to my apartment force-fed advertising from companies I pretty decidedly dislike (that's the other thing: there's no feedback mechanism; you can't make ads more relevant, express your interests, or veto content. It's AT&T; it's MegaCorp; it's not an option.).

After purchasing the Kindle and enjoying its pretty screensavers, then having them suddenly get replaced by unsightly ads, users can find a settings page on Amazon's website that will allow them to pay an additional $40 to remove the plague of ads they hardly realized the signed up for. This is pretty unacceptable.

What Do We Do About It?

I'm not a huge fan of "hacking" or "jailbreaking." I've been down that road of tinkering with electronics, and while it's fun in the short term, it almost always causes problems in the long term that make you really just wish you could have things back to the way they were. As a result, I'm really only game for "jailbreaking" if it solves a really significant problem. In my opinion, this is the case with the Kindle.

The Kindle Touch is a wonderful piece of hardware, and its software is pretty top-notch, too, especially for the function it serves, but the permanent ads are just too much.

Generally speaking (I am not a lawyer), there's a precedent for jailbreaking not being illegal, even if it is in violation of a terms of use contract for a device or service (especially for a Linux-based device like the Kindle). What it can cause is a voiding of one's warranty or a discontinuing of one's provided services.

For this reason, and because I'm really not a fan of this $40 shakedown from Amazon if my dissatisfaction with ads grows unbearable, I consider the Kindle Touch not to have a $40 ad removal fee, but to have a $40 optional warranty. I have no intention of paying that $40, and if that voids my warranty, so be it. I've jailbroken my Kindle Touch, taken a couple of steps to disable the ads, then left it alone, and I couldn't be happier with the results. I've got my beautiful screensavers back, but other than that the device functions as it always has. I'll cover my process of doing this in a later post for anyone interested.

So to wrap it up, here's where I stand: advertisers are welcome to bring relevant, non-intrusive ads into my life, and I won't block them. Heck, I'll probably click on a few of them. However, there is a line, and once it's crossed by, say, attempting to commandeer my coffee table as a billboard, the symbiotic relationship is broken. Plenty of people will do a little research, figure out how to turn the badness off, and resume their lives, even at the expense of a warranty here or there. By being too aggressive, advertisers and advertising platforms lose, and I hope the folks at Amazon look long, hard at this pricing model before it gets any worse.

As for me, I'm going to pretend this all never happened, that there never was a "Special Offers" edition of the Kindle Touch. Now, if you'll excuse me, I've got a book to read.

Cheers,

I am obviously not a lawyer. I do not own any of these images; they are the property of Amazon.com Inc. and distributed alongside the Kindle Touch device (which you really should buy one of).

Understand that these images are copyright property of Amazon.com Inc. and that you may only use them with permission, not from me, but from the copyright owners.

With that said, and reminding you again to follow all the rules, enjoy!

You can also download the complete set as a ZIP archive here.

Cheers,

As a result, I, like many others, have turned to Amazon S3, a service actually geared toward hosting media and other non-text content. With S3's Free Usage Tier, I actually haven't had to pay a dime yet (it lasts for one year), and when I do, it'll be a very small amount.

S3 uses a pay-for-what-you-use style of billing, where you're billed based on how much storage you're using, how many requests are made for files you've uploaded, and how much data actually gets transferred. It's changed a few times, so I won't bother copying down the billing plans, as they'll likely be outdated quickly. Instead, I'll just link to them for anyone interested.

Because S3 bills based on how much data gets requested per month, anything we can do to reduce that number actually saves money. Is there something we can do? Well, yes.

Making Our Files Smarter

It's sort of a perfect solution: reduce the number of requests coming into our S3 account and speed up page load times, without the user being negatively affected at all. All this is accomplished by setting the Expires value of our files to some date off in the future. This will become the HTTP Expires header value that lets browsers know not to request the resources over and over again, instead loading them (nearly instantly) from their local caches.

NOTE: This is obviously only useful for resources that actually won't change, like images.

We can set this metadata value from the S3 Console either at upload time (Set Details -> Set Permissions -> Set Metadata in the upload wizard), or from the Properties pane that can be opened for any existing file (find it under the Metadata tab).

In either case, use the Add more metadata button to create a new key/value pair with Expires for the key and the file's expiration date for the value:

(during initial upload):

(or after initial upload):

Now, here's a possible sticky point. HTTP specifies that Expires dates should be in RFC 1123 format. It's a very exact format that can be easily messed up if you're trying to enter it by hand. Luckily, Ruby's CGI class has a built-in way of generating these dates. If you're using a Mac (or a Linux/BSD box with Ruby installed), use this handy one-liner in a terminal (Terminal app on Mac under Utilities in the Applications folder) to generate the date (without the $):

$ ruby -r CGI -e 'puts CGI.rfc1123_date(Time.local(2013, 7, 14))'

Instead of 2013, 7, 14 (my 24th birthday), use whichever date you have in mind. The format is year, month, day. If you're really fancy (and sure that your files won't change), use the max value for a 32-bit timestamp:

$ ruby -r CGI -e 'puts CGI.rfc1123_date(Time.at(2 ** 31 - 1))'

Here's that value for any impatient copy-and-pasters:

Tue, 19 Jan 2038 03:14:07 GMT

Now that we know how to set our file expiration date, let's look at what actually happens when we do.

Does It Actually Work?

Here's an S3-hosted image of Octobi Wan Catnobi that has no extra metadata set:

and here's an S3-hosted image of Spocktocat that has its Expires header set:

We can verify that this is true pretty easily. If you're using a UNIX-like operating system (basically anything but Windows), open a terminal (Terminal application on a Mac, found under Utilities in the Applications folder), and enter the following command (without the $) to make a request for the first image:

$ curl -v http://dl.jetheis.com/s3-metadata/octobiwan.jpg > /dev/null

Now look at the portion of the output that is prefixed with a <. Those are all of the response headers:

< HTTP/1.1 200 OK
< x-amz-id-2: +JWpez+WdCrliLIuJgb1JQ9GrdUaM2QkRF/Cc+oZBmvtZWMBCsYb4bavdptvXJEo
< x-amz-request-id: 616907A681625FE3
< Date: Wed, 07 Mar 2012 17:05:14 GMT
< Last-Modified: Wed, 07 Mar 2012 16:38:05 GMT
< ETag: "dcef3abedf0e0761203aaeb85886a6f3"
< Accept-Ranges: bytes
< Content-Type: image/jpeg
< Content-Length: 65307
< Server: AmazonS3

No Expires. Let's try the image we set that header on:

$ curl -v http://dl.jetheis.com/s3-metadata/spocktocat.jpg > /dev/null

We'll look at the output prefixed with < again:

< HTTP/1.1 200 OK
< x-amz-id-2: IZevTGh6eOzexdotN5RaSTaROUtmWc+7hWpq1t7CVD6Mz98G2m174S35wFEkk8pD
< x-amz-request-id: E321C35ACC2CB79E
< Date: Wed, 07 Mar 2012 17:10:07 GMT
< Expires: Sun, 14 Jul 2013 04:00:00 GMT
< Last-Modified: Wed, 07 Mar 2012 16:44:52 GMT
< ETag: "c817148a2d2589ca977fed81c2e5a6f2"
< Accept-Ranges: bytes
< Content-Type: image/jpeg
< Content-Length: 69947
< Server: AmazonS3

And there it is: our shiny new Expires header:

Expires: Sun, 14 Jul 2013 04:00:00 GMT

A Better Example

While this is all well and good, we haven't quite proven that setting this header does anything or cuts any costs. We'll now conduct a true test of the new configuration using Google Chrome (this one can be performed on Windows, too). Follow along if you'd like.

First, browse to this page using Chrome and open the Developer Tools pane (Alt + Command + I on a Mac, or by clicking the wrench and selecting Tools -> Developer Tools).

In the Developer Tools pane, click the Network tab. We'll see that there isn't anything there yet, because Chrome isn't "recording" network activity unless the pane's open.

Now click the Jimmy Theis at the top of the blog to jump back to the home page. We're navigating away from and back to the page because pushing Refresh actually forces all resources to be reloaded.

Now here's the kind of wonky part. Chrome does a great job of making browsing fast, so it actually does cache resources without expiration dates for a short time. To circumvent this, it seems the resources need to not be accessed for quite a while. So, forget about this and go browse Reddit or Hacker News or something and come back in about 30 minutes.

Once you've browsed some and allowed sufficient time, find the link to this post on the homepage (or the archives if this is old enough), and click on it. Make sure the Developer Tools pane is still open.

Once the page has loaded, scroll through the network activity. You should see both octobiwan.jpg and spocktocat.jpg in the list, probably somewhat close to each other.

Whoa! Something actually happened. We can see that spocktocat.jpg was loaded "(from cache)" and took a total of 0 ms to load, while octobiwan.jpg shows a 304 "Not Modified" response, a data transfer of 286 bytes, and a latency of 206 ms. So what does this mean?

Let's look at our base case first: octobiwan.jpg, which has no information dictating when it expires, could have potentially changed (from the browser's point of view), so Chrome makes a new request for the image. The intelligent computer at Amazon gave it back a 304 response, which simply tells the browser that the resource hasn't changed, so we won't bother sending it again. This saves us the bandwidth of downloading the entire image again (the request is 286 bytes instead of the full 60+ KB the image takes up), but it still makes a request to S3, and that costs money.

On the other hand, spocktocat.jpg is marked as not expiring for years from now, so Chrome doesn't even bother making a request at all. It simply grabs the image from the cache and displays it. This speeds up page load and saves us money on our Amazon bill. As a side note, if that image where to ever change, doing a hard refresh of the page would force it to be reloaded, so we're not stuck with an outdated image if we ever change our minds.

Conclusion

It's relatively simple to set the Expires value of content hosted on S3, and it does have a real effect on both site performance and the number of requests made to Amazon. In fact, apart from the work of setting those values, there isn't much of a downside to the practice. Some software suites offer this functionality in a little more accessible interface, and lots of other posts recommend using these (paid) software suites to set these extra metadata values. The purpose of this post, however, is really to highlight a potential problem and present a solution that doesn't require spending extra money. Feel free to try any S3 management software, but know that you've already got the tools you need to start tuning your account for cost effectiveness.

Cheers,

The puzzle is called "One Tough Puzzle" (available from Amazon and others) and consists of 9 puzzle pieces, each with four interlocks (two in and two out). The interlocks are shaped like each of the four suits in a conventional deck of cards, so a positive heart interlock can link with a negative heart interlock, and so on. Below is a picture of what the puzzle pieces more or less look like.

Image credit: Official Product Page

To solve the puzzle, one must arrange the pieces such that they form a three by three square when interlocked. The outer edges don't necessarily have to be neat or uniform in any way, but the box does specify that there will be six interlocks protruding from the edge of the finished puzzle. Because of this lack of an edge, the puzzle offers basically no hints as to whether or not you're headed down the right path, making it especially frustrating and probably near impossible for someone without tons of time on his or her hands.

After a lot of trying, I did solve it (though not necessarily by conventional means). So, for the impatient (or the Google searchers), here's the solution (assuming your puzzle pieces match the ones I worked with):

H: Heart
C: Club
S: Spade
D: Diamond
             D       S     
 +---|---+---|---+---|---+ 
 |   S   |       |       | 
 -H      -D      -H      -S
 |       |   H   |   C   | 
 +---|---+---|---+---|---+ 
 |   S   |       |       | 
 -C      -S      -C      -D
 |       |   H   |   D   | 
 +---|---+---|---+---|---+ 
 |   H   |       |       | 
 -D      -D      -C      -H
 |       |   C   |   C   | 
 +---|---+---|---+---|---+

For the more curious, I'll talk a little bit about how I solved it. If you're only here for the solution, bail out now.

First of all, I should make it clear that I didn't just try different combinations by hand until I found the solution. I'm not nearly patient enough, and I don't think that would even be all that much fun. Instead, I wrote a small program (a script really) that tries all the possible arrangements until it finds a solution. This is obviously much faster than trying combinations by hand because no physical pieces are being moved, and a computer can think considerably faster than a human.

I wrote the script in JavaScript, the language used to add functionality to most web pages, so that anyone will be able to run it right here from this blog post. To that end, I've created a jsFiddle that you can test drive right here. I apologize about how primitive the interface is; it's really meant to be a proof of concept. If you'd like to create a better interface, feel free.

To use it, just set the interlocks on each of the pseudo pieces (the red squares at the top). + means the interlock is protruding, and - means it isn't. If your puzzle pieces are the same as mine, you shouldn't have to change a thing; just hit the Solve button. The solution to whatever you've entered will print below the Solve button, unless one can't be found.

EDIT: I've also added a second button, Find Solutions with Flipped Pieces, that will do exactly what it says. Any piece marked with an F in the solutions is a flipped version of another piece. (This one takes a few seconds to run)

Mobile Users: Use this link for full screen.

All of the code is available in a Gist (MIT License). If you'd like to tinker with it, you should probably do it from the Gist, not the jsFiddle. I've directly imported the solving functionality in the fiddle, so you can't really mess with it too much, but I have included an html page that has the same content as the fiddle in the Gist.

To play with it, clone the Gist, run the tests, and open the demo:

$ git clone git://gist.github.com/1544631.git onetoughpuzzle
$ cd onetoughpuzzle
$ open tests.html
$ open playground.html

If you're curious about the algorithm used, I'll talk about that now. At the core of the script is a function called solvePuzzle that does all the state exploration and real solving. It employs a depth-first search using a stack to keep track of states to be explored. By state, I mean the following:

• A partially filled board (filled left to right, top to bottom) with valid pieces placed in specific orientations.
• The remaining pieces not yet used on the board.

The algorithm, in plain English, looks like this:

• Create a new state that is just the empty board with all of the pieces remaining to be placed.
• Add it to the workspace (states to be explored next, represented by a stack).
• Repeat the following until a solution is found:
  • Pop (remove) the first state in the workspace.
  • Using this state, evaluate each piece remaining to be placed one at a time:
  • If the piece can fit in the next available space on the board in any of its four rotated orientations, create a new state with that piece placed in each valid orientation and add that to the workspace.

If a state is ever removed from the workspace and found to be a valid solution, the algorithm exits successfully. If, however, the workspace is ever depleted of states, no solution exists for the puzzle and the algorithm exits unsuccessfully. The actual code for the algorithm is below.

var solvePuzzle = function(pieces) {
    // Helper function that removes the first element of an array, if there is one.
    var shortened = function(ary) { return ary.length <= 1 ? [] : ary.slice(1); }

    var board = new Board();
    var workspace = [];

    // Push initial empty board state
    workspace.push(new State(board, pieces));

    while (true) {

        // Base case that will be triggered if a solution is not found
        if (workspace.length <= 0) return null;

        // Retrieve the top state on the workspace
        var state = workspace.pop();

        var board = state.board;
        var pieces = state.pieces;

        // Base case that will be triggered when the board is filled
        if (board.isFull()) return board;

        for (var i = 0; i < pieces.length; i++) {
            // Retrieve one of the remaining pieces
            var piece = pieces[i];

            // Strip that piece out of the pices left over
            var nextPieces = pieces.slice(0, i).concat(pieces.slice(i + 1, pieces.length));

            // Generate rotations of the retrieved piece
            var piece2 = piece.rotated();
            var piece3 = piece2.rotated();
            var piece4 = piece3.rotated();

            // If any rotation of the piece fits in the next available space,
            // create the state with that piece added to the board and push
            // it onto the workspace stack
            if (board.canFitNextPiece(piece)) workspace.push(new State(board.withNextPiece(piece), nextPieces))
            if (board.canFitNextPiece(piece2)) workspace.push(new State(board.withNextPiece(piece2), nextPieces));
            if (board.canFitNextPiece(piece3)) workspace.push(new State(board.withNextPiece(piece3), nextPieces));
            if (board.canFitNextPiece(piece4)) workspace.push(new State(board.withNextPiece(piece4), nextPieces));
        }
    }
}

There's obviously quite a bit more code that defines the models for pieces and boards, as well as a test suite I used while writing the logic. I can't promise that it's bulletproof, so please let me know if you find any mistakes.

I had a lot of fun working on this problem, and I hope it was at least half of an interesting read, even if search algorithms are old news to you.

Cheers, and Happy New Year!

This post has nothing to do with me other than the fact that my experiences are one of the data points. In fact, this could probably more accurately titled Things I Wish Someone Had Sat Me Down and Told Me Four Years Ago.

Before we begin, let's assume that you've already heard the standard job interview advice: be yourself, dress up, make eye contact, ask them questions, etc. I'm not proposing that we throw out any of the age-old wisdom of folks in university career services offices. Rather, I'd simply like to offer up a few addenda:

1. Don't be Yourself

Yeah, yeah, I know I just said I'm not contradicting old advice, but trust me, I'm not. Hear me out on this one.

When an advisor says to "be yourself" in an interview setting, it makes it sound like you ought to be the person you are every day in engineering school. There's just one problem: that person is basically a schizophrenic shut-in with sarcasm tourettes. No offense; we're all like that. The only problem is that nobody wants to hire Jimmy Weirdo, no matter how good of a programmer he is.

So how do we fix it? Pretend to be someone totally different? Nope. Try this: take a couple of minutes and think about what you're going to be like in 5 years. You'll still be you, but you'll also be a mid-twenties professional developer. That's the guy this company wants to hire, and that's the guy you need to start acting like.

Now, let's be clear. I'm not saying that you need to act like you've already hit your midlife crisis to get people to like you. Rather, I'm saying that it's profoundly uncommon for a company to meet a programming student who is demonstrating that he is ready and willing to grow up.

So how do we do this? Here's my running list:

1. Get a haircut. A good one.
2. Shave. Zero hair coming out of your neck.
3. Buy some stylish business casual clothes. I know, I'm horrible at this too. Get a girl (not your mom, or your aunt) to help you.
4. Practice wearing those clothes. Learn to tie a tie loose enough that your eyes don't bug out when you sit down (you know exactly what I'm talking about). Adults are comfortable in clothes.

And most of all, just act like an adult. I'll cover it more in a second, but seriously, just think about how you're probably going to act in a few years when you don't have Mountain Dew dripping off your teeth and try to emulate that.

2. Know Your Stuff

If there's one thing that will get you not hired, no matter how good of a programmer you think you are, it's not knowing the fundamentals. Whether you call yourself a PHP developer, an embedded systems programmer, or a system administrator, if you're showing up to a technical interview for a developer position, you absolutely will be asked the fundamental questions. It's incredible how many smart kids blow these. I'll admit that I've been one of them.

So what do you need to know? Well, that probably depends on what you're applying for, but I do have a running list of things that you should bring with you to a technical interview:

1. Polymorphism. If you aren't able to basically recite what polymorphism is, don't bother showing up.

2. Memory layout. Seriously. If you don't know the difference between the stack and the heap, you might be about to look pretty stupid.

3. Access modifiers. Specifically public, private, etc., as well as static, and sometimes more language-specific modifiers like abstract and virtual. Even if you don't use a language that uses them, know what they mean.

4. Data structures. Know these inside and out. Literally. Know how they work, the efficiency of the operations on them, and what they're useful for. Start with this list:

• Lists. Array-based and linked. Know the difference.
• Stacks
• Queues
• Hash Tables (the answer to 80% of programming questions)

• Binary Search Trees (likely used as a set, which you should also know)

  I've also used Tries and Heaps from time to time in interviews, so those are great to know as well.

1. Sorting. Know Merge Sort, Quicksort, and the difference. It also may be useful to know a few of the less efficient but more common ones (Bubble Sort, Selection Sort, Insertion Sort, etc.) so you can quickly identify them in existing code.

2. Searching. Know how to search the various data structures that you have in your utility belt, but also know something about solution finding (searching states in a problem). Specifically things like pathfinding in a maze, collecting rewards, solving sliding puzzles, etc. Know the difference between bredth-first and depth-first search, and be able to implement them quickly. If you're applying for a very technical job, you're probably going to need to know more.

3. Optimizations and efficiency. If I had a nickel for every time I heard, "Okay, but how can we make it faster?" Know how to pick a faster data structure, be able to speak intelligently about your decisions. Also know a thing or two about memoization.

4. Database structure. One kind of question that really seems to sneak up on students is the dreaded design question, usually worded something like, "So, take a few minutes and describe how you'd design eBay." Well, take some time and think about it. It basically comes down to being able to design good Domain Models, ER Models , and knowing a thing or two about database normalization.

5. Design patterns. Ever heard of the Gang of Four? If not, time to put on your reading hat and learn something. If there's one thing that can really make you seem like a professional in interviews, I beleive that this is it. If you're unfamiliar, start here. Also make sure you're familiar with MVC.

6. Other interview questions. Go hunting for classic technical interview questions. There are scores of them online, ranging from brain teasers to full blown implementation problems. Get good at thinking on your feet and solving these in 10-20 minutues or so.

There are tons more, but that should really get you started and prepare you for 80%+ of interview questions (and honestly probably make you immediately more qualified than half of your peers). In case you're still interested, a few that I left out are development methodologies, testing strategies, and dynamic programming.

CAVEAT: Although I've really tried to stress the importance of having a strong foundational knowledge going into your interview, one critical thing to remember is that under no circumstances should you pretend to know something you don't. You're only digging your own grave at that point. Unfamiliar with a term or concept? Just say so. You may be surprised the good conversation that comes out of it, and it may be the difference between you solving a problem and you looking like an idiot.

3. Don't be an Ass

This one. I'm pretty convinced that this is the number one reason smart people don't get good jobs. This is also one of the hardest things to do, because when it comes down to it, you have no idea that you're being an ass. I sure didn't.

Fundamentally, it's a matter of respect. If you can't respect the people who are interviewing you, you're unhirable. There are a lot of ways you can be incredibly disrespectful without even knowing it, so let's look at a few cases.

First, let's get one thing straight: you're not doing the company a favor. If anything, you are blessed that your inherent social awkwardness drove you into a field that happened to explode with jobs during your lifetime. Remember what you're doing: you're asking someone to consider you qualified enough to sign over large sums of money to you twice a month in return for time and effort spent in an office. That's not a favor.

"Yeah, but I'll make them so much more than they'll pay me." Yeah, that's the idea, and it's called being a business. Don't flatter yourself into thinking you're some kind of anomaly.

"Yeah, but I'm a rockstar programmer! Nobody in the whole class can sling code like me!" That may be. And that should make you the number one pick for the position, right? Wrong. The only person who can probably see that you're a great programmer is the developer conducting the interview, but he's not so much interested in money-making potential like HR is. He's hiring a team member who he may have to work with for the next 10 years. He can teach a mediocre developer the ways of the company, but he can't make you less unbearable.

Here's another one of my favorites: an interviewer is giving you the rundown of the company's software architecture, and he mentions a specific piece of technology/framework/library/whatever that you used at one time but don't anymore. You, being the extremely experienced developer, instantly say, "Ew!" and smirk like you're better than someone. Come on. First of all, you have no idea what sort of design and architecture decisions went into selecting this particular piece of technology, and your largest code base to date probably hasn't crossed 1000 lines of code, so you wouldn't even be qualified to speak on it if you did know the reasoning behind it.

I don't want to rant too much, but I do want to make this clear: I've seen more opportunity lost due to self-entitlement than I have due to lack of qualifications. If you walk in acting like you own the place, you'll come up short every time.

4. Be Interesting

Okay, let's take a break for a second. If you can master the previous three points, you're in the top slice, and you'll get job offers. No questions asked. From what I've seen, there are just a couple more things that really set you apart in the extremely competitive positions, so I think it's good to cover those as well.

One of the most important things you can do to win the really desirable positions is to be different from your competition. It seems obvious, but it's something that's largely lacking from those entering the professional world.

Now, I don't mean different like "I only wear sandals, because I don't believe in shoes." That's obnoxious. I mean different in that you've followed your personal technical passions, relevant to the position or not, and done something on your own without anybody telling you to. Did you make a website? Sweet. An app? Very sweet. Anything at all (sigh, yes, even a game) that you've done on your own really shows a ton about the kind of person you, and it gives you plenty to talk about in your interview.

Another easy way to be interesting is to read. Read Hacker News. Read /r/programming. Read Slashdot. Read something. One of the most satisfying feelings is being knee-deep in an interview with a company that uses all sorts of technologies you've never heard of and having your interviewer mention something you've read an article about. Being able to contribute that little information (as long as it's not some sensationalist blog article) sometimes completely changes the dynamic of the interview for the better.

Sometimes even more important than reading things is trying things. Take any opportunity you get to try out a new tool, framework, or language. Even if you never do anything useful with it, you just added something to your interview tool belt, and you might even be able to answer questions about it.

One way or another, it's important for you to be different from your peers. It seems that more and more employers are hiring batches of students from the same colleges, so being the one guy whose resume doesn't look exactly like his transcript is probably the biggest favor you can do yourself. Heck, it's about the only point in this post that's any fun, so why not?

EDIT: A great piece of advice from Kenny Gao:

I think it's worth adding that a big part of Being Interesting (or more generally, being memorable) is being knowledgeable about the company that you're interviewing with. I'm always surprised at the positive reaction that I get from interviewers when I ask them about something that's unique to their company that they're passionate about, and it makes for a great entry point into a meaningful discussion.

5. Be Charming

This final point is probably the hardest one to advise on, but it seems to really make a difference when it comes down to it. You probably know the situation all too well: someone who's half as qualified as you but is just so damn likeable that nobody can say no to him gets an offer before you. It's not sneaky or deceitful; it's just the honest nature of people: they hire who they like.

If you're one of these lucky folks, congratulations; you're already probably basking in a wonderful life. As for the rest of us, let's do our best to emulate some of this charming behavior.

Why? Well, if there's one thing you learn from interviewing, it's that there will always come a time when the ship is sinking. It's these times when the only thing you've got left to save you is a grin, a little joke, and as much charm as you can muster up. It's not that the charming guys among us don't make mistakes; it's just that their mistakes seem so insignificant since we like them so much.

I really don't have any great advice for how to be more charming. It's something I don't think I ever really got a good hold of. If you can find some way to channel your inner Sinatra though, you've got the world by the tail.

Well, that about wraps things up. Again, this is in no way a definitive list of interview tips. Rather, it's just a collection of things that get said a lot but never officially written down. If it helps even one person get a job, it'll be entirely worth the time it took to jot it down.

Cheers,

Mike Lester gets the credit for this idea. I wasn't aware of this feature in Chrome until he showed me. So thank him.

If you've been a student at Rose-Hulman for more than a day, you know all too well the blessing and curse that is the Schedule Lookup Page. We're all thankful that our college can be so close knit and trusting that we can share this information with each other, but we also generally don't like the schedule lookup page. I don't need to list complaints here, but one of the biggest ones is the number of clicks and the amount of typing it takes to find any one student's schedule.

The good news is that (because of Google Chrome's awesome features) we can speed up your boring old Schedule Lookup workflow and make you a real Rose-Hulman power user, and it will look something like this:

To accomplish this, we'll set up a Custom Search Engine in Google Chrome that will let us search the schedule database directly. It's pretty easy, so let's get started.

First, open the preferences pane in Chrome (⌘, on a Mac, or by clicking the wrench and selecting Preferences (Options on some systems).

Once inside the preferences pane, click the Manage Search Engines... button.

You should see two sets of search engine entries, Default search options and Other search engines. At the bottom of the Other search engines box, make a new entry as shown below:

(Here's the link to copy and paste into the third field)

https://prodweb.rose-hulman.edu/regweb-cgi/reg-sched.pl?termcode=201220&view=tgrid&id1=%s&bt1=ID%2Username

Let's review what we just did. We created a new search engine that will be triggered when we enter the keyword schedule, followed by a space, in the address bar. This new search engine will display its name as Schedule Lookup. If you'd like to change either of these to something you like better, feel free; you won't hurt anything as long as you don't use a name that's already taken by another search engine.

IMPORTANT: If you're following these instructions and it's not Winter Quarter 2011, you're going to need to modify the URL pasted in the third field slightly: the six digit number after termcode= in the URL will need to be changed to the current Rose-Hulman term code (in the posted URL, it's 201220). If you're unfamiliar with how Rose-Hulman term codes work, here's a reminder (remember not to put a space in your actual term code):

2012 20
 |    | 
 |    |- 10 times the current term number (1 for fall, 2 for winter, 3 for spring)
 |    
 |- The calendar year this academic year ends in

Once you've made any changes, it's time to try this thing out. Close your preferences pane and type schedule someusername in your address bar. You should see it automatically switch to say Search Schedule Lookup, and you should land on the appropriate schedule page when you hit Enter. You should also be able to search for partial names, just like on the regular Schedule Lookup Page.

One more thing: While we're at it, let's solve one more annoying problem with the Schedule Lookup Page: the fact that you can't seem to get a link directly to your own schedule. Take the link below, change TERMCODE to the term code you figured out in the last section and USERNAME to the username you want to link to, and voilà! You've got a link directly to a schedule page.

https://prodweb.rose-hulman.edu/regweb-cgi/reg-sched.pl?termcode=TERMCODE&view=tgrid&id1=USERNAME&bt1=ID%2Username

EDIT: Will Anderson created a custom chrome search engine with even more functionality, hosted on his blog. If you're looking for more flexibility beyond what this post describes, check out his post.

EDIT FOR FIREFOX USERS: Tom Most created a GreaseMonkey Script that automatically makes schedule pages "bookmarkable" when you reach them from the schedule lookup search page. If you're a Firefox/GreaseMonkey user, check it out.

Cheers,

First off, I have noticed this pattern of never having a blog that's more than a year old, and I do see it as a potential problem, because I may eventually have something interesting to say that may be useful more than eight months in the future. I'm not saying that it's happened yet, but I'm not ruling out the possibility.

Second, I think I'm finally growing out of this idea that I need to play system administrator for all the things I depend on, so I've decided to move my blog to "The Cloud" where it can be safe from my sometimes very stupid hands. This is probably the best decision I've made in a while. Part of this decision includes switching from Wordpress to Octopress, which I have to admit, makes me feel very comfortable writing posts so far.

Third, I did have a lot of posts about my work at Microsoft as a summer intern, and while there was nothing particularly top secret about the content of those posts, it's probably easier if I don't claim responsibility for things I say or infer about the company, especially now that I'll be going to work full time for a company besides Microsoft. I'm sure I'll mention it from time to time, but we'll take that as it comes.

I'm excited to be making big decisions about my social media life, and I really like the Octopress platform so far. I'm sure I'll have more to say about it, and I imagine I'll configure it some more and discuss my thoughts on it in the future once I've actually used it some more.

Cheers, and Happy Thanksgiving.