:(

Not found.

Setting up Ubuntu 12.04 Virtual Machine for Firefox OS Build

Ultimately, I want to try installing FirefoxOS on my old Xperia X8 phone and give it a new lease of life. For now, this is just a few words on my experience building FirefoxOS for emulator. This was all done on Windows 8.1 with Ubuntu 12.04 64bit virtual machine running in Virtual Box 4.3.6. Even though the guide says otherwise, it is possible to run the emulator inside Virtual Box.

Right at the start I had issues with even running Ubuntu installation. Virtual Box is offering, when configuring the type of operating system, Ubuntu 64bit distribution, however, the option did not show up initially. With plain Ubuntu selected it just doesn’t work. The issue was that Hyper-V client was installed on my machine and prevented Virtual Box from using virtualization support (AMD-V or Intel VT-x) even though it had been enabled in BIOS. The solution was to uninstall Hyper-V, then Ubuntu 64bit option appeard in the drop down list (along with other 64bit Linux distributions).

With that out of the way I created a Ubuntu 64bit virtual machine with 4GB of RAM and HDD of 40GB. I tried initially with less memory and HDD space but the system and the build take over 30GB so I’d say 40GB is a must.

The whole process is quite … well, I’m tempted to say straight forward. It’s not so bad, once you follow the script, which I failed to do twice. Eventually I succeeded. Here are the steps/commands.

Install Ubuntu 12.04, then Virtual Box Guest Addons (addons are optional but just makes life so much easier … until it comes to running the emulator).

Next are the commands that need to be run.

sudo apt-get update
sudo apt-get install autoconf2.13 bison bzip2 ccache curl flex gawk gcc g++ g++-multilib git ia32-libs lib32ncurses5-dev lib32z1-dev libgl1-mesa-dev libx11-dev make zip

sudo apt-get install libgl1-mesa-dev libglapi-mesa:i386 libgl1-mesa-glx:i386

sudo ln -s /usr/lib/i386-linux-gnu/libX11.so.6 /usr/lib/i386-linux-gnu/libX11.so
sudo ln -s /usr/lib/i386-linux-gnu/mesa/libGL.so.1 /usr/lib/i386-linux-gnu/libGL.so

sudo apt-get install binutils-gold

ccache --max-size 3GB

git clone git://github.com/mozilla-b2g/B2G.git
cd B2G

./config.sh emulator

./build.sh

The first two lines are straight from the prerequsites guide (Requirements for Linux). The third, fourth and fifth are to overcome emulator build issues. The next one is for fixing “…is referenced by DSO” error. And the rest is cach configuration, cloning and configuring repository and finally building. Emulator build issue will come up and DSO error will come up, did I mention I failed to follow the script a couple of times? Btw, configuration is actually getting the necessary projects to be built, B2G project is just build system. It takes a while to download everything – talking about an hour or two on a speedy connection. Build takes a while too, an hour or two … well, I don’t remember to be honest, I was doing other things while this was happening :$

Anyway, the last remaining thing is making emulator run. It is as simple as: ./run-emulator.sh :) … well, after a few other tweaks. 3D acceleration needs to be enabled in Virtual Box for this virtual machine. That’s simple. The issue I spent some time figuring out was how to make emulator running properly because it was showing only blank screen due to OpenGL error. Since my X server got corrupt at one stage – booted into a blank screen, I uninstalled Virtual Box Guest Addins, and that made emulator start working. It’s quite a pain in the back to use virtual machine without the guest addon, so the trick is to install it but disable vboxvideo module. Easier said than done. I tried few things and black listing doesn’t work, rmmod didn’t work either etc. I’m not that good with Linux, but the solution I came up with didn’t need any sophistication whatsoever.

The fix is to remove or rename vboxvideo.ko so it is not loaded on startup. Ha :) Didn’t I say no sophistication! I found vboxvideo.ko in : /lib/modules/3.8.0-35-generic/misc and renamed it with sudo mv videobox.ko _videobox.ko (or you could use /lib/modules/`uname -a`/misc/ to get to the module)

Anyway, after rebooting the virtual machine here’s the result:

Using Bing Maps Ajax Control

In the previous post I added some server side processing to use Bing Maps REST services. This time I’ll use AJAX control to show the addresses on the map and show some basic information in info box. First thing to do is show the map. That turns out to be easy:

map = new Microsoft.Maps.Map(document.getElementById('myMap'), {credentials: 'your-key-here', mapTypeId: Microsoft.Maps.MapTypeId.road});

Very similar to the basic example, I just added map type. Later on I’ll zoom in on  addresses after search, initially the whole world is shown. One thing to note is credentials – Maps Key needs to go there. I think it’s totally stupid to have it in plain text and use that for billing someone. Anyway, I’m not going to put mine on GitHub.

The next is to show pins. This is why coordinates are needed – to be able to put pins on the map. This makes it very easy to show the pin after receiving coordinates from backend:

$.get("/coordinates", $("form").serialize(),
	function(data){
		$.each(data, function(i, item){
			if(item[0] != "error"){
				var pushpin = new Microsoft.Maps.Pushpin(new Microsoft.Maps.Location(item[2][0], item[2][1]), null);
				map.entities.push(pushpin);
			}
		});
}, "json");

To center the map I just used the first location and zoomed in to show more restricted area:

if(i == 0){
    map.setView({ zoom: 8, center: new Microsoft.Maps.Location(item[2][0], item[2][1]) })
}

That was pretty easy, let me just quickly add info box and I’ll show how the code looks like after all has been put together. Infobox should be shown upon clicking on a pushpin, so event handler is required for that.

infoBox = new Microsoft.Maps.Infobox(map.getCenter(), {width: 200, height: 100, visible: false});
map.entities.push(infoBox);
//to show it
infoBox.setLocation(new Microsoft.Maps.Location(lat, lon));
infoBox.setOptions({visible: true});

I opted for keeping only one global instance of infobox, initialized it and made it invisible. Once it is in the list of entities depending on which push pin is clicked location needs to be set and then its visibility set. Oh, yes, to attach event, that’s a bit old-style, can’t use jQuery unfortunately.

pushpin.myLocation = location; //location details came from server
pushpin.myHandlerId = Microsoft.Maps.Events.addHandler(pushpin, "click", showInfoBox);

function showInfoBox(e){
	infoBox.setLocation(e.target.getLocation()); //e.target is the pushpin
	var location = e.target.myLocation;
	infoBox.setOptions({ visible: true, title: location.addr, description: "(" + location.lat + ", " + location.lon + ")"}); //setting title and description sent from server
}

I need this handler Id in order to detach event later on. I’ve also added location (coming from server) to the pushpin object, so in handler I can access it easily. Here’s the full Javascript code:

var map = null;
var infoBox = null;
var bing = Microsoft.Maps; //alias

 $(function() {
    map = new bing.Map($('#myMap').get(0), {credentials: 'your-key-here', mapTypeId: bing.MapTypeId.road});
	infoBox = new bing.Infobox(map.getCenter(), {width: 200, height: 100, visible: false});
	
    $( "input[type=submit]" )
    .button()
    .click(function( event ) {
        event.preventDefault();
        //jquery ajax call
        $.get("/coordinates", $("form").serialize(),
            function(data){
                $("div#result").empty();
                var locations = [];
                $.each(data, function(i, item){
                    if(item[0] == "error"){
                        $("div#result").append('<p><em>'+ item[1] +'</em></p>');
                    }else{
                        $("div#result").append($('<p></p>').text(item[1] + ': ' + item[2][0] + ', ' + item[2][1]));
                        locations.push( {lat: item[2][0], lon: item[2][1], addr: item[1]});
                    }
                });
                updateMap(locations);
        }, "json");
    });
});

function updateMap(locations)
{
    clearMap();
	map.entities.push(infoBox);

    $.each(locations, function(i, l){
       var pushpin = new bing.Pushpin(new bing.Location(l.lat, l.lon), null);
	   pushpin.myLocation = l;
       map.entities.push(pushpin);
	   pushpin.myHandlerId = bing.Events.addHandler(pushpin, "click", showInfoBox);
	   if(i == 0){
	       map.setView({ zoom: 8, center: new bing.Location(l.lat, l.lon) })
	   }
    });
}

function clearMap(){
    while(map.entities.getLength()){
		var entity = map.entities.pop();
		if(entity.myHandlerId){
			bing.Events.removeHandler(entity.myHandlerId);
		}
	}
}

function showInfoBox(e){
	//var mapLocation = new bing.Location(location.lat, location.lon);
	infoBox.setLocation(e.target.getLocation());
	var location = e.target.myLocation;
	infoBox.setOptions({ visible: true, title: location.addr, description: "(" + location.lat + ", " + location.lon + ")"});
}

Or see the whole web.py template file on GitHub: index.html.

A few notes: I converted data coming from server to an object with lat, lon and addr fields, I’ve added an alias bing to save me some typing, also I’m detaching all click events when clearing map entities – there’s no guidance from Microsoft on this, the documentation is very sparse, so this might or might not help with garbage collection.
In the next post I’ll finally get to incorporate the TSP alghoritm, so ’till next time.

Adding Geocoding to Python TSP Application

OK, so far so good, lets improve on where we left off. Lets do geocoding with Bing Maps. Basically, I’ll just find coordinates for a given address. That would be enough as a next step, and following that I’ll add map control and pins in a short while (this is where I’ll need those coordinates). Ultimately I’d want to have distances between given points retrieved from Bing and calculate shortest route and show that on screen. I haven’t used Bing Maps before so I better go slowly on this.

To use Bing Maps I need maps developer account. Need to register with Microsoft account here: www.bingmapsportal.com I’ll be using REST services, so I’ll need keys as per Getting Started article. After a few retries I finally managed to get those keys. Recently the site is behaving better, originally when I tried doing this … well, lets say it was bit off putting experience.

I’ll try to find a location by address. Actually no, by query, it looks simpler. I’m sure finding location by address is better, but I’m not sure how I would want UI to look like yet, thus I’ll opt for the simpler one. Simplest URL to get coordinates should look something like this:

http://dev.virtualearth.net/REST/v1/Locations?query=url encoded address&maxResults=1&key=Bing Maps Key

Please note that maxResults=1, I’m just going to take the first result I get back. In a real application this would probably not be that simple. To translate the above to a proper URL, lets find, say, Blarney Castle, Cork, Ireland:

http://dev.virtualearth.net/REST/v1/Locations?query=Blarney%20Castle%2C%20Cork%2C%20Ireland&maxResults=1&key=Your Bing Maps Key

You’d need to replace that end part with your Bing Maps key to get some meaningful result. And the result is in JSON, it looks like this for the above query, just to know what to expect from Bing:

{
  "authenticationResultCode": "ValidCredentials",
  "brandLogoUri": "http:\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/dev.virtualearth.net\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/Branding\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/logo_powered_by.png",
  "copyright": "Copyright © 2013 Microsoft and its suppliers. All rights reserved. yada yada yada",
  "resourceSets": [
    {
      "estimatedTotal": 1,
      "resources": [
        {
          "__type": "Location:http:\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/schemas.microsoft.com\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/search\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/local\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/ws\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/rest\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\/v1",
          "bbox": [
            51.9411011,
            -8.5592403,
            51.9431,
            -8.5550003
          ],
          "name": "Castle Gardens, Cork, County Cork, Ireland",
          "point": {
            "type": "Point",
            "coordinates": [
              51.9419937,
              -8.5571699
            ]
          },
          "address": {
            "addressLine": "Castle Gardens",
            "adminDistrict": "County Cork",
            "countryRegion": "Ireland",
            "formattedAddress": "Castle Gardens, Cork, County Cork, Ireland",
            "locality": "Cork"
          },
          "confidence": "High",
          "entityType": "RoadBlock",
          "geocodePoints": [
            {
              "type": "Point",
              "coordinates": [
                51.9419937,
                -8.5571699
              ],
              "calculationMethod": "InterpolationOffset",
              "usageTypes": [
                "Display"
              ]
            },
            {
              "type": "Point",
              "coordinates": [
                51.9419937,
                -8.5571699
              ],
              "calculationMethod": "Interpolation",
              "usageTypes": [
                "Route"
              ]
            }
          ],
          "matchCodes": [
            "Good"
          ]
        }
      ]
    }
  ],
  "statusCode": 200,
  "statusDescription": "OK",
  "traceId": "b7609a7a76bc41e2a97fc0b8ef4511b1|LTSM001159|02.00.183.2300|LTSMSNVM001471, 7.76, LTSMSNVM001466"
}

That looks like a lot but luckily I don’t need all of that, for the time being I’ll use only coordinates. Lets get the data first, for that I’ll be using urllib and json library for parsing, well JSON.
To get coordinates it should be relatively simple, like this:

import json
import urllib
bingKey = 'your key goes here'
urlPrefix = 'http://dev.virtualearth.net/REST/v1/Locations?query='
urlSuffix = '&maxResults=1&key=' + bingKey

address = "Blarney Castle, Cork, Ireland"
url = urlPrefix + urllib.quote(address) + urlSuffix
jsonresult = json.loads(urllib.urlopen(url).read())
resource = jsonresult['resourceSets'][0]['resources'][0]
print (resource['address']['formattedAddress'], resource['point']['coordinates'])

I could’ve done this in one line but I deliberately split it for a bit better readability. The first thing to do is to prepare URL, then load it and parse as JSON, then some processing is required to get the actual coordinates.
The above is fine for running it from command line but I want to do this from screen. For this I want a text box where a list of addresses can be passed in (address per line), and I want to find coordinates for all of them. This should be simple with templates in web.py.
This is my initial index.html, and it will go into Templates folder – templates/index.html:

$def with (coordinates)
        <p>Please enter address per line to get their coordinates</p>
        <form method="get">
        <textarea id="addresses" name="addresses">
        </textarea>
        <input type="submit" value="submit" />
        </form>
        <div id="result">
        </div>
        <div id='myMap' style="position:relative; width:900px; height:600px;">$coordinates</div>

Nothing fancy, simple form to pass addresses as input and show coordinates (note $coordinates inside myMap div). On the server side some changes are required to configure templates folder and to change index to accept input and render coordinates as output. Here’s code.py with added templating handling:

# -*- coding: UTF-8 -*-
import web 

render = web.template.render('templates/')
 
urls = ( 
    '/', 'index' 
) 

import json
import urllib
import os
bingKey = os.getenv('BINGKEY') #need to configure this in azure, if running it from command line prior to doing python code.py run SET BINGKEY=your key
maxAddresses = 10 #one address per line, limit to 10
urlPrefix = 'http://dev.virtualearth.net/REST/v1/Locations?query='
urlSuffix = '&maxResults=1&key=' + bingKey

class index: 
    def GET(self):
        i = web.input(addresses = None)
        if i.addresses is None or len(i.addresses.strip()) == 0:
            return render.index("")
        else:
            print urllib.unquote_plus(i.addresses)
            return render.index(getCoordinates(i.addresses))

def getCoordinates(addresses):
    addressQueries = [urllib.quote(address.strip()) for address in addresses.splitlines() if address.strip() <> '']
    addressQueries = addressQueries[:maxAddresses]
    urls = [urlPrefix + query + urlSuffix for query in addressQueries]
    jsonresults = [json.loads(result) for result in [urllib.urlopen(url).read() for url in urls]]
    result = [processResult(j) for j in jsonresults]
    return json.dumps(result)
   
def processResult(data):
    if data['statusCode'] <> 200:
        return ("error", data.statusCode)
    #do some processing
    if len(data['resourceSets']) == 0:
        return ('error', 'no results')
    result = data['resourceSets'][0]
    if result['estimatedTotal'] <= 0:
        return ('error', 'no items')
    result = result['resources'][0]
    return ('success', result['address']['formattedAddress'], result['point']['coordinates'])

def wsgiHandler(): 
    return web.application(urls, globals(), autoreload=False).wsgifunc()
 
if __name__ == "__main__": 
    app = web.application(urls, globals()) 
    app.run()

The code is pretty similar to what we had before just does this for maximum 10 addresses with some more processing and error handling added. There are some things worth noting: I’ve configured environment variable (through Azure dashboard on configuration tab of my web site) BINGKEY so I don’t need to keep it in code; class Index is handling input from page and just calls getCoordinates to get an array of coordinates. that’ really it.
Lets finish off by adding Ajax support with jQuery.
With some simple changes I’ve added an ajax call to a new URL that will be provided – like a service, to get all coordinates and show that onto the screen, here’s the index.html:

<!doctype html>
<html>
<head>
<link rel="stylesheet" href="http://code.jquery.com/ui/1.10.3/themes/smoothness/jquery-ui.css" />
<script src="http://code.jquery.com/jquery-1.10.1.min.js"></script>
<script src="http://code.jquery.com/ui/1.10.3/jquery-ui.js"></script>

<script type="text/javascript">
var map = null;
 $$(function() {
    $$( "input[type=submit]" )
    .button()
    .click(function( event ) {
        event.preventDefault();
        //jquery ajax call
        $$.get("/coordinates", $$("form").serialize(),
            function(data){
                $$("div#result").empty();
                var locations = [];
                $$.each(data, function(i, item){
                    if(item[0] == "error"){
                        $$("div#result").append('<p><em>'+ item[1] +'</em></p>');
                    }else{
                        $$("div#result").append($$('<p></p>').text(item[1] + ': ' + item[2][0] + ', ' + item[2][1]));
                    }
                });
        }, "json");
    });
});
</script>

</head>
<body>
	<p>Please enter address per line to get their coordinates</p>
	<form method="get">
	<textarea id="addresses" name="addresses">
	</textarea>
	<input type="submit" value="submit" />
	</form>
	<div id="result">
	</div>
	<div id='myMap' style="position:relative; width:900px; height:600px;"></div>
</body>

That was realtively simple on the UI side and on the server side it requires some reorganization of things in code.py (most notably to add a new URL handler, which is now serving JSON result instead of Index):

# -*- coding: UTF-8 -*-
import web 

render = web.template.render('templates/')
 
urls = ( 
    '/', 'index',
    '/coordinates', 'coordinates'
) 

import json
import urllib
import os
bingKey = os.getenv('BINGKEY') #need to configure this in azure, if running it from command line prior to doing python code.py run SET BINGKEY=your key
maxAddresses = 10 #one address per line, limit to 10
urlPrefix = 'http://dev.virtualearth.net/REST/v1/Locations?query='
urlSuffix = '&maxResults=1&key=' + bingKey

class index: 
    def GET(self):
        return render.index()

class coordinates:
    def GET(self):
        print 'in'
        i = web.input(addresses = None)
        if i.addresses is None or len(i.addresses.strip()) == 0:
            return ""    
        else:
            print urllib.unquote_plus(i.addresses)
            return getCoordinates(i.addresses)

def getCoordinates(addresses):
    addressQueries = [urllib.quote(address.strip()) for address in addresses.splitlines() if address.strip() <> '']
    addressQueries = addressQueries[:maxAddresses]
    urls = [urlPrefix + query + urlSuffix for query in addressQueries]
    jsonresults = [json.loads(result) for result in [urllib.urlopen(url).read() for url in urls]]
    result = [processResult(j) for j in jsonresults]
    return json.dumps(result)
   
def processResult(data):
    if data['statusCode'] <> 200:
        return ("error", data.statusCode)
    #do some processing
    if len(data['resourceSets']) == 0:
        return ('error', 'no results')
    result = data['resourceSets'][0]
    if result['estimatedTotal'] <= 0:
        return ('error', 'no items')
    result = result['resources'][0]
    return ('success', result['address']['formattedAddress'], result['point']['coordinates'])

def wsgiHandler(): 
    return web.application(urls, globals(), autoreload=False).wsgifunc()
 
if __name__ == "__main__": 
    app = web.application(urls, globals()) 
    app.run()

As a side note, that $$ for jQuery is a bit of a bummer, should’ve probably put this into a separate Javascript file.
Anyway, I’ll leave it at this for now. I don’t have fully functional application yet, but I’m getting there. Next time I’ll be adding Bing Map onto the screen which should only require UI changes.

Setting up web.py – Python web application on Azure

It is very well to have a great algorithm but without making it available to be used by someone – making an application out of it – it is really just a nice exercise, not really a useful piece of software. So lets make a web application that would calculate us the shortest route.

I’ve chosen Azure for this, I suppose any other cloud PaaS provider supporting Python would do. The reason I chose Azure because I’m familiar with it and it will be free for a simple application like this. I think Microsoft did a good job on this, and I very rarely say words of praise for them. But enough chit chat and lets get to it.

Now, just for the record, I won’t go into every detail of how to setup all of this, just high level pointers.

The two main documents I followed are how to setup Python web sites and how to configure Django. Most of the stuff here comes from the latter one, the former I used as a starting point to have a better understanding of how things work.

So a quick overview of steps:

  1. Prerequisites – Azure account and GitHub account (or use local Git repository)
  1. Create web site on Azure
  1. Setup handler mapping with: * for extension, d:\Python27\python.exe for script processor path and D:\python27\scripts\wfastcgi.py for additional arguments
  1. Initialize GitHub (or local Git) repository
  1. Link up Azure with GitHub from either Quick Start page of the web site or Dashboard tab
  1. Install web.py
  1. Setup WSGI handler
  1. Create simple page to test if everything configured correctly

Setup Azure account if you haven’t done that already. Next, create a web application (quick create is good enough) and under configuration tab, at the very bottom – setup handler mapping with: * for extension, d:\Python27\python.exe for script processor path and D:\python27\scripts\wfastcgi.py for additional arguments. This is the basic configuration effectively making Python handle all page requests. There’s more details here for reference. I didn’t follow the steps exactly and I felt the tutorial is a bit all over the place, but everything needed for setting up Python web site is there. I named mine pythontsp. Simples.

A nice feature is integration with GitHub and I’ll avail of that fact. GitHub repository created at: https://github.com/mlalevic/pythontsp . Next thing is to link it up with Azure web site. Actually that’s straight forward and it’s a nice touch that it is there on the main (Quick Start) page for your site configuration. Follow link to setup deployment from source control, choose GitHub and link up your account with Azure. It’ll allow you to choose repository unless you have only one in which case it’ll just deploy that one immediately. (Btw, the option to setup deployment from source control is also there on the Dashboard tab of the site)

Next thing – which web framework to use? Microsoft has explanation how to setup Django(btw, there’s a step-by-step guide there how to setup your local git repository). I wante something more lightweight so I opted for Web.py. Of course, nothing on how to set this up on Azure exists yet, but should be simple, according to their doc . All that is required is to download gzip file (here’s version 0.37), unpack it somewhere and copy web folder into the root of your application. Finalize this by adding and committing to the GitHub repository.

So far so good, but we won’t see anything until WSGI handler is configured. That turns out to be no problem. First lets setup a test page as per webpy tutorial. Here’s the simplest code (code.py):

Before doing anything else, lets see if it runs locally (basically, just run: python code.py from your repository folder). Going to http://127.0.0.1:8080 should result in Hello world! output in browser window.

Unfortunately, this won’t work on Azure since WSGI handler is not configured yet, but that is simple (based on Django config). Firstly a method returning WSGI application is required, so code.py needs fixing by addition of:

def wsgiHandler():
    return web.application(urls, globals(), autoreload=False).wsgifunc()

Next, configuration needs to be added, basically to tell Azure where to find this WSGI handler. On configure tab of the web site under app settings – somewhere towards bottom of the page, PYTHONPATH and WSGI_HANDLER needs to be set. PYTHONPATH: D:\home\site\wwwroot since this is how Azure is pointing to our site and WSGI_HANDLER in our case is: code.wsgiHandler() since that’s how the method is called in code.py (don’t forget to save changes at the end).

Finally following http://pythontsp.azurewebsites.net/ yields Hello world! Everything works as it should and we’re ready to roll in about 15 minutes. Nice!

Traveling salesman problem – dynamic algorithm implementation in Python

I just wanted to share some code – dynamic programming algorithm for Traveling Salesman Problem (TSP) in Python. It’s simple and short and shows how Python is really as close as it gets to pseudo code since the code is nearly exact copy of pseudo code shown on one of the courses I did.

I finished couple of courses on coursera recently – algorithms 2 and linear optimization. These are very interesting courses with challenging homework. One problem was common between them – Travelling salesman problem (TSP).

TSP is an NP-hard problem meaning (informally) – there’s no polynomial time algorithm to solve them. Brute force algorithm has O(n!) complexity. Dynamic algorithm shown here has O(n22n) complexity. While not great it is still way better than doing it brute force. For comparison, 10! is 3,628,800 while 102210 = 102,400 an order of magnitude, or for n=11, 39,916,800 vs 247,808 – that’s already 2 orders of magnitude difference. If you’re not familiar or rusty with big-Oh notation, algorithms 1 has that covered in good detail.

Following code is nearly 1-to-1 copy of the pseudo code from algorithms 2 course. That’s only possible because it’s done in Python which is as close to actual programming in pseudo code as it gets. So without further ado here’s the algorithm in the whole 14 lines:

Python is awesome – eh! I’m sure I could have done this in 3-4 lines but then it would’ve been indecipherable. Well, it’s not much better as is if you’re not already familiar with the algorithm :) I will just briefly cover it, for more details go see the lectures from Algorithms 2 course.

The idea behind the algorithm is that we keep optimal sub-routes of certain length with their end-point. Then we add a point to the routes and figure out optimal sub-routes that are now one point longer then in the previous step. And we keep doing this until we get to the full route. (That was a bit simplistic but should suffice).

So with the above in mind, the main algorithm starts from line 7, before that it’s all setup and except line 5 not exactly necessary. Line 5 is initial distances – basically distances between point 0 and all others (optimal sub-routes of length 1). The data structure used is Dictionary where key is tuple of set of points in the optimal sub-route (frozen – so it could be used as a key) and the end point of the sub-route. The value of the dictionary is tuple of the length of the sub-route and list which is the sub-route i.e. {(set_of_points, end_point):(length, the_route)}

The loop variable m is the length of the sub-route – when m reaches cnt-1 we get the full route. On line 9 we iterate over all sets of length m (they have to include starting point – 0). And then in lines 10 and 11 basically we figure out what are the optimal sub-routes of length m.

Those 2 lines (10 and 11) are really the key to this algorithm, we’re using optimal sub-routes of length m-1 which we already have from the previous step and we want to figure out optimal sub-routes of length m ending with j.

The end of the algorithm is just to complete the route by going back to point 0 (line 13).

How good is it? Well, it’s crap … actually it depends on what you need and how quickly you need it.

Points Time (seconds)
5 0
6 0
7 0.001
8 0.002
9 0.007
10 0.019
11 0.045
12 0.114
13 0.291
14 0.705
15 1.72
16 4.152
17 9.995
18 23.454
19 55.11
20 121.961
21 278.42
22 628.242

Processing Time for Routes per number of Points

It can calculate paths with 14 or 15 points under a second but that’s about it in terms of nearly real-time. I managed to get results up to 22 points, but after that the performance went off the cliff mainly due to memory usage. It required ca. 6GB of memory and most of the time was spent on swapping at that stage, CPU was barely used. Basically, that’s the problem with dynamic programming approach, memory usage. Also, as it can be seen from the graph, even with lots of memory at hand things will go slow pretty quickly. It is safe to say that it certainly can’t do 100 point path, and likely not even 25 in some realistic time-frame and realistic memory size.

Anyway, this is interesting as a toy project and I intend on exploring how to make a real-world application out of this – having an algorithm that kicks ass is one thing, turning it into an application is a different thing altogether. Also, I’ll be trying this out in other languages – like, say F#. Lets see what happens.

Finally, if you haven’t heard of coursera I strongly recommend you check it out. It has hundreds of free online courses from prestigious universities. I would also recommend the two (ahem, three) above mentioned courses – Algorithms 1 and 2  and one of my favourites Linear optimization – they are superb quality, though but rewarding. Btw, be forewarned, these courses are addictive!

Fixing 69-C00D36BE error when playing video on Xbox 360

Recently I got D-Link DNS-320 ShareCenter and enabled UPnP on it so I could stream videos to my Xbox 360. I was getting the following error for some videos:

Unplayable Content

Can’t play this content because it may not be supported.

Status code: 69-C00D36BE

But it was working for other videos, and when I tried playing them from USB storage, it worked just fine. What I figured out is that videos in parent folder worked just fine and they all used the same encoding for both video and audio. I moved problematic videos so to parent folder and, guess what – they played just fine. I might investigate further why is this happening, but seems that path to the videos might’ve been to long or something.

Other error I’ve encountered is:

Uplayable Content

Can’t play this content because it contains audio or video with unsupported codec.

Status code: 80-C00DF242

Now, this is actually unsupported codecs. The videos in question were encoded with DivX 3 and 4 which are unsupported – only DivX 5 and later are supported on Xbox. I’ll see later on how to transcode them with ffmpeg and I’ll update here (should be easy).

Oh, yes, nearly forgot, when I was getting the latter error Xbox would say openning media or similar, in the case of the former it wasn’t even trying to open it.

Connecting to Network Printer Using a Particular User

Recently I got D-Link DNS-320 ShareCenter. Seems very good value for the money, and I already had 2 disks I wanted to put in a RAID. Anyway, there’s there was a bug in the firmware that would only allow printing as admin user (once custom users are added to the NAS printer cannot be accessed as a guest I suppose anymore but new useres don’t have permissions to access it).

That’s not a bother in Linux – it asks for permissions and you can print, but on Windows it just says the printer cannot be connected or something. So after some digging solution is to redirect the printer to a local port and manually add credentials under which to connect. So in general case this can be used:

net use LPT1 \\\\servername\\printername password /user:username

Or in case of DNS-320, since using admin user is required and the printer shows as lp it goes like this:

net use LPT1 \\\\you_nas_machine_name_or_ip\\lp put_admins_password_here /user:admin

After doing this from Harward and Sound -> Printers do Add Printer -> Add Local Printer -> LPT1, it’ll ask to choose drivers (TIP: pre-install them) and after that printer’s ready for printing.

For more info on net use command go here

Using JavaScript Modules – A Catch

I’m sure I saw somewhere an example how to use JavaScript modules in Firefox extensions and I just used that snippet. Anyway, I was recently caught by a conflict between New Tab Jumpstart extension and NetVideoHunter Basically they could not work together and whichever was loaded first was working properly, second loaded wasn’t.

It turns out that conflict was due to both extensions registering modules folder with the same alias modules. Both extensions would thus import their files with a similar uri: Components.utils.import(“resource://modules/some_module.js”);

The reason why this was failing is resource://modules will be registered for the first loaded extension so for one of the extensions some_module.js file will not be found in the registered location (or even worse it will be found but would be completely wrong).

It was simply fixed by changing registration in chrome.manifest to: resource jumpstart content/modules/ and replacing resource://modules to resource://jumpstart in all files.

Now when I look at it it’s completely logical but you do it once, don’t think about it at the time and you forget about it but it comes back to bite you later. All in all, if you plan on using modules in your extension do not register your modules folder with modules alias or similar, use your extension’s alias.

Experimental HexWax expandIO-USB Library on Git

I have added experimental library for HexWax expandIO-USB to GitHub . It should work fine for official evaluation board as well as it works for mine custom made one. The library is still in early stage so some significant changes are to be expected to both code and code structure.

Read only repository is here: git://github.com/mlalevic/HexWax-expandIO-Python-Library.git

Nearly all commands from the firmware are covered, and I have added two examples – one single threaded and one multi-threaded – the same example – blinking LEDs.

See how simple it is:

All commands are created like SetBit(“TRISC”, 6, 0), method pack() is used to get byte array representation for sending to device. Unpacking is done by a corresponding unpack class – like SetBitUnpack, and it unpacks input packet into member attributes.

Here’s multi-threaded version which is even simpler:

UsbBackgroundRead spawns a thread to read data from USB device in background. This is useful if the device can have external events – interrupts.

Anyway, got to do some more documentation on it and add more examples soon.

USB Programming with Python on Linux – PyUSB version

In my earlier post I was using libhid however due to it’s alleged problems with multi-threading I decided to use PyUSB instead. The code is a bit different, however a little shorter and simpler.

One notable thing to be aware of is that device I’m using is HID device and Linux is automatically loading HID drivers for it so it needs to be unloaded for PyUSB to continue working. That’s done by calling dev.detachkernel_driver(0)_ I suppose the device is used as vendor-specific device then, but who cares.

Anyway, here’s the code, should be a bit simpler than before: