If you have a rooted Android phone, you have full control over your device — and unrestricted access to the data it contains. In this post, I’m going to show you how you can use your rooted Android device to do something that the average person can’t do: namely, export your contacts from the Facebook app on Android.

1. Get the contacts database

It turns out that the Facebook app stores your contacts in an SQLite database located on the filesystem at /data/data/com.facebook.katana/databases/fb.db. In order to use this database, we need to copy it to a computer. Since Android doesn’t provide access to the internal storage via USB, I first copied the database to my SD card using a root file browser, and then copied it to my computer via USB.

2. Examine the contacts database

Now that you have the database on your local machine, you can analyze it and determine its structure. Begin by opening it up with the SQLite client:

$ sqlite3 /path/to/fb.db

Now it’s just the standard procedure when dealing with an unknown database:

2.1 List the tables

sqlite> .tables
albums                    friends                   page_search_results
android_metadata          friends_data              perf_sessions
cache                     key_value                 photos
chatconversations         mailbox_messages          search_results
chatmessages              mailbox_messages_display  stream_photos
connections               mailbox_profiles          user_statuses
default_page_images       mailbox_threads           user_values
events                    notifications

2.2 Determine which tables contain the data you’re looking for

The table’s name is often a good indicator of its contents. In this case, the friends table (technically, it’s a view) contains all the data we need.

2.3 Determine which columns to extract

Here’s the structure of the friends view:

sqlite> .schema friends
CREATE VIEW friends AS SELECT connections._id AS _id, connections.user_id AS user_id, connections.display_name AS display_name, connections.connection_type AS connection_type, connections.user_image_url AS user_image_url, connections.user_image AS user_image, connections.hash AS hash, friends_data.first_name AS first_name, friends_data.last_name AS last_name, friends_data.cell AS cell, friends_data.other AS other, friends_data.email AS email, friends_data.birthday_month AS birthday_month, friends_data.birthday_day AS birthday_day, friends_data.birthday_year AS birthday_year FROM connections LEFT OUTER JOIN friends_data ON connections.user_id=friends_data.user_id WHERE connections.connection_type=0;

In this case, the important columns are:

• display_name
• user_image_url
• first_name
• last_name
• cell
• other
• email
• birthday_month
• birthday_day
• birthday_year

At this point, the hard part is over and it’s just a matter of extracting the data from the database.

3. Export the data

3.1 The vCard format

Now that we know exactly which data we need, we can export it from the database into a useful format. The most useful format for contact data appears to be vCard, which is almost universally supported in communication apps. I won’t go into the details of the vCard specification, but here’s an example of what we’re trying to generate:

BEGIN:VCARD
VERSION:3.0
N:Feynman;Richard;;;
FN:Richard Feynman
TEL;TYPE=HOME:+72973525698
EMAIL;TYPE=PREF:rfeynman@princeton.edu
BDAY:1918-5-11
REV:2012-01-08T18:36:35.814661
END:VCARD

BEGIN:VCARD
VERSION:3.0
N:Planck;Max;;;
FN:Max Planck
TEL;TYPE=CELL:+66260695729
EMAIL;TYPE=PREF:planck@berlin.de
BDAY:1858-4-23
REV:2012-01-08T18:36:36.043204
END:VCARD

Notice that multiple contacts can exist in the same file.

3.2 A script to generate the vCard

I’ve written a Python script to generate a vCard from the fb.db:

#!/usr/bin/env python
import sys
import base64
import codecs
import sqlite3
import urllib2
import argparse
import datetime

def parse_database(database):
    conn = sqlite3.connect(database)
    conn.row_factory=sqlite3.Row
    c = conn.cursor()
    fields = 'display_name, user_image_url, first_name, ' +\
             'last_name, cell, other, email, birthday_month, ' +\
             'birthday_day, birthday_year'
    c.execute('select %s from friends' % fields)
    return [row for row in c]

def generate_vcard(contact, photos=False):
    card = "BEGIN:VCARD\nVERSION:3.0\n"
    card += "N:%s;%s;;;\n" % (contact['last_name'], contact['first_name'])
    card += "FN:%s\n" % contact['display_name']

    if contact['cell']:
        card += 'TEL;TYPE=CELL:%s\n' % contact['cell']

    if contact['other']:
        card += 'TEL;TYPE=HOME:%s\n' % contact['other']

    if contact['email']:
        card += "EMAIL;TYPE=PREF:%s\n" % contact['email']

    birthday = "-".join([str(f) for f in [contact['birthday_year'],
                                          contact['birthday_month'],
                                          contact['birthday_day']]
                         if f != -1])
    if birthday:
        if birthday.count('-') == 1: birthday = "1900-" + birthday # default year
        card += "BDAY:%s\n" % birthday

    if photos and contact['user_image_url']:
        try:
            photo = urllib2.urlopen(contact['user_image_url']).read()
            card += "PHOTO;ENCODING=B;TYPE=JPEG:%s\n" %\
                    base64.b64encode(photo)
        except:
            pass


    card += "REV:%s\nEND:VCARD\n" % datetime.datetime.now().isoformat()
    return card

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument('database', help="path to facebook database", default="fb.db", nargs='?')
    parser.add_argument('vcard', help="file to write contacts to", default="fbcontacts.vcf", nargs='?')
    parser.add_argument('--photos', action="store_true", help="download profile pictures")
    args = parser.parse_args()

    with codecs.open(args.vcard, 'w', 'utf-8') as vcard:
        contacts = parse_database(args.database)
        for i, contact in enumerate(contacts):
            sys.stderr.write("\rexporting contact %s of %s" % (i+1, len(contacts)))
            card = generate_vcard(contact, args.photos)
            print >> vcard, card
            sys.stderr.flush()
        sys.stderr.write("\n")

if __name__ == "__main__": main()

It just goes through each row, grabs the relevant data, and writes it out in vCard format.

To use the script, just run python fbcontacts.py /path/to/fb.db. You’ll end up with all of your contacts in a vCard file, complete with email addresses, phone numbers, birthdays, and (if you specify the --photos flag) profile pictures.

Conclusion

Restrictions don’t apply to those with rooted phones and a bit of curiosity.

A while back, I wrote about streaming music with Ampache. Ampache is a nice piece of software, with some unique advantages (like Android support). However, there are simpler ways to stream music. I’m going to show you how to stream music using sshfs and (optionally) mp3fs. One of the best things about this approach is that it allows you to access your collection with the media player of your choice.

Before you start, you’re going to need a Linux machine with your music collection on it (the server). You will also need another Linux machine to act as the client (e.g. a laptop with a small hard drive).

Configuring the server

Install the ssh server

The first thing you’re going to want to do is install an ssh server, if it’s not already installed.

$ sudo aptitude install openssh-server

If your music is already compressed, or if you just have a very fast internet connection, you’re done configuring the server. Otherwise, read on to learn how to transcode your music on-the-fly with mp3fs.

Set up mp3fs

MP3FS is a read-only FUSE filesystem which transcodes audio formats (currently FLAC) to MP3 on the fly when opened and read. This was written to enable me to use my FLAC collection with software and/or hardware which only understands the MP3 format e.g. gmediaserver to a Netgear MP101 MP3 player. — Kristofer Henriksson

If you have any music in FLAC format, you’re probably not going to be able to stream it without first transcoding to MP3. mp3fs solves this problem. First, install it.

$ sudo aptitude install mp3fs

NOTE: Depending on your distro, the repositories might have an outdated version of mp3fs. If the following commands don’t work, try installing a newer version of mp3fs (either by compiling it yourself or finding a newer package).

Now that it’s installed, we’ll set it up. Create a folder for the mp3fs:

$ mkdir ~/MP3

Next, add an entry to /etc/fstab to automatically mount the mp3fs:

# cat >> /etc/fstab << EOF
mp3fs#/home/USER/Music /home/USER/MP3 fuse allow_other,ro,bitrate=320 0 0
EOF

Make sure you adjust the paths and bitrate, if necessary.

Finally, mount the mp3fs:

$ sudo mount -a

Now your music collection should appear at ~/MP3 in MP3 format.

Configuring the client

We’re going to use sshfs to stream the music. It uses SSH to allow you to mount remote filesystems on the local machine. In other words, it will make your remote music collection available on the client machine. To start, install sshfs.

$ sudo aptitude install sshfs

Now, mount the remote music collection (adjust the parameters as necessary):

$ sshfs USER@example.com:Music ~/Music

Your music collection should now be visible on the client at ~/Music. Fire up your favorite media player, allow it to scan your music library, and enjoy.

If you want the sshfs to be automatically mounted, you will first need to set up key-based SSH authentication. Once that’s done, you will need to edit /etc/fstab:

# cat >> /etc/fstab << EOF
sshfs#USER@example.com:Music /home/USER/Music fuse defaults,idmap=user 0 0
EOF

Now your music collection will be available at login.

A couple months ago, I decided to expand my knowledge of artificial intelligence by participating in the 2011 AI Challenge. It was an incredibly interesting and educational experience. Sadly, I was forced to divert my attention away from the AI Challenge to focus on more important things.

One of the more interesting things I learned from the AI Challenge was an A* algorithm which supports searching from multiple sources to multiple targets, simultaneously. I used this algorithm to efficiently gather food: one pass of this algorithm calculated paths to each food tile.

The algorithm is similar to the basic A*, except for a few key differences. First of all, the frontier is prepopulated with all of the sources. Secondly, the goal test function checks to see if the current position corresponds to any of the targets, not just a single target. Finally, the heuristic is the Manhattan distance to the nearest target.

This is the algorithm in pseudocode:

frontier = {sources}
explored = {}
loop:
    if frontier is empty: return
    path = remove_choice(frontier) # minimize f + h where h = distance to nearest target
    s = path.end
    add s to explored
    if s in targets: command source to follow path
    for a in actions:
        add [path + a -> Result(s, a)] to frontier
            unless Result(s, a) in frontier + explored

I’ve uploaded my bot to GitHub, so you can actually see this algorithm in practice if you want.

Introduction

I’ve been intrigued by the concept of using computers to generate audio for a long time. It turns out that you can generate audio with nothing but the standard library of Python.

The approach I used relies heavily on the itertools module. Essentially, I use itertools to create infinite generators and then take some data from these generators to produce the audio. The resultant sequence of floats in the range [-1.0, 1.0] is converted to 16 bit PCM audio (i.e., a sequence of signed 16 bit integers in the range [-32767, 32767]) and then written to a .wav file using the wave module.

If you’re not familiar with iterators and the itertools module, this post may be somewhat hard to follow. itertools really opens up some interesting possibilities in Python, making it more like Lisp or Haskell. In truth, if you’re relying on itertools as much as I am in this post, you might as well just use Lisp or Haskell and receive a nice performance boost. The reason I didn’t is quite simply because I wanted to generate some audio in Python.

To follow the code examples below, you probably need to perform the following imports:

import sys
import wave
import math
import struct
import random
import argparse
from itertools import *

Generating Waves

You may remember from your physics class that sound consists of waves. Many instruments produce tones that are basically a combination of pure sine waves. Thus, we need a way to produce sine waves if we want to generate audio. My first approach was something like this:

def sine_wave(frequency=440.0, framerate=44100, amplitude=0.5):
    if amplitude > 1.0: amplitude = 1.0
    if amplitude < 0.0: amplitude = 0.0
    return (float(amplitude) * math.sin(2.0*math.pi*float(frequency)*(float(i)/float(framerate))) for i in count(0))

This computes a sine wave of infinite length at the specified frequency, and returns an infinite generator which samples the wave 44,100 times per second.

The problem with this approach is that it is inefficient. Sine waves are periodic functions, meaning that they repeat themselves after a certain period. This means that we can pre-calculate the function for one period, and then return an iterator which simply cycles these pre-computed values indefinitely:

def sine_wave(frequency=440.0, framerate=44100, amplitude=0.5):
    period = int(framerate / frequency)
    if amplitude > 1.0: amplitude = 1.0
    if amplitude < 0.0: amplitude = 0.0
    lookup_table = [float(amplitude) * math.sin(2.0*math.pi*float(frequency)*(float(i%period)/float(framerate))) for i in xrange(period)]
    return (lookup_table[i%period] for i in count(0))

This resulted in a substantial performance improvement on my machine, but this is Python after all so a discussion of performance is perhaps a moot point.

Generating Noise

Sometimes you want to generate noise. The simplest kind of noise is called white noise, which is completely random audio data.

def white_noise(amplitude=0.5):
    return (float(amplitude) * random.uniform(-1, 1) for _ in count(0))

The main downside to this approach is that random values need to be calculated 44,100 times per second. Using the itertools module, we can pre-calculate one second of white noise, and then just cycle that data:

noise = cycle(islice(white_noise(), 44100))

Combining Functions

As I mentioned earlier, complex sounds can be modeled as combinations of pure sine waves. If you’re generating a stereo audio file, you can have different audio functions in each channel. The way I chose to represent this concept is as follows:

c1 = (f1, ..., fn)
c2 = (f1, ..., fn)
channels = (c1, c2)

c1 is the left channel, c2 is the right channel. Each channel is an iterable containing the functions that comprise that channel. All channels are then combined into a single iterable, channels.

If you play the same sound through both channels of a stereo audio file, the sound will seem to come from the center of the soundstage.

channels = ((sine_wave(440.0),),
            (sine_wave(440.0),))

You can also control the location of the sound by altering the amplitude of the waves. This example will make a 440.0 Hz sine wave which is slightly left of center:

channels = ((sine_wave(440.0, amplitude=0.5),),
            (sine_wave(440.0, amplitude=0.2),))

Additionally, you can have more than one function playing at the same time. Here’s an example of a 200.0 Hz tone in the left channel, a 205.0 tone in the right channel, and some white noise in the background:

channels = ((sine_wave(200.0, amplitude=0.1), white_noise(amplitude=0.001)),
            (sine_wave(205.0, amplitude=0.1), white_noise(amplitude=0.001)))

That’s a binaural beat.

Computing Samples

Recall from your physics class that waves combine with each other to produce new waves. We can compute this new wave by simply adding the waves together.

Now that we have defined the audio channels, we need to compute the sum of the functions in the channel at each sample in the file. Since our waves are represented as generators, we want to create a new generator which calculates the sum of each sample in the input generators. Essentially we want a function that accepts audio channels in the format described above and returns a generator which yields tuples where element 0 is the sum of the functions in the left channel at that point, and element 1 is the sum of the functions in the right channel at that point.

This calls for use of the imap and izip functions.

def compute_samples(channels, nsamples=None):
    return islice(izip(*(imap(sum, izip(*channel)) for channel in channels)), nsamples)

Note that if nsamples is specified, we return a sequence of finite length (using the islice function). Otherwise, we return a sequence of infinite length. Since we are using iterators, sequences of infinite length can be represented more or less elegantly and efficiently.

Writing a Wavefile

The next step is to use the wave module to create a .wav file. The first thing to do is to generate the wave header, which is some information at the beginning of the wavefile that describes the contents of the file. The information we need to generate this header is as follows:

• nchannels - the number of channels contained in the file. For stereo, this is 2.
• sampwidth - the size of each sample, in bytes. Recall that a byte is 8 bits, so for 16 bit audio this is 2.
• framerate - the number of samples per second. I usually set this to 44100 (CD quality).
• nframes - the total number of samples to write. This is equal to the framerate multiplied by the duration of the file in seconds.

To open a wavefile for writing with the wave module, do this:

w = wave.open(filename, 'w')
w.setparams((nchannels, sampwidth, framerate, nframes, 'NONE', 'not compressed'))

The 'NONE' and 'not compressed' just indicate that we are creating an uncompressed wavefile (nothing else is supported by the wave module at the time of writing).

Now the wavefile is ready for our audio data. 16 bit audio is encoded as a series of signed 16 bit integers. The first thing to do is to scale our sequence of floats in the range [-1.0, 1.0] to signed 16 bit integers (in the range [-32767, 32767]). For example:

max_amplitude = 32767.0
samples = (int(sample * max_amplitude) for sample in samples)

We’re writing a binary format, so we need the struct module to convert our audio data to the correct binary encoding. Specifically, we need the struct.pack function. The struct.pack function uses format strings to designate how to pack the data. A signed 16 bit integer is also known as a signed short, so we want to use the format string ‘h’ (the format string for a signed short). Thus, to pack the integer 1000 into a signed short:

struct.pack('h', 1000)

Now, we are going to be creating stereo audio files, so we need to consider how .wav files represent multiple channels. It turns out that .wav files look something like this:

L1R1L2R2L3R3L4R4

Where L1 is the first sample in the left channel, R1 is the first sample in the right channel, and so on. In other words, the channels are interleaved.

Finally, we want to keep performance in mind. On one extreme, we write data to the file every time we compute a sample. This is memory-efficient, but incurs a severe performance penalty due to the overhead of writing to the file. On the other extreme, we pre-compute the entire file and write all of the samples at once. This does not incur the aforementioned performance penalty, but it has two major problems. First, it requires a huge amount of memory, since the entire .wav file will be loaded into memory. Second, it means you can’t stream the audio as it is generated, which means you can’t play the audio in realtime (by writing to stdout and piping to aplay, for example).

Thus, we take the third approach: buffer chunks of the audio stream and write each chunk as it is computed. This offers the advantages of both techniques.

So, putting all of this together, we end up with something like this:

def grouper(n, iterable, fillvalue=None):
    "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx"
    args = [iter(iterable)] * n
    return izip_longest(fillvalue=fillvalue, *args)

def write_wavefile(filename, samples, nframes=None, nchannels=2, sampwidth=2, framerate=44100, bufsize=2048):
    if nframes is None:
        nframes = -1

    w = wave.open(filename, 'w')
    w.setparams((nchannels, sampwidth, framerate, nframes, 'NONE', 'not compressed'))

    max_amplitude = float(int((2 ** (sampwidth * 8)) / 2) - 1)

    # split the samples into chunks (to reduce memory consumption and improve performance)
    for chunk in grouper(bufsize, samples):
        frames = ''.join(''.join(struct.pack('h', int(max_amplitude * sample)) for sample in channels) for channels in chunk if channels is not None)
        w.writeframesraw(frames)

    w.close()

    return filename

wavebender

I have compiled these techniques and a few others into a module called wavebender. Here’s the current source code (at the time of writing), but you can always find the latest at https://github.com/zacharydenton/wavebender.

#!/usr/bin/env python
import sys
import wave
import math
import struct
import random
import argparse
from itertools import *

def grouper(n, iterable, fillvalue=None):
    "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx"
    args = [iter(iterable)] * n
    return izip_longest(fillvalue=fillvalue, *args)

def sine_wave(frequency=440.0, framerate=44100, amplitude=0.5):
    '''
    Generate a sine wave at a given frequency of infinite length.
    '''
    period = int(framerate / frequency)
    if amplitude > 1.0: amplitude = 1.0
    if amplitude < 0.0: amplitude = 0.0
    lookup_table = [float(amplitude) * math.sin(2.0*math.pi*float(frequency)*(float(i%period)/float(framerate))) for i in xrange(period)]
    return (lookup_table[i%period] for i in count(0))

def square_wave(frequency=440.0, framerate=44100, amplitude=0.5):
    for s in sine_wave(frequency, framerate, amplitude):
        if s > 0:
            yield amplitude
        elif s < 0:
            yield -amplitude
        else:
            yield 0.0

def damped_wave(frequency=440.0, framerate=44100, amplitude=0.5, length=44100):
    if amplitude > 1.0: amplitude = 1.0
    if amplitude < 0.0: amplitude = 0.0
    return (math.exp(-(float(i%length)/float(framerate))) * s for i, s in enumerate(sine_wave(frequency, framerate, amplitude)))

def white_noise(amplitude=0.5):
    '''
    Generate random samples.
    '''
    return (float(amplitude) * random.uniform(-1, 1) for i in count(0))

def compute_samples(channels, nsamples=None):
    '''
    create a generator which computes the samples.

    essentially it creates a sequence of the sum of each function in the channel
    at each sample in the file for each channel.
    '''
    return islice(izip(*(imap(sum, izip(*channel)) for channel in channels)), nsamples)

def write_wavefile(filename, samples, nframes=None, nchannels=2, sampwidth=2, framerate=44100, bufsize=2048):
    "Write samples to a wavefile."
    if nframes is None:
        nframes = -1

    w = wave.open(filename, 'w')
    w.setparams((nchannels, sampwidth, framerate, nframes, 'NONE', 'not compressed'))

    max_amplitude = float(int((2 ** (sampwidth * 8)) / 2) - 1)

    # split the samples into chunks (to reduce memory consumption and improve performance)
    for chunk in grouper(bufsize, samples):
        frames = ''.join(''.join(struct.pack('h', int(max_amplitude * sample)) for sample in channels) for channels in chunk if channels is not None)
        w.writeframesraw(frames)

    w.close()

    return filename

def write_pcm(f, samples, sampwidth=2, framerate=44100, bufsize=2048):
    "Write samples as raw PCM data."
    max_amplitude = float(int((2 ** (sampwidth * 8)) / 2) - 1)

    # split the samples into chunks (to reduce memory consumption and improve performance)
    for chunk in grouper(bufsize, samples):
        frames = ''.join(''.join(struct.pack('h', int(max_amplitude * sample)) for sample in channels) for channels in chunk if channels is not None)
        f.write(frames)

    f.close()

    return filename

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument('-c', '--channels', help="Number of channels to produce", default=2, type=int)
    parser.add_argument('-b', '--bits', help="Number of bits in each sample", choices=(16,), default=16, type=int)
    parser.add_argument('-r', '--rate', help="Sample rate in Hz", default=44100, type=int)
    parser.add_argument('-t', '--time', help="Duration of the wave in seconds.", default=60, type=int)
    parser.add_argument('-a', '--amplitude', help="Amplitude of the wave on a scale of 0.0-1.0.", default=0.5, type=float)
    parser.add_argument('-f', '--frequency', help="Frequency of the wave in Hz", default=440.0, type=float)
    parser.add_argument('filename', help="The file to generate.")
    args = parser.parse_args()

    # each channel is defined by infinite functions which are added to produce a sample.
    channels = ((sine_wave(args.frequency, args.rate, args.amplitude),) for i in range(args.channels))

    # convert the channel functions into waveforms
    samples = compute_samples(channels, args.rate * args.time)

    # write the samples to a file
    if args.filename == '-':
        filename = sys.stdout
    else:
        filename = args.filename
    write_wavefile(filename, samples, args.rate * args.time, args.channels, args.bits / 8, args.rate)

if __name__ == "__main__":
    main()

You can execute the file directly and it will generate a pure sine tone.

Examples

SBaGen

SBaGen is a program which generates binaural beats. It’s reasonably complex, consisting of around 3000 lines of C. You can instruct SBaGen to generate a 200Hz pure sine tone in one channel and a 204Hz pure sine tone in the other channel by doing this:

$ sbagen -i 202+2/10

You can also generate multiple binaural beats simultaneously:

$ sbagen -i 202+2/10 400+20/10

The following emulates sbagen -i, but it’s about 100x slower. No problem for real-time use on a modern computer, but you’re better off using the real deal for serious use.

#!/usr/bin/env python
import re
import sys
from wavebender import *
from itertools import *

def sbagen_phrase(phrase):
    '''
    147.0+4.0/1.27 -> two sine_waves. one 145.0 hz; one 149.0 hz. each at amplitude of 0.0127.
    '''
    if 'pink' in phrase:
        # pink/40 -> white_noise(amplitude=0.4)
        amplitude = float(phrase.split('/')[-1]) / 100.0
        return (white_noise(amplitude),
                white_noise(amplitude))

    carrier, remainder = re.split('[+-]', phrase, 1)
    beatfreq, amplitude = remainder.split('/')

    carrier = float(carrier)
    beatfreq = float(beatfreq)
    amplitude = float(amplitude) / 100.0

    return (sine_wave((carrier - beatfreq/2), amplitude=amplitude),
            sine_wave((carrier + beatfreq/2), amplitude=amplitude))

def sbagen_line(line, length=None):
    '''
    Given a sequence of (l, r), (l, r), return a sequence of (l, l), (r, r).
    '''
    return izip(*(imap(lambda s: islice(s, length), sbagen_phrase(phrase)) for phrase in line.split()))

if sys.argv[1:]:
    channels = sbagen_line(' '.join(sys.argv[1:]))
else:
    sys.exit(1)

samples = compute_samples(channels)
write_wavefile(sys.stdout, samples)

You can use it like this:

$ ./sbagen.py 272.2+7.83/10 332+7.83/10 421.3+7.83/10 289.4+7.83/10 367.5+7.83/10 442+7.83/10 295.7+7.83/10 414.7+7.83/10 422+7.83/10 | aplay

That generates a bunch of simultaneous binaural tones and uses aplay to play them in realtime.

Melody

Here’s an example of a melody, using itertools and wavebender.

#!/usr/bin/env python
from wavebender import *
from itertools import *
import sys

def ncycles(iterable, n):
    "Returns the sequence elements n times"
    return chain.from_iterable(repeat(tuple(iterable), n))

def waves():
    l = int(44100*0.4) # each note lasts 0.4 seconds

    return cycle(chain(ncycles(chain(islice(damped_wave(frequency=440.0, amplitude=0.1, length=int(l/4)), l),
                                     islice(damped_wave(frequency=261.63, amplitude=0.1, length=int(l/4)), l),
                                     islice(damped_wave(frequency=329.63, amplitude=0.1, length=int(l/4)), l)), 3),
                       islice(damped_wave(frequency=440.0, amplitude=0.1, length=3*l), 3*l),

                       ncycles(chain(islice(damped_wave(frequency=293.66, amplitude=0.1, length=int(l/4)), l),
                                     islice(damped_wave(frequency=261.63, amplitude=0.1, length=int(l/4)), l),
                                     islice(damped_wave(frequency=293.66, amplitude=0.1, length=int(l/4)), l)), 2),
                       chain(islice(damped_wave(frequency=293.66, amplitude=0.1, length=int(l/4)), l),
                             islice(damped_wave(frequency=329.63, amplitude=0.1, length=int(l/4)), l),
                             islice(damped_wave(frequency=293.66, amplitude=0.1, length=int(l/4)), l)),
                       islice(damped_wave(frequency=261.63, amplitude=0.1, length=3*l), 3*l)))

channels = ((waves(),), (waves(), white_noise(amplitude=0.001),))

samples = compute_samples(channels, None)
write_wavefile(sys.stdout, samples, None)

Conclusion

Well, there’s your daily abuse of itertools. For more itertools madness, check out my Project Euler Solutions.

This guide will teach you how to unleash your music collection. Access it from anywhere with an internet connection – on your laptop, your phone, at work, or on a plane.

This guide has three parts. Part one tells you how to build a server for less than $300. Part two discusses how to build a music collection. Part three discusses how to stream that collection across the internet.

If you already have a computer that is connected to the Internet 24/7, you can skip part one.

Part One: Building a Server

We will need a computer to use as the server. You have three options here:

1. Re-use an old computer. The cheapest option.
2. Purchase a new computer. The easiest option.
3. Build a new computer. The educational option.
4. Purchase a VPS. Potentially the best option, with a few caveats (more details below).

If you chose option 3, read the following section. Otherwise you can skip past it.

Building a new computer

The first thing to do when building a new computer is to come up with a parts list. It turns out that there are only six things you need to build a computer:

• CPU (aka processor)
• Motherboard
• RAM (aka memory)
• Storage drive(s)
• Power supply
• Case

Seasoned builders will be quick to point that there are a plethora of additional parts that can be used to build a computer. Expert builders will be even quicker to point out that you don’t even need a case or storage drives. For the purposes of this guide, however, I will focus on the six aforementioned parts. What follows is a list of the six parts I used to build my media server. They will most likely be out of date by the time you read this – just use them as an example.

CPU: AMD Athlon II X2 250 ($60.99)

You don’t need a super-powerful processor in your server. That said, this processor packs an astonishing punch at 60 bucks.

Motherboard: Gigabyte GA-MA74GM-S2 740G ($54.99)

I’m really pleased with this motherboard. It’s very small (Micro ATX), yet it comes with a ton of features like onboard video, gigabit ethernet, sound, and the ability to upgrade to a discrete graphics card if desired.

If you use this motherboard (or similar), your media server will be able to perform double-duty as a media center if you hook it up to your TV. Expect to see another guide explaining how to do this in the future.

RAM: A-DATA 2GB DDR2-800 ($32.99)

Just some basic, cheap DDR2 RAM. Works well (did I mention it was cheap?).

Storage drive: Samsung Spinpoint F4 2TB 5400 RPM ($79.99)

You’re going to want a large drive in your media server to store your music collection. 2TB for 80 bucks is just an incredible deal. Less than three years ago I paid the same price for 10% of that.

Power supply: Logisys 575W ($24.99)

Normally I use high-end power supplies when building computers, so I was a bit wary of using this $25 power supply. It was substantially lighter than I am used to (heftier power supplies are typically higher-quality), but so far it has performed admirably.

Case: Apex TX-381-C Micro ATX Tower ($29.99)

It’s a solid case. Very inexpensive. Somewhat loud.

That’s a grand total of around 280 bucks for a great server. Today you can probably get an even better machine for the same price or less.

Once you have all of the parts, you will need to put them together. Check out How To Assemble A Desktop PC, a great wikibook teaching you how to do that.

Setting up the server

Now that you have a machine to use as your media server, you will need to install Linux on it. The version (or “distro”) I recommend is Ubuntu Server Edition. Take a look at the Ubuntu Server Guide. which will teach you everything you need to know.

You’re going to want to set up SSH access to your machine so that you can manage it remotely. You can find the details in the OpenSSH section of the Ubuntu Server Guide.

The final thing you need to do is to hook your new server up to the Internet. For streaming 320kbps music files, I recommend having a minimum upload bandwidth of around 384kbps (50KB/s). That’s what I used to have, and occasionally I had to reduce the streaming rate to 192kbps to eliminate stuttering. Miraculously my ISP increased my upload bandwidth to around 1mbps, for free (as far as I know). That’s more than enough for streaming music.

A note on VPSs

If you opt to use a VPS, you don’t have to worry about setting up a Linux server with a 24/7 high speed internet connection. What you do need to worry about is violating your hosting provider’s Terms of Service. They may not appreciate you downloading and streaming music on their servers.

The other thing is that you likely won’t have unlimited disk space, even if you do have “Unlimited Disk Space!”. I would think twice before uploading a 400GB FLAC collection to a VPS.

If you can deal with these two conditions, then using your VPS as a media server is probably the best way to go. You get an extremely fast connection and you don’t have to worry as much about maintaining the server.

Part Two: Building a music collection

What good is a music server without any music? That’s a problem that this section of the guide intends to solve. There are a lot of ways to get music these days: iTunes, purchasing directly from the artist, BitTorrent, and even purchasing from a store. For simplicity, I’m just going to focus on BitTorrent. If you don’t know what BitTorrent is, you may want to read this introduction first.

This section of the guide will teach you how to access and use the best music repositories in the world (for free).

Installing the BitTorrent client

You may be familiar with Transmission – it’s an excellent, easy-to-use BitTorrent client for Windows, Mac, and Linux. Transmission can also run in the background, as a daemon. This is called transmission-daemon. transmission-daemon comes with a beautiful web interface which you will be using to manage your torrents from anywhere in the world.

To install transmission-daemon on Ubuntu, ssh into your server and type the following:

$ sudo aptitude install transmission-daemon

First we make sure that transmission-daemon is not running:

$ sudo /etc/init.d/transmission-daemon stop

Now you want to configure transmission-daemon, so do:

$ sudo $EDITOR /etc/transmission-daemon/settings.json

You want to make the following changes:

"rpc-whitelist-enabled": false,
"rpc-username": "your-username",
"rpc-password": "your-password",

This allows you to access transmission-daemon remotely, as long as you specify the correct username and password.

Finally, we restart transmission-daemon:

$ sudo /etc/init.d/transmission-daemon start

Now you can log in to the transmission-daemon web interface by pointing your web browser to http://your-server:9091/. Once you’ve logged in, you should see a nice interface where you can manage torrents and edit preferences. This is how you’ll be interacting with transmission-daemon most of the time.

What we need now is some torrents to download!

Finding music for your collection

I usually find new music based on recommendations from friends or Last.fm. Last.fm is a service which monitors your listening habits and then provides recommendations based on that data. It’s pretty cool, and it makes it easier to answer “So, what kind of music do you like?” with something other than “Oh, I listen to a little bit of everything.”.

Once you have some candidates for adding to your collection, you need to actually get your hands on the files. To do this, we use a BitTorrent search engine. The three that I use are (ranked from decent to best):

• The Pirate Bay
• Demonoid
• What.CD

The Pirate Bay

Most BitTorrent users will be familiar with The Pirate Bay. It’s one of the largest BitTorrent sites and certainly the most infamous. They offer a fair amount of music, probably enough for the casual user. There are no real quality standards here so you may have to search a bit before finding the good stuff. The Pirate Bay does not require registration.

Demonoid

Demonoid is similar to The Pirate Bay in that it offers a wide range of content. I often find that if something isn’t on TPB, it’s on Demonoid (and vice versa). Demonoid requires registration, but it’s not difficult to get in.

What.CD

What.CD is the holy grail for music enthusiasts. It is indisputably the greatest music collection ever assembled. If you’re lucky enough to get in, you will have access to pretty much every release of every album in any format you could want. They maintain their high quality by maintaining a high quality userbase, so if you want to get in you have two options: get an invite or pass an interview.

A brief digression on formats

There are two kinds of music formats: lossy and lossless.

MP3, AAC, and OGG are all lossy formats, meaning that they discard some of the audio data in order to achieve smaller file sizes. Lossy formats are prevalent on public trackers like The Pirate Bay.

FLAC is a lossless format, meaning that it preserves all of the original audio data. As you build your music collection, you will learn more and more about FLAC. My collection consists solely of FLACs. One cool thing about FLAC that relates to this guide is that you can convert it to a lossy format on-the-fly for streaming over the internet – useful if you have a slow connection.

Part three: Serving your music collection over the Internet

To stream your music over the Internet we will be using something called Ampache. The name is a portmanteau of the words Amp (as in amplifier) and Apache (the prominent web server).

Ampache provides a web interface to your music collection. You use the interface to create playlists. The playlists can then be played in the browser or opened in your favorite standalone media player. There are also Ampache clients for Android and iPhone, so you can access your full music collection on your phone. Additionally, Ampache can transcode your music on-the-fly to any format (useful for streaming to devices with slower internet connections).

Installing Ampache

Ampache is included in the Ubuntu repositories. Just do:

$ sudo aptitude install ampache mysql-server

And the required programs will be installed for you. When asked which web server to configure automatically, select apache2. When asked to restart the web server, select “Yes”. Choose the root password for your MySQL server and remember it.

At this point, try navigating to http://your-server/ampache/. If the page is not found, do the following:

$ sudo $EDITOR /etc/apache2/apache2.conf

Add the following to the bottom of that file:

Include /etc/ampache/ampache.conf

Restart the web server:

$ sudo /etc/init.d/apache2 restart

Now, open http://your-server/ampache/ in a web browser. You will see a webpage entitled ‘Ampache Installation’. Click on ‘Start configuration’ near the bottom of the page.

On the next page, enter the MySQL root password in the ‘MySQL Administrative Password’ box. Then click ‘Insert Database’.

On this page, type ‘root’ into the ‘MySQL Username’ box. The ‘MySQL username’ is the MySQL root password you entered on the previous page. Click ‘Write Config’ and you will be prompted to download an ampache.cfg.php file. Save this file to your local machine.

Configuring Ampache

Make the following changes to ampache.cfg.php:

xml_rpc: "true"
allow_zip_download: "true"
transcode_m4a: "false"

If you would like to transcode your FLACs on-the-fly, make the following change:

transcode_flac: "true"

If you have multiple formats of each album (e.g. if you download albums in MP3, OGG, AAC, and FLAC), each format will be indexed. To eliminate these duplicates, you can opt to only index one of these formats. To only index FLAC:

catalog_file_pattern: "flac"

When you’ve finished editing ampache.cfg.php, copy it to the /etc/ampache directory on your server:

$ scp /path/to/ampache.cfg.php root@your-server:/etc/ampache/

Once ampache.cfg.php is in place on your server, click ‘Check for Config’. Both ‘Ampache.cfg.php Exists’ and ‘Ampache.cfg.php Configured?’ should now say ‘OK’. Click ‘Continue to Step 3’.

Finally, setup the administrator account. Once you’ve filled out the form, click ‘Create Account’.

Login to your Ampache installation as the administrator. We will now configure Ampache to scan your music collection.

On the menu at the left of the page, click the ‘Admin’ icon (looks like a small server). Then click ‘Add a Catalog’.

The catalog name can be anything you like. ‘Path’ should be set to to the path of your music location. If you are using transmission-daemon and would like all of its downloads to be indexed, use /var/lib/transmission-daemon/downloads/. Then click ‘Add Catalog’.

Once your music collection has been indexed, click ‘Continue’. Now click on the ‘Preferences’ icon in the menu on the left of the page.

If you have opted to transcode FLACs on-the-fly, click on ‘Streaming’ and set your ‘Transcode Bitrate’ to something more reasonable, like 320. Click ‘Update Preferences’ and you’re done.

Using Ampache

Now you’re ready to use Ampache. Using Ampache is basically a two-step process. First you queue some music into a playlist. Then you open that playlist in a media player which handles the streaming for you.

Queueing Music

Click on the “Home” icon in the menu on the left. Click on “Albums” to view a list of your albums. If you click the green plus icon next to any album title, it will be loaded into your playlist. You’ll see the tracks in the playlist view on the right side of the screen.

Opening the playlist

Now that you have some music in the playlist, click the “Play” icon (looks like a broadcast tower) located above the playlist on the right side of the screen. You will be prompted to download a playlist file. Download it and open it with the media player of your choice – Totem or VLC for example. You should hear some music. Enjoy!

Conclusion

Hopefully you now have enough information to build a killer media server. I covered a lot of ground in this guide, so feel free to ask any questions you may have.

Background

I’m working on a Django project which deals with geographic data. To handle this data, I’m using GeoDjango (django.contrib.gis), which is a fantastic framework for working with GIS information in Django. The data I am using consists of points scattered across the Earth, so I decided to store the geographic information in the WGS84 datum (SRID 4326), the system used by GPS.

The problem is that since WGS84 is a geographic coordinate system, as opposed to a projected coordinate system, GeoDjango returns the Cartesian distance between points as a float value in degrees. This is not useful for presenting to users, since we deal with kilometers and miles in everyday life. The distance we want is known as the geodesic distance.

Geodesic Distance

Geodesic distance refers to the distance between two points if you were to travel between them on the Earth’s surface. Thus, it is the ‘real’ distance between two points, as opposed to the theoretical distance returned by GeoDjango.

The formulae used to calculate this distance are quite complex. Luckily, they have been implemented for us in a Python module called geopy. The specific method we will be using is known as Vincenty’s method. It’s accurate to within 0.5mm!

The specific function is geopy.distance.distance. Here’s a simple example demonstrating its use:

>>> from geopy.distance import distance as geopy_distance
>>> washington = (38.53, 77.02)
>>> chicago = (41.50, 87.37)
>>> d = geopy_distance(washington, chicago)
>>> print d.meters
942408.377797
>>> print d.miles
585.585417063

Notice how converting between different units of measure on the resultant Distance object is as simple as accessing different attributes of that object (in this case, meters and miles).

Solution

In the example below, we have a Route object which can be associated with an arbitrary number of waypoints. Since the geopy distance function only works on two points, we use the itertools module to take the points pairwise so that we can calculate the distance for each pair and find the sum of the distances. Once we have calculated the geodesic distance with geopy and itertools, we turn it into a GeoDjango Distance object, which allows us to seamlessly convert to several different kinds of units as well as interface with the rest of GeoDjango’s spatial query functions.

Here’s an example models.py which demonstrates this approach:

from itertools import tee, izip

from django.contrib.gis.db import models
from django.contrib.gis.measure import Distance

from geopy.distance import distance as geopy_distance

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

# Create your models here.
class Route(models.Model):
    name = models.CharField(max_length=100)

    def length(self):
        '''Determine the length of the route.'''
        points = (waypoint.point for waypoint in self.waypoint_set.orderby('time'))
        meters = sum(geopy_distance(a, b).meters for (a, b) in pairwise(points))
        return Distance(m=meters)

class Waypoint(models.Model):
    time = models.DateTimeField()
    route = models.ForeignKey(Route)
    point = models.PointField(srid=4326)
    objects = models.GeoManager()

def distance(*points):
    '''
    Find the geodesic distance between two or more points.

    If more than two points are specified, the points are assumed
    to be on a route. The total length of this route is
    calculated.

    Returns a django.contrib.gis.measure.Distance object.
    '''
    meters = sum(geopy_distance(a, b).meters for (a, b) in pairwise(points))
    return Distance(m=meters)

def example():
    from django.contrib.gis.geos import Point
    # Calculate the distance to San Franciso from Washington, D.C., via Chicago.
    washington = Point(38.53, 77.02)
    chicago = Point(41.50, 87.37)
    san_francisco = Point(37.47, 122.26)

    d = distance(washington, chicago, san_francisco)
    print "Washington, D.C. -> Chicago -> San Francisco:"
    print "%(miles)0.2f miles, or %(kilometers)0.2f kilometers (or %(fathoms)0.2f fathoms)" % {
            'miles': d.mi,
            'kilometers': d.km,
            'fathoms': d.fathom
    }

>>> import app.models
>>> app.models.example()
Washington, D.C. -> Chicago -> San Francisco:
2458.41 miles, or 3956.42 kilometers (or 2163398.31 fathoms)

The distance function can either be used on its own or as an instance method, as in Route.length(). If you have any questions, feel free to ask in the comments.

Additional Notes

Projected Coordinate Systems

If your data is concentrated in a small area, then you could use a projected coordinate system (such as SRID 32140, for South Texas) to solve the problem.

PostGIS Geography Field Type

Alternatively, you could try storing your data using the PostGIS Geography field type, which performs geodesic calculations instead of Cartesian calculations. The downside with this approach is that it prevents you from using many of the GeoDjango functions. For instance, none of the Spatial Aggregate functions worked, in my testing. Since this is a relatively new PostGIS feature, I expect it to become more usable in the future. Once it does, I recommend using that instead, as it makes more sense to have these kinds of calculations occur seamlessly at the database level.

So you’ve set up a BuddyPress Album+ loop to place BuddyPress Album+ images anywhere on your site. You’re using the built-in template tags to display the images, along with some information about each one. These built-in template tags are great for most purposes, but if you want to display information about the image author, you were previously out of luck.

To fill that void, I’ve written a couple of basic template tags which retrieve information about the author of the current image in the loop. Just add these template tags to the functions.php file in your theme directory, and you will be able to use them right away.

<?php
function bp_album_get_author_userdata() {
        global $pictures_template;
        $author_userdata = get_userdata($pictures_template->picture->owner_id);
        return $author_userdata;
}


function bp_album_get_the_author() {
        $author_userdata = bp_album_get_author_userdata();
        return $author_userdata->display_name;
}
?>

The function bp_album_get_author_userdata() retrieves all of the author information and returns it as an object. See the function reference for get_userdata() for more information about how to use this object.

The second function, bp_album_get_the_author(), works similarly to get_the_author(). It simply returns the display name of the author of the current image in the loop.

I was recently messing around with the dd program to write ISO images to USB drives, instead of wasting DVDs or CDs. The command to do this is as follows:

# dd if=archlinux-2010.05-netinstall-x86_64.iso of=/dev/sdX

Where sdX is the device name of the disk you wish to write the image to.

This is alright if you only have two disks in your computer, where you would almost certainly want to write to /dev/sdb. However, if you have more than two disks, you need to be absolutely sure that you have selected the correct device — choose the wrong disk, and its data will be overwritten by that of the ISO image.

This is precisely what happened to me (twice, in fact!). I thought I was writing to my flash drive but it turned out that I was actually writing to my 1TB external backup drive. Luckily I had the presence of mind to kill the dd process after I realized that the activity light on the flash drive was not blinking, but the 80MB or so of data that was written was enough to destroy the MBR. That’s a big problem because the MBR acts like a map telling the computer where data is located on the drive. Without that map, the drive is useless.

Thankfully, one Christophe Grenier has written a program called TestDisk which scans the raw data of the hard drive and searches for lost partitions. I was able to recover the lost partitions on my drive using this fantastic tool.

It uses a few different methods to recover the lost partitions. First, it quickly scans through the entire hard drive, looking for lost partitions. Then, it gives you the option to perform a deeper search, which inspects the drive more carefully. Finally, it checks if there is a backup MBR on the device, and if so, uses it to replace the lost MBR.

This final option worked for me. Personally, I think this should be the first step performed, as it takes several hours to scan the entire drive twice whereas it presumably takes less than a second to inspect the backup MBR.

Check out this step-by-step guide detailing its use.

Recently, I created a new landing page for Ultralight Backpacking Network. It features a grid of images posted by the site’s users. Ultralight Backpacking Network is using BuddyPress Album+ to manage users’ photo albums, so I needed to figure out a way to display BuddyPress Album+ images anywhere on the site. It turns out that BuddyPress Album+ makes this a relatively easy task. You retrieve the images using a loop, a process familiar to anyone who has modified or created a WordPress theme. Here’s an example of a BuddyPress Album+ loop:

<div id="photos">
<?php bp_album_query_pictures('per_page=5'); ?>
<?php if ( bp_album_has_pictures() ) : ?>
        <ul class="thumb">
        <?php while ( bp_album_has_pictures() ) : bp_album_the_picture(); ?>
                <li>
                        <a href="<?php bp_album_picture_middle_url(); ?>" title="<?php bp_album_picture_title(); ?>">
                                <img src='<?php bp_album_picture_thumb_url() ?>' alt="<?php bp_album_picture_desc(); ?>" />
                        </a>
                </li>
        <?php endwhile; ?>
        </ul> 
<?php endif; ?>
</div>

Notice how similar it is to the WordPress loop. An important thing to remember is that you must first call the function bp_album_query_pictures() before you can start the BuddyPress Album+ Loop. This function initializes the Query object used for the loop. The bp_album_query_pictures() function supports a few different parameters:

• owner_id - This is the numeric ID of the user whose photos you wish to display.
• id - This is the numeric ID of the photo you wish to display. Only used if you wish to display a single photo.
• privacy - Retrieve photos based on privacy settings. Can be one of the following:
  • public - photos visible to everyone
  • members - photos visible to members
  • friends- photos visible to friends of the current user
  • private- photos visible to the current user
  • admin- photos visible to the site administrator
• adjacent- Used to select a photo immediately preceding or succeeding the photo specified by id. Use one of either:
  • next - select the next photo
  • prev - select the previous photo
• orderkey- Specify which field to use to sort the photos. This is one of the following:
  • id - sort by the numeric ID of the photos
  • user_id- sort by the numeric ID of the users who uploaded the photos
  • status- sort based on the status of the photos
• ordersort- Specify the order in which to sort the photos. One of either:
  • ASC - sort in ascending order
  • DESC - sort in descending order
• per_page - The number of photos you would like to display per page. If you want 24 photos, this is where you would specify that.
• offset- Start selecting photos after a certain offset.

Once you’ve started the loop, you have a few different options depending on how you want to display the data. Here are some of the template tags you can use:

• bp_album_picture_title - Prints the title of the image.
• bp_album_picture_desc - Prints the image description.
• bp_album_picture_id - Prints the numeric ID of the image.
• bp_album_picture_url - Prints the URL to the page where the image is located.
• bp_album_picture_original_url - Prints the URL to the original image.
• bp_album_picture_middle_url - Prints the URL to the scaled image.
• bp_album_picture_thumb_url- Prints the URL to the image thumbnail.
• bp_album_adjacent_links - Prints links to the preceding and succeeding albums or images.

There are several other template tags you can use – too many to list here, in fact. For more information, check out includes/bp-album-templatetags.php in the bp-album folder. If you want to display information about the album author, you are going to need a few additional template tags that don’t come with BuddyPress Album+ by default. See this post for more details. That’s enough information to get you up and running with custom BuddyPress Album+ themes.

There are those who would have you believe that every number is interesting. However, there are interesting numbers and then there are interesting numbers. Today I’m going to talk about numbers in the latter category.

Munchausen numbers are numbers with the property that the sum of their digits raised to themselves equals the number itself. I think this is best explained with an example:

3^3 + 4^4 + 3^3 + 5^5 = 3435

I don’t know about you, but I find this extremely interesting! (Come on! You don’t think that’s interesting?) In any case, I decided to write a few different programs to find these numbers.

The basic algorithm I came up with is as follows:

• Separate the number into its constituent digits.
• Find the sum of each digit raised to itself.
• If this sum equals the original number, then it is a Munchausen number.

That’s fairly self-explanatory, right? Let me show you a few different ways to do this.

Ruby

Ruby was the first “real” programming language I learned. Before Ruby, I was writing simple programs on my TI-89, but that doesn’t really count. If you’re wondering, I first learned how to program by reading the excellent Learn to Program, by Chris Pine.

In Ruby, the easiest way to get the digits of a number is simply to convert the number into a string. Once that is established, one simply needs to apply the aforementioned algorithm to each number within a certain limit to find the Munchausen numbers within that limit:

#!/usr/bin/env ruby
# munchausen.rb - finds munchausen numbers

5000.times do |i|
    digits = i.to_s()
    sum = 0
    digits.each_char do |digit|
        digit = digit.to_i()
        sum += digit ** digit
    end
    if sum == i
        puts i.to_s() + " (munchausen)"
    end
end

C

C is great if you need to eke out every last drop of performance from your machine. I wouldn’t think of using it in any other case, though. That being said, it is much easier than assembly language, but come on people – this is the 21st century.

I took a slightly different approach here and used modular arithmetic to extract the digits from the number. To find the least significant digit, we take the remainder when the number is divided by 10. We do this until all digits have been extracted. Then we simply apply the algorithm as in the previous example.

// calculate munchausen numbers
#include <stdio.h>
#include <math.h>

int limit = 5000; // the upper bound of the search

int i;
int main() {
    for (i = 1; i < limit; i++) {
        // loop through each digit in i
        // e.g. for 1000 we get 0, 0, 0, 1.
        int number = i;
        int sum = 0;
        while (number > 0) {
            int digit = number % 10;
            number = number / 10;
            // find the sum of the digits 
            // raised to themselves 
            sum += pow(digit, digit);
        }
        if (sum == i) {
            // the sum is equal to the number
            // itself; thus it is a 
            // munchausen number
            printf("%i (munchausen)\n", i);
        } 
    }
    return 0;
}

Clojure

Clojure is an interesting new language, conceived in 2008. It is a Lisp which targets the Java Virtual Machine, meaning it can make use of any existing Java code whilst being written in a functional style.

Functional programming is an intriguing concept. It seems more theoretical than the imperative style I am used to, but perhaps that is because I am learning the language by reading Structure and Interpretation of Computer Programs.

One thing about Clojure that seems strange to me is the fact that it lacks a standard library. This means that you have to define your own exponentiation function. In this case, I just used a function from the Java standard library.

The other idiosyncrasy I noticed is that in Clojure, converting a char to an int returns the ASCII representation of that char, rather than performing a direct conversion. Thus, we must subtract 48 in order to receive the number itself.

#!/usr/bin/env clojure
(defn ** [x n]
  (. (. java.math.BigInteger (valueOf x)) (pow n)))

(defn raise-to-itself [number]
  (** number number))

(defn digits [number]
  ; convert the number to a string,
  ; and convert each char to an int.
  ;
  ; subtract 48 because casting a char
  ; to an int returns the ASCII
  ; representation of that char.
  (map #(- (int %) 48) (str number))) 

(defn munchausen? [number]
  ; if the sum of the digits raised to
  ; themselves is equal to the number 
  ; itself, then it is a munchausen number.
  (= (apply + (map raise-to-itself (digits number))) number))

(def munchausen (filter munchausen? (range 5000)))
(println munchausen)

Python

Python is easily my favorite language. Everything about it just seems “right”. Of course, this is probably because it is the language I use the most – but then we have a chicken-or-egg scenario, don’t we?

Here’s the program written in Python. I used it to find every Munchausen number less than 500,000,000. After thirty minutes or so of intense computation, it turns out that the only Munchausen numbers are 1 and 3435. Others have posited that 438,579,088 is a Munchausen number, but this is false because 0^0 = 1, at least in most programming languages.

#!/usr/bin/env python3
# calculates munchausen numbers
#
# these are numbers with the property
# that the sum of its digits raised
# to themselves produces the original
# number.

for i in range(5000):
    digits = (int(digit) for digit in str(i))
    if sum(digit ** digit for digit in digits) == i:
        print(i, "(munchausen)")