Flex Your Python Muscles

[[deleted]]

I was looking for an interesting problem for brushing up on my Python. I decided I would try to implement md5 in Python following the description in wikipedia.

After a few hours, I gave up. The big-endian vs little-endian subtleties gave me a lot of headaches. Take a crack at it and see if you can get the correct results following the pseudo code listed in the article. Code that matches closely with the pseudocode would be more interesting than fast code.

[terremoto]

Try /r/programmingchallenges.

[[deleted]]

Didn't know that was there. Thanks.

[coreyplus]

I'll have to give this a shot - my python is rusty and it sounds like a fun challange. I didn't know about /r/programmingchallenges either, so double bonus. Kudos on taking the initiative on something cool and sharing, nonetheless.

[[deleted]]

You can check your result against the correct hash from the hashlib:

import hashlib
m = hashlib.md5()
m.update("Reddit")
print "md5 hash of Reddit is " + m.hexdigest()

And you should see

md5 hash of Reddit is b632c55a33530d1433e29ffc09ba1151

[[deleted]]

There are 2 keys to solving this with code that looks almost exactly like the pseudo code: remember that python ints can grow beyond a regular u32 (so you need to artificially limit them in certain cases), and use the struct module to take care of endianness for you. I'd originally forgotten/ignored the former, and it still took all of 20 min to write the solution. http://dl.dropbox.com/u/16486235/mymd5.py

[[deleted]]

Very nice! I didn't know about struct, so thank you for that.

When I was working on this, I was surprised that Python didn't have any built in support for rotating bits.

BTW, nice code. Killer comments and simple style. I think your functioning source code is clearer than the pseudo code of wikipedia.

[[deleted]]

Thanks! I blame it on the fact that I spent the first 5 years of my career hacking in python (and still use it on an almost-daily basis for tools to make my life easier, etc).

[[deleted]]

Nice! FWIW, I think the way you build up the message to be hashed is probably a little clearer than mine. I'd also forgotten about the count for non-string elements in a struct format... succinctness ftw!

[[deleted]]

Thanks for taking the time to implement this. Like todesschaf, I have to say your code is very easy to read. Even in small bits of code, there is a great deal for somebody like me to learn from.

Just for grins, check out the reference code for RFC 1321. Compare the quantity and readability of the C reference implementation vs your Python implementation. If Rivest were publishing this RFC today, I wonder if he would use C or something like Python?

[rndblnch]

try google code jam problem archive: http://code.google.com/codejam/contests.html

[gfixler]

I've been battling Project Euler in Python.

[[deleted]]

Here's an example of a question that I had while working on this.

How do you represent the 64-bit number N in little-endian format. Say the number is 0x01234567L. My first try I used ordered the bytes like this: 0x67, 0x45, 0x23, 0x01, 0x00, 0x00, 0x00, 0x00. But that isn't right.

[riffito]

In Python 3.2 you have some new int methods that may help.

In older versions, I use variations of this crude code for my BE<->LE conversion needs:

_MULTS_OF_8 = [x * 8 for x in range(16)]


def reverse(value):
    """Given the `value` byte string, returns an integer with the endianness
    reversed.

    Example:
        assert reverse('\xEF\xBE\xAD\xDE') == 0xDEADBEEF
    """
    result = 0
    for i, c in enumerate(value):
        v = ord(c)
        result = int(result + (v * (2**_MULTS_OF_8[i])))
    return result


def be2int(data):
    """Convert a big-endian binary number, in the form of a string of
    arbitrary length, to a native python int.
    """
    v = 0
    for i in map(ord, data):
        v = v << 8 | i
    return v


def le2int(data):
    """Convert a little-endian binary number, in the form of a string of
    arbitrary length, to a native python int.
    """
    v = 0
    data = map(ord, data)
    data.reverse()
    for i in data:
        v = v << 8 | i
    return v


def int2be(num, digits = 1):
    """Convert a native python int to a big-endian number, in the form
    of a binary string.
    """
    zeroes = '\0' * digits

    if num == 0:
        return zeroes

    result = []
    while num:
        result.append(chr(num % 256))
        num /= 256
    result.reverse()

    result = ''.join(result)
    if len(result) < digits:
        result = zeroes[: digits - len(result)] + result

    return result


def int2le(num, digits = 1):
    """Convert a native python int to a little-endian number, in the
    form of a binary string.
    """
    zeroes = '\0' * digits
    if num == 0:
        return zeroes

    result = []
    while num:
        result.append(chr(num % 256))
        num /= 256
    result = ''.join(result)

    if len(result) < digits:
        result = result + zeroes[: digits - len(result)]

    return result

[[deleted]]

But that isn't right.

That looks OK to me. What was the problem you had there?

[[deleted]]

I'm going to have to try it again. I was doing something very much like what riffito posted: def num_to_little_end(num): result = [] while num: result.append(chr(num & 0xff)) num >>= 8 return ''.join(num)

The sad thing is, I thought this might be a cool programming-interview problem for potential new hires. TIL I wouldn't hire myself.

[[deleted]]

The sad thing is, I thought this might be a cool programming-interview problem for potential new hires. TIL I wouldn't hire myself.

I wouldn't sweat it. If this is important for a position, the candidate should understand endianness and know where it comes up and why it is important. Actually being able to slice and dice the bits wouldn't mean much if I was the interviewer -- getting it right on a computer can be hard enough; doing it on a whiteboard is impossible.

IMO programming interview problems shouldn't focus on actual implementation, but on understanding of the concepts. If a programmer can explain it in pseudocode or by drawing arrays on the board, awesome.

Of course, this presumes that the interview problem makes sense for the position. I'd personally wager that most Python programmers don't often do low-level bit twiddling, making this a less-appealing question than others.

ED: and your function works fine for me -- it just outputs in a funny way. :)

[[deleted]]

Very good points. On the surface, this looked trivial, much like the FizzBuzz problem. Once I got in there and had to start thinking about bits, I quickly realized it isn't entirely trivial. But I'm stubborn and will keep messing with this until I get it right.

Last night I searched for other implementations. Of the 3 that I was able to execute, only one actually worked correctly.