Solving Euler Question 24

I'm learning Clojure by solving project Euler. Here is a python version of one of the solutions.

#!/usr/bin/env python
''' Solving http://projecteuler.net/index.php?section=problems&id=24

Note that Python's 2.6 itertools.permutations return the permutation in order so
we can just write:
    from itertools import islice, permutations
    print islice(permutations(range(10)), 999999, None).next()

And it'll work much faster :)
'''

from itertools import islice, ifilter

def is_last_permutation(n):
    return n == sorted(n, reverse=1)

def next_head(n):
    '''Find next number to be 'head'. 

    It is smallest number if the tail that is bigger than the head.
    In the case of (2 4 3 1) it will pick 3 to get the next permutation
    of (3 1 2 4)
    '''
    return sorted(filter(lambda i: i > n[0], n[1:]))[0]

def remove(element, items):
    return filter(lambda i: i != element, items)

def next_permutation(n):
    if is_last_permutation(n):
        return None

    sub = next_permutation(n[1:])
    if sub:
        return [n[0]] + sub

    head = next_head(n)
    return [head] + sorted([n[0]] + remove(head, n[1:]))

def nth(it, n):
    '''Return the n'th element of an iterator'''
    return islice(it, n, None).next()

def iterate(func, n):
    '''iterate(func, n) -> n, func(n), func(func(n)) ...'''
    while 1:
        yield n
        n = func(n)

def permutations(n):
    return ifilter(None, iterate(next_permutation, n))

if __name__ == "__main__":
    n = range(10)
    m = 1000000
    print "Calculateing the %d permutation of %s" % (m, n)
    print nth(permutations(n), m-1)

pmap

#!/usr/bin/env python
'''Parallel map (Unix only)'''

__author__ = "Miki Tebeka <miki.tebeka@gmail.com>"

# The big advantage of this implementation is that "fork" is very fast on
# copying data, so if you pass big arrays as arguments and return small values
# this is a win

# FIXME 
# * For too many items, we get "Too many open files"
# * Handle child exceptions

from os import fork, pipe, fdopen, waitpid, P_WAIT
from marshal import dump, load
from itertools import takewhile, count

def spawn(func, data):
    read_fo, write_fo = map(fdopen, pipe(), ("rb", "wb"))
    pid = fork()
    if pid: # Parent
        return pid, read_fo

    # Child
    dump(func(data), write_fo)
    write_fo.close()
    raise SystemExit

def wait(child):
    pid, fo = child
    waitpid(pid, P_WAIT)
    value = load(fo)
    fo.close()
    return value

def pmap(func, items):
    '''
    >>> pmap(lambda x: x * 2, range(5))
    [0, 2, 4, 6, 8]
    '''
    children = map(lambda item: spawn(func, item), items)
    return map(wait, children)

if __name__ == "__main__":
    def fib(n):
        a, b = 1, 1
        while n > 1:
            a, b = b, a + b
            n -= 1
        return b

    items = range(10)
    print "pmap(fib, %s)" % str(items)
    print pmap(fib, items)

__subclasses__

New style classes have a __subclasses__ method which I find useful the problem of "find me all instances to run" - without any metaclass black voodoo :)

A trivial example:

#!/usr/bin/env python

class Animal(object):
    pass

class Dog(Animal):
    def talk(self):
        return "whoof whoof"

class Cat(Animal):
    def talk(self):
        return "miao"

class Pig(Animal):
    def talk(self):
        return "oink oink"

def all_animals():
    return Animal.__subclasses__()

if __name__ == "__main__":
    for animal in all_animals():
        print "%s says: %s" % (animal.__name__, animal().talk())

This way, if we add a new animal all_animals will work without any change from us.

glue

Sometime you need to produce a quick prototype for a site that is an aggregation of several other sites.

One quick way is to glue the parts you want from each site into the page.
We'll use a more relaxed version of trampoline to overcome cross site scripting.

redirect.cgi

#!/usr/bin/env python
'''Get content of "foreign" web pages, enable cross-site AJAX'''

from urllib2 import urlopen, URLError
from cgi import FieldStorage

if __name__ == "__main__":
   import cgitb; cgitb.enable()

   form = FieldStorage()
   url = form.getvalue("url", "")
   if not url:
       raise SystemExit("no url")

   try:
       o = urlopen(url)
   except (URLError, ValueError), e:
       raise SystemExit("error: %s" % e)

   print "Content-type: %(content-type)s\n" % o.headers
   print o.read()

And then in our page we'll glue the parts. I'm using the same part from Weather Underground but with different area. (Ignoring the fact they have a good API :)

index.html

<html>
   <head>
       <title></title>
       <style>
           h1.title {
               text-align: center;
           }
           .header {
               background: blue;
               color: white;
               font-size: 1.3em;
               font-weight: bold;
               font-variant: small-caps;
           }
           div.left {
               float: left;
               width: 50%;
               height: 400px;
               overflow: auto;
           }
           div.right {
               float: right;
               width: 50%;
               height: 400px;
               overflow: auto;
           }
       </style>
   </head>
   <body>
       <h1 class="title">Weather Meshup</h1>

       <div>
           <div class="left">
               <div class="header">Beverly Hills</div>
               <div id="bh">Loading ...</div>
           </div>

           <div class="right">
               <div class="header">New York</div>
               <div id="ny">Loading ...</div>
           </div>
       </div>
       <div>
           <div class="left">
               <div class="header">Chicago</div>
               <div id="ch">Loading ...</div>
           </div>

           <div class="right">
               <div class="header">Washington</div>
               <div id="wa">Loading ...</div>
           </div>
       </div>
   </body>
   <script src="jquery.js"></script>
   <script>
       function weather_url(zipcode) {
           return 'http://www.wund.com/cgi-bin/findweather/getForecast' +
                  '?query=' + zipcode;
       }

       function load_foreign(id, url, selector) {
           $('#' + id).load('redirect.cgi ' + selector, {url: url});
       }

       function load_weather(id, zipcode) {
           var url = weather_url(zipcode);
           load_foreign(id, url, 'div#conditions');
       }


       function on_ready()
       {
           load_weather('bh', '90210');
           load_weather('ny', '10001');
           load_weather('ch', '60290');
           load_weather('wa', '20001');
       }

       $(document).ready(on_ready);
   </script>
</html>

@reboot

cron has a nice special rule called @reboot which will run every time the machine is rebooted (doh!).

I use it for two main things:

1. Notify me when one of my servers was rebooted (sometimes IT don't tell me in advance)
2. Run my services. This is easier than writing an /etc/init.d scripts and I store my servers crontab in the source control, so deploying a new machine is easier.
   

An example:

# Notify that machine was rebooted
@reboot /path/to/mail -s "Machine $HOSTNANE rebooted" me@somewhere.com < /dev/null
# Run my server
@reboot (cd /path/to/awesome/server/directory && ./run_server)

Where run_server is usually something like:

#!/bin/bash

nohup ./server.py&

calc

A very simple command line/GUI calculator. The main trick here is to export all of math to the global namespace and then just eval the expression.

twiver

A Twitter search client the updates every 10min.

#!/usr/bin/env python

from BaseHTTPServer import HTTPServer, BaseHTTPRequestHandler
from urlparse import urlparse
from urllib2 import urlopen
from operator import itemgetter
from rfc822 import parsedate_tz
from time import strftime
import re
from functools import partial

try:
  import json
except ImportError:
  import simplejson as json

HTML = '''
<html>
    <head>
        <title>Twiver - Refreshing Twitter Search</title>
        <style>
            h2 {
                font-variant: small-caps;
            }
            table#results {
                border: 1px solid black;
                width: 100%;
            }
            table#results tr:hover {
                background: silver;
            }
            span#updated {
                font-family: Monospace;
            }
        </style>
    </head>
    <body>
        <h2>Twiver - Refreshing Twitter Search</h2>
        Query: <input id="query" size="60" /> <button id="run">Go</button>
        <table id="results">
        </table>
        <span id="updated"></span>
        <hr />
        By <a href="mailto:miki.tebeka@gmail.com">Miki</a>
    </body>
    <script src="jquery.js"></script>
    <script>
        var running = 0;

        function handle_result(data) {
            if (!running) {
                return;
            }

            var table = $('#results');
            table.empty();
            $.each(data, function (i, text) {
                var tr = $('<tr><td>' + text + '</td></tr>');
                table.append(tr);
            });
            $('#updated').html('Updated: ' + new Date());

            setTimeout(update, 10 * 1000);
        }

        function update() {
            var query = $.trim($('#query').val());
            url = '/search?q=' + query;
            $.getJSON(url, handle_result);
        }

        function run() {
            var button = $('#run');
            if (button.text() == "Go") {
                var query = $.trim($('#query').val());
                /* FIXME: The best way will be to disable the button until there
                  is text
                */
                if (query.length == 0) {
                    alert("Please enter *something*");
                    return;
                }
                button.text("Stop");
                running = 1;
                update();
            }
            else {
                running = 0;
                button.text("Go");
            }
        }

        function on_ready()
        {
            $('#run').click(run);
        }
        $(document).ready(on_ready);
    </script>
</html>
'''

def format_time(time):
  # Wed, 11 Feb 2009 00:10:36 +0000
  time = parsedate_tz(time)
  return strftime("%m/%d/%Y %H:%M", time[:9])

# 'http://mikitebeka.com' -> 
# '<a href="http://mikitebeka.com">http://mikitebeka.com</a>'
inject_links = partial(
  re.compile("(http://[^ ]+)").sub,
  "<a target=\"_new\" href=\"\\1\">\\1</a>")

def format_result(result):
  time = format_time(result["created_at"])
  text = inject_links(result["text"])
  return "[%s] %s" % (time, text)

class RequestHandler(BaseHTTPRequestHandler):
  def do_GET(self):
      if self.path == "/":
          self.wfile.write(HTML)
      elif self.path.startswith("/search"):
          self.updates()
      elif self.path.endswith(".js"):
          self.wfile.write(open(".%s" % self.path).read())
      else:
          self.send_error(404, "Not Found")

  def updates(self):
      o = urlparse(self.path)
      url = "http://search.twitter.com/search.json?" + o.query
      data = urlopen(url).read()
      obj = json.loads(data)
      results = map(format_result, obj["results"])
      self.wfile.write(json.dumps(results))

if __name__ == "__main__":
  server = HTTPServer(("", 8888), RequestHandler)
  server.serve_forever()

"Game of Life" in JavaScript

<html>
    <head>
        <title>Game Of Life</title>
        <style>
            table {
                border: 5px solid black;
            }
            td {
                width: 15px;
                height: 15px;
            }
            td.dead {
                background: green;
            }
            td.alive {
                background: red;
            }
        </style>
    </head>
    <body>
        <b>Game of Life<b>
        <table id="board">
        </table>
        <button id="run">Run</button>
        <button id="step">Step</button>
        <button id="clear">Clear</button>

    </body>
    <script src="jquery.js"></script>
    <script>
        var NUM_ROWS = 30;
        var NUM_COLS = 30;
        var DEAD = 'dead';
        var ALIVE = 'alive';
        var RUNNING = 0;
        /* We keep this for fast access since jQuery selectors
        $('#board tr:nth-child(' + row + 1 + ') td:nth-child(' + col + 1 + ')'
        are slow
        */
        var BOARD = [];

        function copy_board() {
            var board = [];
            for (var row = 0; row < NUM_ROWS; ++row) {
                var cells = [];
                for (col = 0; col < NUM_COLS; ++col) {
                    var state = get_cell(row, col).hasClass(ALIVE) ?
                                ALIVE : DEAD;
                    cells.push(state);
                }
                board.push(cells);
            }

            return board;
        }

        function cell_neighbours(row, col) {
            var uprow = (row + 1) % NUM_ROWS;
            var downrow = (row - 1) % NUM_ROWS;
            var leftcol = (col - 1) % NUM_COLS;
            var rightcol = (col + 1) % NUM_COLS;

            /* FIXME: Find a better way (since -1 % 10 => -1) */
            downrow = (downrow < 0) ? NUM_ROWS - 1 : downrow;
            leftcol = (leftcol < 0) ? NUM_COLS - 1 : leftcol;

            return [
                [uprow, leftcol], [uprow, col], [uprow, rightcol],
                [row, leftcol], [row, rightcol],
                [downrow, leftcol], [downrow, col], [downrow, rightcol]
            ];
        }

        /* http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Rules */
        function calc_new_state(current_state, num_alive) {
            if (current_state == ALIVE) {
                if (num_alive < 2) {
                    return DEAD;
                }
                else if (num_alive > 3) {
                    return DEAD;
                }
                else {
                    return ALIVE;
                }
            }
            else {
                if (num_alive == 3) {
                    return ALIVE;
                }
                else {
                    return DEAD;
                }
            }
        }


        function on_step() {
            /* Copy old board since we're going to change the current */
            var board = copy_board();

            function is_alive(cell) {
                return board[cell[0]][cell[1]] == ALIVE;
            }

            for (var row = 0; row < NUM_ROWS; ++row) {
                for (var col = 0; col < NUM_COLS; ++col) {
                    var neighbours = cell_neighbours(row, col);
                    var num_alive = $.grep(neighbours, is_alive).length;
                    var current_state = board[row][col];
                    var new_state = calc_new_state(current_state, num_alive);
                    if (new_state != current_state) {
                        toggle(row, col);
                    }
                }
            }
        }

        function run() {
            if (!RUNNING) {
                return;
            }
            on_step();
            setTimeout(run, 200);
        }

        function on_run() {
            var button = $('#run');
            if (button.text() == 'Run') {
                button.text('Stop');
                RUNNING = 1;
                run();
            }
            else {
                button.text('Run');
                RUNNING = 0;
            }
        }

        function get_cell(row, col) {
            return BOARD[row][col];
        }

        function toggle(row, col) {
            var cell = get_cell(row, col);

            if (cell.hasClass(ALIVE)) {
                var add = DEAD;
                var remove = ALIVE;
            }
            else {
                var add = ALIVE;
                var remove = DEAD;
            }

            cell.removeClass(remove).addClass(add);
        }

        function make_handler(row, col) {
            return function() {
                toggle(row, col);
            }
        }

        function initiaize_board() {
            var table = $('#board');
            for (var row = 0; row < NUM_ROWS; ++row) {
                var tr = $('<tr />');
                var cells = [];
                for (var col = 0; col < NUM_COLS; ++col) {
                    var td = $('<td />');
                    td.addClass(DEAD);
                    td.click(make_handler(row, col));
                    tr.append(td);
                    cells.push(td);
                }
                table.append(tr);
                BOARD.push(cells);
            }
        }

        function on_clear() {
            $('.' + ALIVE).removeClass(ALIVE).addClass(DEAD);
        }

        function on_ready()
        {
            initiaize_board();
            $('#step').click(on_step);
            $('#run').click(on_run);
            $('#clear').click(on_clear);
        }

        $(document).ready(on_ready);
    </script>
</html>

Find Module Version

Quick script to check which version of Python module is installed.

#!/usr/bin/env python
'''Find python module version'''

__author__ = "Miki Tebeka <miki.tebeka@gmail.com>"

def valueof(v):
    if callable(v):
        try:
            return v()
        except Exception:
            return None
    return v

def load_module(module_name):
    module = __import__(module_name)

    # __import__("a.b") will give us a
    if ("." in module_name):
        names = module_name.split(".")[1:]
        while names:
            name = names.pop(0)
            module = getattr(module, name)

    return module

def find_module_version(module_name):
    module = load_module(module_name)
    attrs = set(dir(module))

    for known in ("__version__", "version", "version_string"):
        if known in attrs:
            v = valueof(getattr(module, known))
            if v:
                return v

    for attr in attrs:
        if "version" in attr.lower():
            v = getattr(module, attr)
            if not v:
                continue
            v = valueof(v)
            if v:
                return v

def main(argv=None):
    if argv is None:
        import sys
        argv = sys.argv

    from optparse import OptionParser

    parser = OptionParser("usage: %prog MODULE_NAME")

    opts, args = parser.parse_args(argv[1:])
    if len(args) != 1:
        parser.error("wrong number of arguments") # Will exit

    module_name = args[0]

    try:
        version = find_module_version(module_name)
    except ImportError, e:
        raise SystemExit("error: can't import %s (%s)" % (module_name, e))

    if version:
        print version
    else:
        raise SystemExit("error: can't find version for %s" % module_name)

if __name__ == "__main__":
    main()

Which build utility to run?

I have the following as a script called "mk" and set in my .vimrc

set makeprg=mk

#!/bin/bash
# Guess which make utility to use

# Miki Tebeka <miki.tebeka@gmail.com>

makecmd=""
if [ -f SConstruct ]; then
    makecmd="scons -Q -D"
elif [ -f build.xml ]; then
    makecmd="ant"
elif [ -f Makefile ]; then
    makecmd="make"
elif [ -f makefile ]; then
    makecmd="make"
elif [ "$OSTYPE" == "WINNT" ]; then
    proj=`ls *.dsp 2>/dev/null`
    if [ -f $proj ]; then
        makecmd="msdev $proj /MAKE"
    fi
fi

if [ -z "$makecmd" ]; then
    echo "can't find project file"
    exit 1
fi

$makecmd $@

Moved to bitbucket

All(?) the code from this blog is now at BitBucket

imapclean

#!/usr/bin/env python
'''Clean your IMAP inbox

Copy all message to "Archive" and delete them from Inbox
'''

__author__ = "Miki Tebeka <miki.tebeka@gmail.com>"

from imaplib import IMAP4
import logging as log

def move_messages(server, user, passwd, purge=0):
    imap = IMAP4(server)
    imap.login(user, passwd)
    imap.select()
    messages = imap.search(None, "ALL")[1][0].split()
    for msg_id in messages:
        flags = imap.fetch(msg_id, "(FLAGS)")[1][0]
        if not flags.startswith(msg_id):
            log.error("bad reply for %s flags - %s" % (msg_id, flags))
            continue
        if "Deleted" in flags:
            log.info("skipping %s - already deleted" % msg_id)
            continue
        log.info("deleting %s" % msg_id)
        imap.copy(msg_id, "Archive")
        imap.store(msg_id, "+FLAGS", "\\Deleted")

    if purge:
        log.info("purging deleted messages")
        imap.expunge()
    log.info("logging out")
    imap.close()
    imap.logout()

def main(argv=None):
    if argv is None:
        import sys
        argv = sys.argv

    from optparse import OptionParser
    from getpass import getpass, getuser

    parser = OptionParser("usage: %prog")
    parser.add_option("-p", "--purge", help="purge deleted messages",
        action="store_true", default=0, dest="purge")
    parser.add_option("-v", "--verbose", help="be verbose",
                      dest="verbose", action="store_true", default=0)
    parser.add_option("--server", help="imap server",
            default="localhost", dest="server")
    parser.add_option("--user", help="IMAP user name",
            dest="user", default="")
    parser.add_option("--passwd", help="IMAP password",
            dest="passwd", default="")

    opts, args = parser.parse_args(argv[1:])
    if args:
        parser.error("wrong number of arguments") # Will exit

    level = log.DEBUG if opts.verbose else log.ERROR
    log.basicConfig(format="%(levelname)s: %(message)s",
                        level=level)

    opts.user = opts.user or getuser()
    opts.passwd = opts.passwd or getpass()

    try:
        move_messages(opts.server, opts.user, opts.passwd, opts.purge)
    except Exception, e:
        if opts.verbose:
            log.exception(e)
        else:
            log.error(e)
        raise SystemExit(1)

if __name__ == "__main__":
    main()

Yeah, the pygments experiment worked.

crashlog

Get email notification whenever your program crashes.

The Code You Don't Write

Act without doing, work without effort.
Think of the small as large and the few as many.
Confront the difficult while it is still easy;
accomplish the great task by a series of small steps.
    - Lao-Tze

Sometimes, the code you don't write is more important than the one you write.
Whenever I start on a new task, my first question is "how can I do this without coding?".

Here's a small (true) exmaple:

We had a problem that serving files on an NFS mounted volume was slow for the first request and them it was good. Probably the mount went "stale" after a while.

First option of learning the inner working of NFS mounts was dropped immediately - you can never know how much time this tinkering will take and if it'll work eventually.

So I decided to keep the NFS mount "warm" by periodically accessing it.

First Version:

from time import sleep
from os import listdir

while 1:
    listdir("/path/to/nfs")
    sleep(10 * 60 * 60)

and in crontab

@reboot /usr/bin/python /path/to/script.py

Then I thought - "cron", and second version came:

from os import listdir

listdir("/path/to/nfs")</code></pre>

and in crontab:

*/10 * * * * /usr/bin/python /path/to/script.py

And then last version (just crontab):

*/10 * * * * /bin/ls /path/to/nfs

So down from 6 LOC to 3 LOC to 1 LOC - that's what I call produtivity :)

Where is Miki?

A little CGI script that show where I am (gets data from my google calendar).

Using Google Data Python API

#!/usr/bin/env python
'''Where where am I? (data from Google calendar)

Get gdata from http://code.google.com/p/gdata-python-client/
'''

__author__ = "Miki Tebeka <miki.tebeka@gmail.com>"

import gdata.calendar.service as cal_service
from time import localtime, strptime, strftime, mktime, timezone

DAY = 24 * 60 * 60

def caltime_to_local(caltime):
    # 2008-11-07T23:30:00.000+02:00
    t = mktime(strptime(caltime[:16], "%Y-%m-%dT%H:%M"))
    tz_h, tz_m = map(int, caltime[-5:].split(":"))
    cal_tz = (tz_h * 60 * 60) + (tz_m * 60)
    if caltime[-6] == "-":
        cal_tz = -cal_tz

    # See timezone documentation, the sign is reversed
    diff = -timezone - cal_tz 

    return localtime(t + diff)

def iter_meetings():
    client = cal_service.CalendarService()
    client.email = "your-google-user-name"
    client.password = "your-google-password"
    client.source = "Where-is-Miki"
    client.ProgrammaticLogin()

    query = cal_service.CalendarEventQuery("default", "private", "full")
    query.start_min = strftime("%Y-%m-%d")
    tomorrow = localtime(mktime(localtime()) + DAY)
    query.start_max = strftime("%Y-%m-%d", tomorrow)
    feed = client.CalendarQuery(query)
    for event in feed.entry:
        title = event.title.text
        when = event.when[0]
        start = caltime_to_local(when.start_time)
        end = caltime_to_local(when.end_time)

        yield title, start, end

def find_meeting(meetings, now):
    for title, start, end in meetings:
        print title, start, end
        if start <= now <= end:
            return title, end

    return None, None

def meetings_html(meetings):
    if not meetings:
        return "No meetings today"

    trs = []
    tr = "<tr><td>%s</td><td>%s</td><td>%s</td></tr>"
    for title, start, end in meetings:
        start = strftime("%H:%M", start)
        end = strftime("%H:%M", end)
        trs.append(tr % (title, start, end))

    return "Today's meetings: <table border='1'>" + \
           "<tr><th>Title</th><th>Start</th><th>End</th></tr>" + \
            "\n".join(trs) + \
            "</table>"

HTML = '''
<html>
    <head>
        <title>Where is Miki?</title>
        <style>
            body, td, th {
                font-family: Monospace;
                font-size: 22px;
            }
        </style>
    </head>
    <body>
        <h1>Where is Miki?</h1>
        <p>
            Seems that he is <b>%s</b>.
        </p>
        <p>
            %s
        </p>
    </body>
</html>
'''

if __name__ == "__main__":
    import cgitb; cgitb.enable()
    from operator import itemgetter

    days = ["Mon","Tue","Wed", "Thu", "Fri", "Sat", "Sun"]
    now = localtime()

    day = days[now.tm_wday]
    meetings = sorted(iter_meetings(), key=itemgetter(-1))

    # Yeah, yeah - I get in early
    if (now.tm_hour < 6) or (now.tm_hour > 17):
        where = "at home"
    elif day in ["Sat", "Sun"]:
        where = "at home"
    else:
        title, end = find_meeting(now, meetings)
        if end:
            where = "meeting %s (until %s)" % (title, strftime("%H:%M", end))
        else:
            where = "at work"

    print "Content-Type: text/html\n"
    print HTML % (where, meetings_html(meetings))