Fun Problem

Design and write, using ISO C (no C++ or language extentions), an implementation for the following function prototype:

int numcmp(const char *s1, const char *s2);

The function numcmp assumes that both null-terminated strings s1 and s2 contain one or more digits and at most one decimal point ('.'); the result for input strings not of this form is not defined. The function compares the contents of the null-terminated string s1 with the contents of the null-terminated string s2. Using a numerical interpretation for the strings, it returns a value of type int that is less than zero if s1 is less than s2; equal to zero if s1 is equal to s2; and greater than zero if s1 is greater than s2.

The function interface is similar to that of strcmp from the standard C library "string.h". It can be used in place of strcmp when a numeric comparison is needed in place of a lexicographic comparison.

The result of the function should be the same as a comparison of the numerical values of represented by the strings. (Examples: "0" is equal to "000"; "12" is equal to "0012"; "100" is greater than "99"; ".02" is greater than "0.001")

The the comparison should be implemented using only simple character processing. (It should not be implemented using float or double.)

There is no limit on the number of digits in the input strings. The implementation should not impose a restriction on the length of the strings.
Do not use any library functions (including the standard libraries) in your implementation.
Example input strings:


I found this problem in a posting on Joel Spolsky's forums. For some reason this kind of problem really appeals to me, so I decided to implement a solution for fun. I think I created a pretty efficient one (numcmp.cpp).

I really enjoy this kind of challenge as a break from bigger projects. I think because it's pure problem solving and I'm freed from the constant burden of trying to define the problem in addition to then solving it. Sometimes it even results in something useful. But in this case it's just for the fun of the half an hour or so it takes to write.

I remember early into me taking on the formula engine, when I had spent a couple of months doing nothing but fixing bugs and learning the old engine and what not, I took another fun project, implementing the MD5 hashing algorithm in LotusScript. I remember reading a posting in a Notes forum somewhere that an MD5 hashing algorithm in LS would be cool to have. I thought about it and decided it would be cool to write one. I asked my boss, Wai Ki Yip, if he didn't mind me doing a side project for a few days, because I hadn't coded anything significant in what felt like forever. He didn't bat an eye, he said go for it, have fun. And I did.

The first catch in writing the algorithm was the utter lack of bitwise operations in LotusScript. So I had lots of missing bit operations to code as functions in a library. They tended to look like this:

Function BitRotRightL( Byval x As Long, Byval bits As Integer) As Long
'Rotates the bits in a long right by the number specified
'Note: bits must be positive
Const maxbits = 32
bits = bits Mod maxbits
If bits Then
Dim overflowmask As Long
If x And twotothe(bits - 1) Then
overflowmask = &h80000000&
x= x Xor twotothe( bits - 1)
End If
If x And &h80000000& Then
BitRotRightL = ((x And mask( bits)) * twotothe( maxbits - bits)) Or overflowmask Or ((x And &h7FFFFFFF&) \twotothe( bits)) Or twotothe( maxbits- bits -1)
BitRotRightL = ((x And mask( bits)) * twotothe( maxbits - bits)) Or overflowmask Or ((x) \twotothe( bits))
End If
BitRotRightL = x
End If
End Function

So I wrote all the operations necessary and as efficiently as I could. After that, implementing the actually hashing algorithm was pretty easy, I mostly copied the design of a java implementation I found.

As you might imagine, the MD5 hashing ran a little slow :). But it worked and I had fun writing it and apparently people are still using it in production. It only took a few days, but it served to energize me at time when I was feeling frazzled and overwhelmed and give me a boost of confidence during the most challenging project I had ever faced. I'm not sure if Wai Ki saw it that way, or if he just wanted to keep me happy, which I suppose is actually the same thing.

Posted September 4, 2005 6:45 PM