therning.org/ magnus

In the comments to my post on the Google treasure hunt Andre asked me to put up my solution for the fourth problem. The problems were personalised and here is mine:

Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 29 consecutive prime numbers,
the sum of 373 consecutive prime numbers,
the sum of 665 consecutive prime numbers,
and is itself a prime number.

The idea behind my solution is that if I have four lists of the sums, and a list of primes, then the solution to the problem is the smallest member of the intersection of all five lists.

I saved the problem of finding primes to the last and instead concentrated on summing up lists of integers in a convenient way. I ended up with the following solution to that:

sumN :: Int -> [Integer]
sumN n = map fst sumi
    where
        sumi = tail $ iterate (sumn) (0, primes)
        sumn (r, xs) = (sum $ take n xs, tail xs)

The real work happens in the inner functions. sumn picks out as many numbers as I want and sums them up, the reason for taking and returning a tuple is that sumi can use iterate to calculate the sequence of sums. The first item in the result of iterate a is a, so sumi drops the first one. This lets me create the needed lists of sums:

sum3 = sumN 3
sum29 = sumN 29
sum373 = sumN 373
sum665 = sumN 665

After having a quick look at the implementation of Data.List.intersect I realised it probably would be a bit too slow. Instead I wrote one that exploits that all the involved lists are ordered:

intersection a@(x:xs) b@(y:ys)
    | x == y = x : intersection xs ys
    | x < y = intersection (dropWhile (< y) xs) b
    | x > y = intersection a (dropWhile (x >) ys)

After convincing myself that this code did what I wanted (basically through playing in GHCi using an incorrect definition of primes, primes = [1..]) I turned to the problem of finding the primes. Of course someone else had already written the Haskell code to find primes. That code fitted perfectly with mine since it produces an infinate list of Integers. Brilliant!

Finally here’s the main that allows me to compile the code and get the answer quickly (it’s slightly modified for the medium, basically I wrote it all on one, long line):

main :: IO ()
main = let
        i1 = (primes `intersection` sum665)
        i2 = (sum3 `intersection` sum373)
        s =  i1 `intersection` i2 `intersection` sum29
    in
        print $ head s

Compiled, it runs in about 5.5 seconds on my desktop machine.

I personally found the first one to be the trickiest, quite a bit of thinking with a colleague before we saw Pascal’s triangle in the problem. I was a bit worried that things would get trickier from there on. It surely didn’t.

The second, summing certain lines taken from files matching certain glob patterns, was easily solved with a short Haskell program.

The third, a routing problem was probably the easiest and I think most easily solved on paper. I did make a mistake though, which I caught before typing my answer into the webform.

The fourth one, adding sequences of primes, was fairly straight forward. I think it would have presented a bit more trouble if I didn’t make use of Haskell’s laziness and support for infinate lists though.

I bet a lot of people would consider this to be fairly obvious, but today, while solving the fourth of Google’s Treasure Hunt problems I realised just how similar in essence laziness+infinate lists in Haskell is to generators in Python. It’s just much easier to work with the former

I hope this will be out of date really soon, but here’s what I did to solve the problems I had with the nVidia driver after upgrading to the latest kernel in Sid (2.6.25). First download the file NVIDIA_kernel-169.12-2286310.diff.txt from this forum article. Then, as root do:

# cd /usr/src
# m-a clean nvidia-kernel
# tar -x -j -f nvidia-kernel.tar.bz2
# pushd modules/nvidia-kernel/nv
# patch -p3 < NVIDIA_kernel-169.12-2286310.diff.txt
# popd
# m-a -O build nvidia-kernel

Now there’s a package ready for installation

I bet you have at least one silly little thing at work that, whenever it happens, you let out a sigh, maybe roll your eyes and whish that everyone would use a proper operating system. A few days I finally decided to do something about one of my things like that. At work, Windows users will at times for some strange reason, manually create directories inside their work area, even though the directories actually are under version control. Invariably they get the case wrong and due to an onfortunate combination of case insensitive filesystem on the client (Windows) and a version control system the cares about case (Perforce). This results in files ending up all over the place even though they belong in the same directory. The Windows users are none the wiser, they simply don’t see the problem. Since I use a sane system (Linux) I do notice, and when I see it I sigh and roll my eyes.

Here’s my take on solving the problem:

module Main where

import Control.Monad
import Data.Char
import System.Directory
import System.Environment
import System.FilePath
import System.IO.HVFS.Utils
import System.Posix.Files

data IFile = IFile
    { iFileIPath :: FilePath
    , iFileIName :: FilePath
    , iFileFull :: FilePath
    } deriving (Show)

toIFile :: FilePath -> IFile
toIFile fp =  IFile path file fp
    where
        path = map toLower $ takeDirectory fp
        file = map toLower $ takeFileName fp

listFilesR :: FilePath -> IO [IFile]
listFilesR path =
    recurseDir SystemFS path >>=
    filterM doesFileExist >>=
    mapM (return . toIFile)

linkFile :: FilePath -> IFile -> IO ()
linkFile dest ifile = do
        createDirectoryIfMissing True newDir
        createLink (iFileFull ifile) newFile
    where
        newDir = normalise $ dest </> (iFileIPath ifile)
        newFile = newDir </> (iFileIName ifile)

main :: IO ()
main = do
    args <- getArgs
    listFilesR (args !! 0) >>= mapM_ (linkFile $ args !! 1)

Yes, this is the code I wrote in Literate Haskell, but I think I’d better not disclose my rant against clueless Windows users publically

Another dear lazyweb post.

Yesterday night I hacked up a silly little tool for use at work. Nothing spectacularⁱ but I thought I’d try this Literate Haskell thing. I decided to go the LaTeX route and created a .lhs file. To my amazement rubber has a module for handling Literate Haskell, unfortunately it passes everything ending in .lhs through lhs2Tex. I didn’t really want to use lhs2Texⁱⁱ but I haven’t been able to find any way of changing rubber’s behaviour through its command line arguments. What I’d like is a way to disable a module for a single invocation. So, dear lazyweb, is there a way to do this from the command line?

So far I’ve worked around this by creating a symbolic link named MyTool.tex that points to the Haskell source, then I run rubber on the link. Not to much of a hazzle, but it’d be nicer to pass an argument to rubber.

1. I’ll post the source here shortly.[back]
2. I’ll probably have a closer look at it later but for now I wanted to keep things as easy as possible.[back]

I just went through the exercise of setting up MediaWiki on a Debian Etch box, but instead of serving it using the common choice of Apache I wanted to use lighttpd. It seems the combination MediaWiki and Apache is well supported on Debian. There was even an install-time question whether I wanted the configuration files set up for me. Well, it’s boring to follow the common path, right?

It seems the combination MediaWiki and Apache is well supported on Debian. Luckily that doesn’t mean it’s difficult to serve it with lighttpd. Here’s how I configured things, and luckily it all seems to work just fine

Installation

First off, I installed mediawiki1.7, lighttpd, php5-cgi, and mysql-server. I made sure that aptitude only pulled in required packages and then I started un-choosing all Apache-related packages. By the time you get to installing MySQL you’ll be asked for a root password, that is if your debconf is set to ask medium-level questions.

Setting up MediaWiki

The Debian package for MediaWiki creates a site in /var/lib/mediawiki1.7 consisting mostly of symbolic links to the actual location of its files. I kept lighttpd’s default document root of /var/www and linked the two by creating a symbolic link /var/www/mw pointing to the MediaWiki site (/var/lib/mediawiki1.7).

Configuration of lighttpd

First enable FastCGI by linking /etc/lighttpd/conf-available/10-fastgi.conf into /etc/lighttpd/conf-enabled/. Then go in and change the bin-path to point to /usr/bin/php5-cgi. To prepare for the MediaWiki configuration, enable mod_rewrite in /etc/lighttpd/lighttpd.conf and finally create the file /etc/lighttpd/conf-enabled/20-mediawiki.conf with the following contents:

url.rewrite-once = (
    "^/$" => "/mw/index.php",
    "^/wiki/([^?]*)(?:\?(.*))?” => “/mw/index.php?title=$1&$2″
  )

Now it’s time to restart lighttpd.

Configuration of MediaWiki

Point a browser to http://your.server/mw/config/index.php to configure the site settings. When that’s done copy the file /var/lib/mediawiki1.7/config/LocalSettings.php one layer up.

That should be it! Enjoy!

I’m writing this mostly so that I’ll remember myself

If pbuilder --create fails when building a base image for Sid then it’s worth trying to build a base image for the stable release and then upgrade to Sid afterwards. The very manual way is pbuild --login --save-after-login.

As promised I’ve now created Debian packages for omnicodec. Since dataenc is a pre-requisite for building from source there are packages for it as well.

I’ve uploaded the source to Debian Mentors here and here. As usual pre-built binaries are available from my own APT repo.

Dear lazyweb, I’ve been racking my brain trying to get information out of the following C struct in a nice way when using ctypes:

struct Foo
{
    unsigned int length;
    char name[];
};

I wrote a little C function to get instance of the struct easily into python:

struct Foo *
put_name(char *name)
{
    struct Foo *foo = malloc(sizeof(struct Foo) + strlen(name));
    foo->length = strlen(name);
    memcpy(foo->name, name, foo->length);
    return(foo);
}

Now, how do I actually get the full contents of Foo.name in python? The only way I could think of that actually works is to create a dummy-struct type in order to get the length out and then use it to dynamically create a new sub-class of ctypes.Structure, then create an instance based on the address of what was returned. I think the following shows it pretty clearly:

class FOO(Structure):
    _fields_ = [('length', c_uint), ('name', c_char * 0)]

liblib = cdll.LoadLibrary(’./_build/liblib.so’)
c_put_name = liblib.put_name
c_put_name.argtypes = [c_char_p]
c_put_name.restype = POINTER(FOO)

def put_name(str):
    f = c_put_name(str)
    K = type(’FOO%s’ % f.contents.length, (Structure,),
                        {’_fields_’ : [('length', c_uint), ('name', c_char * f.contents.length)]})
    return K.from_address(addressof(f.contents))

I still think there ought to be some other way that ‘feels’ nicer. I mean the use of “short arrays” (declared as here with [], or zero size as supported by GCC, or the more portable array of size one) seems to be common enough to warrant some support from ctypes, right?

Any suggestions for improvements?