Travelling Santa — kirit.com

Santa has to deliver presents at cities scattered over a small area. Unfortunately he only knows where one of the cities is. Thankfully he can expect that the residents will be able to point him to another city when he arrives there. Santa has a lot of other places to go to so doesn't want to spend too much time going back and forth visiting cities in this small area. Can you help him?

Your task is to write a computer program that will help to guide Santa as he looks for the cities that he must visit. In order to help him to find the best program Santa approached Felspar and we put together a quick Django application so that he can find the best program to use.

The programs

The program that you write must be capable of interacting with the Santa website to tell a virtual Santa where to move. He can make a single move going north, south, east or west. The program will play on square tiles and can only see the eight tiles immediately around Santa (and of course the tile that Santa is on). At the start of the game you will be at a city and you will be told of the location of another city.

All locations are given relative to the position where Santa is. So, for example, if you are told that a city is 3 north and 2 west then you must move north three times and west twice in order to land on it. When you do land on it another city location will be revealed to you (assuming that there are more cities to reveal).

The initial configuration is played with ten cities spread over a 15 ȕ 15 area. The board is not bounded — there is nothing stopping you from just heading north forever. You are not told where you are relative to the small populated area where the cities are — you only know the positions of the cities that you have discovered and that have been revealed to you.

Using the Travelling Santa website

The first thing you should do is to head over the Travelling Santa web site and register then log in. To make sure you properly understand what happens we have created a web interface that you can use to play manually. Click on the link for the “test city plans” and create a new city plan.

You will see some API instructions that will be useful to you later, four buttons to move Santa and the information that you currently have and there are links to show what that information will look like to your program.

Registering a program

When you have a program that you want to use to enter you should register it. This is done from the home page by clicking on the “list of programs” link. You will probably want to register one program for different algorithms that you want to enter, maybe also keeping one for test runs. Later on you will be able to mark some programs as inactive.

Once the program has been registered it can make new city plans and control Santa's journey completely automatically.

Scoring entries

There are many details here yet to be sorted out — your feedback is welcome. Santa realises that there is a large random element to this and doesn't want to penalise unlucky programs. Because of this he will not count either the best or the worst performances of a program and nor will he just use the number of moves. What he wants to do is to work out what the best route would have been given the starting city and then mark the program based on its ratio of moves that it made to this optimum.

That is, a program that visits all the cities using 100 moves, when it was possible to do the journey in 50 moves will get a score of 2 — clearly the lower the score the better and hopefully some programs will be able to get quite close to 1. Santa knows that if any programs get less than one then he's got his calculations wrong.

In order to get the puzzle out so everybody gets plenty of time to think about it and work on it we haven't written the marking part of the system yet — that should follow sometime this week.

The API

You can work in any programming language that you want. The only requirements are that the program must be able to make HTTP requests on our server (both GET and POST)¹ [1Note that the web server uses host headers, so you must have a HTTP 1.1 client. You can probably get away with a HTTP 1.0 client if you are able to add the required host header to the request.] and that it must be able to understand the JSON data sent back.

In order to make it easier for people we have not implemented any security layer — the program and the city plan URLs are based on SHA1 hashes. So long as you don't give them away this ought to be secure enough for the modest requirements of this site.

Making a new city plan

Once a program has been registered on the site you will get a URL that looks something like this:

http://santa.example.com/program/72ad9d54ed20330fdeaa539be922f6b9b8c01bd3/

This page will list out what your program has done so far. In order to make a new city plan it must make a POST request to the following:

http://santa.example.com/program/72ad9d54ed20330fdeaa539be922f6b9b8c01bd3/new/1/

Note that case is important, and so are those trailing slashes. Because the REST API expects to be given JSON you will need to put some valid JSON in the POST body. This should just be the string null.

Assuming that everything works properly then you will get back a HTTP 302² [2This really ought to be a 303, but Django uses 302s and we've not changed that.] with the base URL for the new city in the Location header.

For now there is only a single city configuration (10 cities on a 15 ȕ 15 grid), but Santa is considering adding new ones later on.

Getting the status of a current city plan

The URL that you will have gotten back from the previous operation will look something like this:

http://santa.example.com/city/f2e20e4dc8929643b9a5b5adafa6dfef670f82aa/

This is the URL of the normal web page that you can use to monitor what is happening. In order to get access to the starting data in JSON format the program should perform a GET agains:

http://santa.example.com/city/f2e20e4dc8929643b9a5b5adafa6dfef670f82aa/json/

Again, the case and the trailing slash are important. In order to make a move the program should now do a POST request against one of four URLs depending on which direction it wishes to move.

http://santa.example.com/city/f2e20e4dc8929643b9a5b5adafa6dfef670f82aa/json/N/
http://santa.example.com/city/f2e20e4dc8929643b9a5b5adafa6dfef670f82aa/json/S/
http://santa.example.com/city/f2e20e4dc8929643b9a5b5adafa6dfef670f82aa/json/E/
http://santa.example.com/city/f2e20e4dc8929643b9a5b5adafa6dfef670f82aa/json/W/

Did we say that the case and the trailing slash were important?

After processing you will get back an updated status message. You will know when you have completed the map because the “completed” time stamp in the problem meta-data will be filled in.

JSON format

I'm not going to document the JSON format here. You should do some maps manually first and look at what you are told in the JSON for various scenarios — this is what the pretty printed JSON link is for.

Example program

In our Subversion repository you will find the following an example Python program that is none too clever, but shows how to interact with the site.

import sys, urllib2, simplejson

def main(args):
    print "Solving problem at " + args[1]
    # The first program argument should be the URL of the configuration that we wish to make
    #  i.e. http://santa.example.com/program/17959aa371fd744b858cc10bdb6ad0662634a19f/new/1/
    request = urllib2.urlopen(args[1], 'null')
    # Assuming this is succesful the final URL will be the redirection to the city page. We can
    # then get the initial information by asking for the JSON blob.
    status = simplejson.loads(urllib2.urlopen(request.url + 'json/'))
    # The 'completed' time stamp will be filled in when the final city is visited
    while not status['problem']['completed']:
        next = None
        # The revealed list shows us cities we've been told about. The city ordering is stable,
        # but newly revealed cities may appear anywhere in the list
        for city in status['revealed']:
            # Find the first city we've not visited
            if not city['visited']:
                print city
                for k in city.keys():
                    # Find the first key which is not 'visited' and then use that as the direction to move in
                    if k != 'visited':
                        next = simplejson.loads(urllib2.urlopen(request.url + ('json/%s/' % k), 'null'))
                        break
                break
        # Make sure we've refreshed the status properly
        if next:
            status = next
        else:
            status = simplejson.loads(urllib2.urlopen(request.url + 'json/'))

if __name__ == "__main__":
    sys.exit(main(sys.argv))

The Travelling Santa web site code

The code that runs the Travelling Santa web site is available for everybody to see. It can be fetched via:

svn co http://svn.felspar.com/public/travelling-santa/trunk travelling-santa-trunk

Feel free to take a look. Doing so is not cheating as it gives nothing away.

Running the site on your own system

If you're familiar with Django then hopefully it will be fairly clear how to use the code and run the site locally to develop against — this has two benefits. Firstly your code will run faster and secondly, you won't be overloading our server.

I'll get some better instructions out, but some quick notes that might help you get up and running:

The settings.py contains connection data for a Postgres database. You will need to change this to something that works on your machine, or create a "Django" user (password of "django") who is the owner of a database called "santa".
You will want to set the PYTHONPATH to the location of the "web-site" directory. If you do not have SimpleJSON installed in your Python installation (i.e. you haven't or couldn't do something like apt-get install python-simplejson) then you will also want the "web-site/django/utils" directory on the PYTHONPATH.
You will need to use python manage.py syncdb to create a blank database, and you will also need to do python manage.py loaddata configurations.json to load the standard city plan configuration.

Patches welcome

We're very happy to accept patches for bug fixes and enhancements — especially simple example client programs to show how to interact with the site using other languages.