Brian Grinstead

Given a parent rectangle and a collection of children rectangles on a 2D plane, how do you find a collection of non-overlapping rectangles that cover the inverse of the original set?

For instance, given the container rectangle along with the set [A, B] -> we want an output similar to [1, 2, 3, 4, 5].

         +----------------------------------------------------------------+
         |                                                                |
         |                                                                |
         |       +------------------+        +--------------------+       |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |       |        A         |        |        B           |       |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |       +------------------+        +--------------------+       |
         |                                                                |
         |                                                                |
         |                                                                |
         |                                                                |
         |                                                                |
         +----------------------------------------------------------------+


         +----------------------------------------------------------------+
         |                                                                |
         |                               1                                |
         +-------+------------------+--------+--------------------+-------+
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |   2   |                  |   3    |                    |       |
         |       |                  |        |                    |   4   |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         +-------+------------------+--------+--------------------+-------+
         |                                                                |
         |                                                                |
         |                              5                                 |
         |                                                                |
         |                                                                |
         +----------------------------------------------------------------+

Solution

Enter the inverse-intersection JavaScript project. It is a kind of micro library. No dependancies, just the math required to solve this problem!

You can grab the JavaScript file from Github.

At Foliotek, we have a lot of components we have built (and are in the process of building) for our various projects.

We are open sourcing some of these, and the first one is the AjaxQ jQuery Plugin. The purpose of this plugin is for managing sequential ajax requests.

It is designed to follow the $.ajax, $.get, and $.post interfaces and return values, only taking one extra parameter (the queue name). Here is a brief sample of the functionality:

$.ajaxq ("MyQueue", {
        url: 'http://jsfiddle.net/echo/jsonp/',
        type: 'post',
        dataType: "jsonp"
});
 
$.postq ("MyQueue", 'path/to/your/resource', onsuccess);
 
$.getq ("MyQueue", 'path/to/another/resource', onsuccess);

In this case, each request would only run once the other finished. See the AjaxQ demo to see it in action with multiple queues.

All the source code is available on Github, available under the MIT License. I hope to have more projects to report on in the future!

A few months ago, I posted about my developer tools concept colorpicker implementation. After that, I was contacted on the devtools mailing list and got some initial feedback. I pulled the jQuery dependency out of a branch on my JavaScript colorpicker using jsfiddle plus the mailing list. From there, I submitted a patch to the WebKit project.

From there, I opened a development case, entitled Web Inspector: Add colorpicker functionality to color swatches in Styles Sidebar. 50+ comments and 10 patches later, the case landed in WebKit. This is really exciting, since it will improve the development experience for Chrome and Safari users. Thanks to all the WebKit developers who helped me along the way with getting the code and UI ready for committing (I needed all the help I could get).

I am planning on sharing more of the technical details and hurdles I had as a first time contributor to the WebKit project in a coming post.

I decided to make an HSV colorpicker for the js1k contest. Here is a demo of the colorpicker and the source code.

Getting Started

I found a great start for actually drawing the wheel at the canvas color wheel post from Ariya Hidayat. I modified that code and got the wheel on the screen in no time.

Also, I had written TinyColor, a JavaScript color parsing library, so the HSV to RGB conversion function was pretty easy to grab (though I did have to make some changes to shrink the function size, more on that later). This let me remove some of the code from the color wheel function that I also needed on mouse move events.

I tied together some buggybasic bounds checking on the circle for mousemove events and printed out the current RGB using the conversion function above, and I had a cool little demo – weighing in at around 2K.

Smaller… Much Smaller

So I needed to drop about half the weight of the project. I learned that you could use ~~x instead of Math.floor(x) provided that the number is positive, so that helped. And there are always tricks about passing in assignments to functions to save a semicolon, storing references to global objects, commonly used math functions, and so on. But it was not quite the time for dropping individual bytes, I needed some big changes.

First, DOM and CSS rules take up a lot of bytes. b.appendChild(d.createElement("input")) is just huge and cannot really be minified beyond what is there. My takeaway was that I needed less DOM elements. I was originally using a container div with a width equal to that of the canvas (400px) and had a little ‘spot’ div that was absolutely positioned based on the current X and current Y value. All of these lines are problems when are you trying to squeeze an ‘application’ into 1k:

container = b.appendChild(doc.createElement("div"));
spot = b.appendChild(doc.createElement("b"));
container.style.cssText='position:absolute;width:400px;margin:auto'
spot.style.cssText='position:relative;height:5px;width:5px'

By moving this functionality into the canvas drawing method (with fillRect, and later fillText), I dropped a couple hundred more bytes.

Next, the hsvToRgb conversion function got an overhaul (it went from 291 bytes to 205, and 33 of those are for the CSS color rule needed for the RGB background color). Takeaway here is that case statements have a lot of control characters, and this particular one was nicely shrunk down using 3 arrays.

 
// 291 bytes <a href='http://closure-compiler.appspot.com/code/jsc1c76aaeacd4bc7fcf6686709cc174fc3/default.js'>minified</a>.
function hsvToRgbBIG(h, s, v) {
    var r, g, b;
 
    var i = math.floor(h * 6);
    var f = h * 6 - i;
    var p = v * (1 - s);
    var q = v * (1 - f * s);
    var t = v * (1 - (1 - f) * s);
 
    switch(i % 6) {
        case 0: r = v, g = t, b = p; break;
        case 1: r = q, g = v, b = p; break;
        case 2: r = p, g = v, b = t; break;
        case 3: r = p, g = q, b = v; break;
        case 4: r = t, g = p, b = v; break;
        case 5: r = v, g = p, b = q; break;
    }
 
    return { r: r * 255, g: g * 255, b: b * 255 };
}
 
// 205 bytes <a href='http://closure-compiler.appspot.com/code/jsc1c76aaeacd4bc7fcf6686709cc174fc3/default.js'>minified</a>.
// Also includes the css color rule as the final return value.
function hsvToRgbSMALL(h, s, v) {
    h*=6;
    var i = ~~h,
        f = h - i,
        p = v * (1 - s),
        q = v * (1 - f * s),
        t = v * (1 - (1 - f) * s),
        mod = i % 6,
        r = [v, q, p, p, t, v][mod] * two55,
        g = [t, v, v, q, p, p][mod] * two55,
        b = [p, p, t, v, v, q][mod] * two55;
 
    return [r, g, b, "rgb("+ ~~r + "," + ~~g + "," + ~~b + ")"];
}

From there, it was mostly reorganizing and adding hacks to make the code smaller. A tip for anyone trying to do this: I wrap all the code into a executing function, so that minifiers will use one letter names for variables (rather than assuming they are global). Then I run the code through Closure Compiler online frequently when making changes to see how effective changes are. Don’t forget to remove the wrapper from the minified file, though!

(function() {
    var oneHundred = 100;
    // All code goes inside here
})();

1k

I finally got to 1024 bytes! It was a fun project, I will probably to it again when another js1k comes along.