Posts Tagged Javascript

JavaScript Sudoku Solver

In Computing science artificial intelligence terms, the game of Sudoku is a constraint satisfaction problem. Constraint satisfaction problems are nice in the regard that there are some very nice heuristics that lead to an easy algorithm to solve them. On the other hand, constraint satisfaction problems with a large problem domain may take an inordinate amount of time to solve.

Sudoku consists of a 9×9 grid, with each grid cell having a possible 9 different values. If we ignore all the constraints, this gives a possible 9^81 boards (1.9662705 × 10^77). Say we can check one-hundred trillion boards a second (100,000,000,000), it would still take ((9^81)/100000000000)/(31556926) = 6.23 × 10^58 years to iterate over all possible combinations! Clearly randomly generating boards and checking if the constraints are fulfilled is not a realistic solution.
Read the rest of this entry »

, , ,

1 Comment

Inject Dojo Bookmark

Sometimes it can be handy to inject Dojo into pages that would not otherwise have it. I’ve used this so I can use dojo.query() on a page to select DOM objects while testing a parser in a different language.

Use drag this link into your bookmarks and have Dojo at your fingertips no matter where your browser takes you:
Inject Dojo v.1.3.2

, ,

No Comments

Cookie Injection Using Greasemonkey

There are several Firefox plugins which allow the user to manipulate their browser cookies. However, most of these plugins force the user to manipulate cookies individually. This can become tedious if the user is simply “importing” cookies from, say, a wireshark dump.

The CookieInjector userscript simplifies this process, by allowing the user to copy-paste the cookie portion of the dump and have the cookies from the dump automatically created on the currently viewed web page.

Updated Cookie Injector Script available on
userscripts-mirror.org

To Use The Script:

Fire up Wireshark, formally Ethereal, if you don’t have Wireshark you can grab it from: http://www.wireshark.org/. Start listening for traffic on the same interface you use to access the internet. To cut down on extra packets, enter tcp as a capture filter. TCP is a transport layer protocol featuring reliable transport, congestion control and connection oriented transfers. Since HTTP uses connections between client and server and therefore the TCP protocol, is is safe to filter out all non-TCP packets. To further filter the packets that Wireshark is displaying enter http.cookie in the filter field. This will filter out all packets which are not using the HTTP application layer protocol and all HTTP packets which do not contain cookies.

Next go to a website that uses cookies. Most websites which support user logins or shopping carts use cookies for these purposes. Make sure that the website that you visit does not encrypt the entire session (such as a banking website), otherwise the packets will be encrypted and not viewable in wireshark. After capturing a couple packets which contain cookies scroll down to the Hypertext Transfer Protocol portion of the packet preview, expand it, and scroll down to the cookie line. Right click on the line, and select copy->Bytes (Printable Text Only). This will copy the human-readable portion of the packet which represents the Cookies associated with this website.

If you haven’t already, install Greasemonkey, and the CookieInjector userscript. Clear your private data, ensuring that the Cookies and Authenticated Sessions options are selected. This will delete all your cookies, so we can see the script in action. Press alt-c to view the CookieInjector dialogue, paste the cookie string from wireshark into the text box and click OK.

Congratulations! Your cookies have now been restored!

How The Script Works:

After the page has loaded the CookieInjector class is initialized. This involves setting up the dialogue and binding a function to the onkeydown event. When the user presses the ALT-C key combination, the CookieInjector keyPress function is called, which checks to see if the correct key combination has been triggered. If it is valid, the dialogue’s display style is changed, making it visible in the middle of the page.

After the user enters the cookie that was copied from Wireshark, the script does a quick cleanup of the string, and then adds the cookies to the browsing session.

Note that the cookie’s host will be the domain that is loaded in the browser when the cookie is injected. The root path will be used for the root of the cookie to ensure that the cookie is persistent across the entire domain. Finally, the cookie is a session cookie, which means that the cookie will expire when the browser is closed.

Security Implications Of Cookies

The use of cookies for identification and authentication presents a dangerous security risk for un-encrypted connections. Most websites (such as Hotmail, Facebook and Gmail), only encrypt the username and password when initially authenticating the user and all traffic following the initial handshake is un-encrypted. As a result, the cookie information is readable by anyone who is listening with appropriate software, and malicious users can steal the cookies of other users on the network, possibly gaining access to their accounts. Un-encrypted or weakly encrypted wireless connections (those which do not use WPA or stronger encryption schemes) are especially susceptible to cookie stealing. This is because anyone with a wireless card can simply listen to all network traffic as it is broadcast through the air, intercepting cookies, images, web pages and any other traffic which may or not be intended for them. Intercepting traffic on a switched network (most LANs) is more complex, but can be accomplished using ARP Poisoning or software such as Ettercap

The take-home lesson is to use encrypted connections, like https, whenever privacy is important. Always remember that if the connection is not encrypted anyone could be listening in.

 

Edit: I have released a new version of the script that should fix the problems with the window appearing in WYSIWYG windows + post data.
Edit: Several people have been reporting the cookie injector window appearing in Gmail emails. All WYSIWYG editors may be affected depending on their implementation. If you experience problems with the cookie injector window showing up where it shouldn’t, edit the userscript to exclude the problem site.

For example, I have updated the userscript to ignore gmail / mail.google.com domains with the following in the header:

// @exclude		   https?://gmail.com/*
// @exclude		   https?://mail.google.com/</del>

Please make the change yourself, or download the new version of the script to suppress its operation on Gmail pages.

External Links:

Greasemonkey: https://addons.mozilla.org/en-US/firefox/addon/748
HTTP Protocol: http://en.wikipedia.org/wiki/HTTP
TCP Protocol: http://en.wikipedia.org/wiki/TCP
Cookies: http://en.wikipedia.org/wiki/HTTP_cookie
Wireshark: http://www.wireshark.org/
Ettercap: http://ettercap.sourceforge.net/
ARP Poisoning: http://en.wikipedia.org/wiki/ARP_spoofing
Ethereal: http://www.ethereal.com/

, , , , , , , ,

47 Comments

Dojo: Meet Google Book Search

For those of you who read about the re-launching of the SFU Bookswap website (http://sfubookswap.com), you may remember that one of the new features was the integration of the Google Books database.
In this entry I am going to talk about how I integrated the Google Book Search functionality into my existing Dojo framework.

First things first: you need to sign up for a Google AJAX Search API key. You can get your key, as well as a description of the API and documentation from Google here: http://code.google.com/apis/ajaxsearch/signup.html.

Google offers a Search container, which allows the integration of several search sources, including the web, images, blogs, news items and books. I only wanted the Book source so I chose to take the simple route and not use the container class. Instead I used the GbookSearch object directly, which allows me to access the data more easily as well as utilize only the desired functionality.

The very first step in integrating the Google Books search results is including the Google class on your page:

<script type="text/javascript" src="http://www.google.com/jsapi?key=<yourapikey>"></script>

Next, we need to ensure that the Google Search namespace is loaded so we have access to the searching functions. This is as simple as including script tags with the following

google.load("search","1");

Because objects are swell, and will allow us to instantiate multiple searches on the same page, we are going to encapsulate the Google Book Search object in a wrapper object which exposes only the functionality we desire.

dojo.declare("GoogleBookSearch", null, {
    constructor: function(){
		this._bookSearch = new GbookSearch();
		this._bookSearch.setNoHtmlGeneration();
		dojo.connect(GbookSearch,"RawCompletion",this,"resultCallback");
    },
    query: function(q){
        this._bookSearch.execute(q);
    },
    resultCallback: function(){
    	console.debug("Got Data Back, Lets Take A look:");
    	console.dir(this._bookSearch.results);
    	for(var x=0; x<this._bookSearch.results.length; x++){
    		document.body.appendChild(this._bookSearch.results[x].html);
    	}
    },
    goToPage: function(p){
    	this._bookSearch.gotoPage(p);
    },
    getNextPage: function(){
    	this._bookSearch.gotoPage(this._bookSearch.cursor.currentPageIndex+1);
    }
});

The first line of this class (the dojo.declare) creates a new GoogleBookSearch object, which does not inherit from any object (the null parameter), which has several functions and attributes.

The Constructor Function:

The constructor function sets up the search object by creating a new GbookSearch instance. To gain a slight speed improvement, we disable HTML generation, which will prevent the GbookSearch class from downloading images and generating Google’s HTML representation of the search results. Finally we connect the “RawCompletion” event that is fired by the GbookSearch object to a callback function in the local object. After every search query is completed, this event is fired by the global object.

The rest of the functions are fairly self explanatory: the query function accepts one argument, which is the query from the user. The query can be an ISBN, author, title or any other combination of book properties that Google stores in their book database. The resultCallback function processes the data after the GbookSearch class has received search results from the server. Notice that they do not come in the form as an argument to the function but, rather, are accessed by iterating through the _bookSearch.results array. The gotoPage and getNextPage move to the next page of search results (as only 4 are returned by default). No other code is needed, as after getting the results for the next page, the “RawCompletion” event is fired once again.

To use your shiny new class, simply instantiate it after the page has loaded. So, for example:

dojo.addOnLoad(function(){
    myBookSearch = new GoogleBookSearch();
});

Make sure you don’t put a var in front of bookSearch, otherwise the object will have only local visibility, and be removed after the function has executed.

Tips and Tricks:

Modifying the callback function.

In my case, I wanted to have a default callback function that is executed when the search results are returned. However, I wanted separate instances of the GoogleBookSearch object to handle search results differently. To do this, we want to “overload” the resultCallback function using dojo’s hitch functionality.

dojo.addOnLoad(function(){
    myBookSearch = new GoogleBookSearch();
    myBookSearch.resultCallback = dojo.hitch(this,function(){
        if( myBookSearch._bookSearch.results.length>0){
           alert('Showing '+myBookSearch ._bookSearch.results.length+' of '+ myBookSearch._bookSearch.cursor.estimatedResultCount +' Results');
        }
    });
});

The dojo.hitch function accepts two arguments, a function or method name as the second argument, and the scope in which the method executes as the first argument. It is crucial that this scope is set correctly as the default behaviour is to execute in the scope of the GoogleBookSearch object which may be ok if only global or Google BookSearch attributes and functions are used, but is insufficient if we are wrapping the GoogleBookSearch object inside another object and want the callback to be defined as a function in the outer object.

Cleaning Up The Results

When returning the results, if any of the attributes of the book were a keyword in the search, for example, the author field contained a keyword, then the keyword in the author field would be enclosed in bold tags. In my application I am importing data into a database so I want it to be as clean as possible. My solution is using a regular expression to remove all HTML tags. For example

myBookSearch._bookSearch.results[0].authors.replace(/(<([^>]+)>)/ig,"")

Extracting the image of the book cover

You may notice that the book covers are dynamically generated for each query and expire after a short time. My workaround for this is to use regular expressions to parse out the book ID and then use the same (permanent) address that Google does when displaying the book covers on the book details page.
This can be accomplished as follows:

var imgUrl = "http://books.google.com/books?id="+/.*id=([^&]*)/g.exec(myBookSearch._bookSearch.results[0].tbUrl)[1]+"&printsec=frontcover&img=1&zoom=1"

The regular expression extracts the book ID from the thumbnail URL and combines it with the persistent book cover URL

There are a bunch of other attributes stored by the GbookSearch object. Look in the Google API to see a bunch of them or, alternatively, use Firebug to snoop the object after results have been returned.

Happy Coding!

External Links
Google AJAX Search: http://code.google.com/apis/ajaxsearch/
Google AJAX Search API: http://code.google.com/apis/ajaxsearch/documentation/reference.html
Firebug: www.getfirebug.com/

, , ,

2 Comments

Greasemonkey And Dojo Integration

Dojo (http://dojotoolkit.org/) is a wonderful javascript toolkit which just reached version 1.0 at the beginning of November. I have been watching and developing with Dojo for a couple years now and I can’t tell you how excited I am to have passed the version 1 milestone

Greasemonkey (http://www.greasespot.net/) is a handy Firefox extension which allows the injection of javascript (called userscripts) into the webpage currently being viewed. This allows for the customization of the look and feel of a website: improving the user interface or adding additional functionality.

In this example, we are going to use greasemonkey and Dojo to display a dialog widget on an arbitrary website.

To simplify the deployment of a userscript we are going to use the AOL Content Distribution Network to pull in a crossdomain build of the dojo toolkit. This is helpful to us as developers as we don’t have to build or maintain Dojo ourselves and is useful to the user as they get an optimized download from a distributed CDN.

First thing’s first: If you haven’t already, download and install the Greasemonkey extension, and create a new user script.

To access the power of Dojo, we must include the Dojo crossdomain build on the page we are visiting. To do this, we will dynamically create a new script element containing the address of the build and append it to the document head:

var script = document.createElement('script');
script.src="http://o.aolcdn.com/dojo/1.0.0/dojo/dojo.xd.js";
document.getElementsByTagName('head')[0].appendChild(script);

Next, since we are going to need a Dijit Dialog object, we will need to also include the Tundra Theme CSS file by appending it to the head object:

var link = document.createElement('link');
link.rel = "stylesheet";
link.type= "text/css";
link.href="http://o.aolcdn.com/dojo/1.0.0/dijit/themes/tundra/tundra.css";
document.getElementsByTagName('head')[0].appendChild(link);

Great! Now we have the Dojo javascript file included on the page as well as the Dijit Tundra theme setup and ready to use. Next, we will actually include the Dojo dependencies we need and display our Dialog!

To ensure that the Dojo Javascript file and the Tundra Stylesheet have been downloaded and parsed we must include the rest of the code in a function that will run when the window fires the “load” event To do this, we will add an event listener to the window object with the function as an argument:

window.addEventListener('load', function(event) {
var dojo =  unsafeWindow["dojo"];
dojo.require("dijit.Dialog");

Also notice that we have created a local variable called Dojo which is a refrence to the unsafeWindow dojo object. Greasemonkey runs all userscripts in a sandbox which provides enhanced security as well as ensures that they do not conflict with any preexisting scripts already on the page. Because, by default, Dojo is instantiated with a visibility relative to the window object it is not visible to our script. By creating a reference to it in a local variable, this allows us to access its functionality.

Also important is the dojo.require statement. This will pull in the dijit.Dialog object which we will be instantiating later on in our script. To ensure that all the dependences have been loaded before we try to create a dialog, we must wait until dojo knows that the external resource has been loaded.

dojo.addOnLoad(function(){
var dijit = unsafeWindow["dijit"];
dojo.addClass(document.getElementsByTagName('body')[0], "tundra");
 
var pane = document.createElement('div');
pane.id = "floatingPane";
pane.innerHTML="Dojo Lives... In GreaseMonkey!";
document.getElementsByTagName('body')[0].appendChild(pane);
 
dialog = new dijit.Dialog({
title: "Dojo Integration Test"
},pane);
dialog.show();
});
}, 'false');

A lot of stuff happens in the above code snippit:
First we grab a local reference to the global dijit object, next we assign a “tundra” class to the body tag, which will allow us to have the correct theme for our Dialog. We create a div node which will eventually become our Dialog, populate it with appropriate attributes and append it to the document’s body tag. Finally we create a new dialog object with a catchy title and the previously created div node as the contents, and display it on screen. Lastly, we close the window.addEventListener object that we created in the previous step.

Downloaded the complete userscript here:
Dojo Integration Userscript This script has been updated and is available here

Special Thanks to Shane Sullivan’s Dojo Debug Script which shows how to access the Dojo object from the Greasemonkey sandbox.

, ,

8 Comments