Dynamic Programming

The Robber Problem

Imagine that you are a burglar planning a heist. Your target is the National Museum, a gallery filled with precious art, artifacts, and dinosaur bones. Your mission is to confiscate as many of the exhibits as possible. The constraint, however, is that you may not loot adjacent rooms. Doing so will trigger the security system and blow your cover.

Given a list of non-negative integers that represent the value of each exhibit, what is the maximum amount of money you can expect from your heist?

For Example

Let's try this list: [5, 3]

When the list is short, our choice is straightforward; we'll take the larger of the two values, $5. But what if there's a third value? [5, 3, 7]

With that, we can either take 5+7 or 3. So, 5+7 ($12) is the answer.

Let's add a fourth: [5, 3, 7, 10]

Now, there are three choices:

1. 5+7 = $12
2. 5+10 = $15
3. 3+10 = $10

Do we skip one value or two? Here, the answer is to skip two (3 and 7). The next question is: how do you do this programmatically for a list of size n?

My Solution

function calculateMaxPath(exhibits) {
    var loot = 0,
        paths = [];

    // For each of the exhibits
    for (var i in exhibits) {
        // Determine the value from 2 and 3 spots back
        var back2 = (i-2 < 0) ? 0 : paths[i-2],
            back3 = (i-3 < 0) ? 0 : paths[i-3];

        // Best path = current value + better of 2 vs 3 back
        var maxPath = exhibits[i] + Math.max(back2, back3);

        // Add the best path to the list of paths
        paths.push(maxPath);

        // Determine if it's the best path seen so far
        loot = Math.max(loot, maxPath);
    }

    // Return maximum loot
    return loot;

}

// Unit Tests
console.assert(calculateMaxPath([]) == 0);
console.assert(calculateMaxPath([5]) == 5);
console.assert(calculateMaxPath([5,3]) == 5);
console.assert(calculateMaxPath([5,3,7]) == 12);
console.assert(calculateMaxPath([5,3,7,10]) == 15);
console.assert(calculateMaxPath([14,11,23,7,27,22]) == 64);

qPoll

qPoll is a mash-up of modern web technologies. Here are the main ingredients:

• Electron: a framework for creating native, desktop applications using open web technologies (HTML, CSS, and JavaScript). It was made by the folks at GitHub and serves as the engine behind their hackable text editor, Atom.
• AJAX: to communicate between Electron and Node.js. AJAX is responsible for posting poll questions to the server. To help, I used jQuery.
• Socket.io: I wanted to show the poll results in real-time. To do that, the server would need to alert each client every time a new vote has been casted. WebSockets makes that possible.
• Node.js: serves as the backend for qPoll. It receives questions, sends them to clients, processes votes, and broadcasts the results.

This is a screenshot of the Electon app:

The top field allows you to enter a question. The fields that follow are the answers. You can add additional answers by clicking on the "+" button. To pose the question to your audience, click the "play" button.

And here's a look at the browser-based client:

The question and answers are populated as soon as the server receives them. Everything is done in real-time using WebSockets, so the client never needs to be refreshed.

To alternate the answer colors, I used an array, for loop, and the modulo operator:

var colors = ["green", "blue", "orange"];

// This will log "green", "blue", "orange", "green", "blue"
[1, 2, 3, 4, 5].forEach(function(answer, key) {
    console.log(colors[key % colors.length]);
});

Hello World

This site is powered by Jekyll and Poole.

Jekyll generates static websites from raw text. It’s written in Ruby and also drives GitHub Pages. @mdo designed and developed Poole, a butler for Jekyll that helps you get started.

Thank you to both!