Sunday, October 13, 2013

SnipMan - the minimalistic snippet manager

Another cute little donationware. This one took about a day to write, and three months to publish... but it's worth it, so check it out: https://github.com/staafl/snipman

Friday, August 9, 2013

Thoughts on component testing

If software testing, we can compare the entire system to a jigsaw puzzle, with each component being a piece. To verify that a piece has the proper shape, we can do one of (at least) three things:

a) check whether it fits in its place,
b) check whether it fits with the pieces around it,
or c) compare it to another piece we already know has the required shape.

Approach a) is exactly standard unit testing - we simulate the proper environment for the piece, using fakes and control flow, and check whether it performs as expected. The challenge is simulating the correct "hole" for the component to fill - it's an exercise in negative space.

Option b) is integration testing. Theoretically speaking, much of it is not mandatory - as long as we've performed the proper unit tests, combinations of components should work as expected, like parts of a mathematical formula; when the number of components involved in a process grows beyond the trivial, we factor it out into separate master components and unit test those at a higher level of abstraction - which however introduces more opportunity for design flaws and excessive architecture.

More importantly, we are imperfect and so are our tests. We are not always capable of creating a perfect representation of the expected environment for our tested components - which, unlike jigsaw puzzle holes is implicit and multi-dimensional. Even well-tested components can be assumed to have undetected rough edges, and as the separate pieces integrate into the larger whole, their entropy multiplies and we risk ending up with an unpredictable system.

In the end, many integration tests serve as sanity checks to make up for deficiencies in our unit-testing code base, as well as to avoid unnecessary design layers.

Option c) would be testing by example, perhaps the topic of a future meditation. Stay tuned...

Wednesday, June 26, 2013

A small victory


Telerik Academy's DSA exam - the 25th of June 2013. Problem description and analysis - coming soon :-)

Friday, May 10, 2013

Flooring numbers with your hands tied

Interesting question on ##csharp@freenode tonight. One of the users was using a system with limited scripting capabilities and needed to write his own floor() function using the very limited set primitives. Basically, if-branching, +, -, *, /, a few math functions (ln, pow, abs) and oddly enough, a distance calculation function for GPS coordinates. The initial reaction of the room, including myself, was along the lines of "sorry, you're screwed." But for some reason the question excited me and I put some more thought into it... hmm, without looping or recursion we've obviously lost Turing-completeness and the problem was probably unsolvable for all inputs, but on the other hand on a logarithmic scale, practical numbers aren't particularly large. What if we tried chopping off decimal digits to get the fractional part? As long as the numbers are bounded, you can throw away the whole part of a number in ~ 9*(log10 bound) operations. Something along the lines of the following C# code:
double GetFractionalPart(double num) {

    // assume num < 1000

    var frac = num;
    if(frac >= 100) {
        frac -= 100;
        if(frac >= 100) {
            if(frac >= 100) {
                frac -= 100;
                    ... // 9 times total
            }
        }
    }

    if(frac >= 10) {
        frac -= 10;
        if(frac >= 10) {
            ...
        }
    }

    if(frac >= 1) {
        frac -= 1;
        if(frac >= 1) {
            ...
        }
    }
}
This method could easily be generated with a script for any desired maximum number of digits. Wait, we can do this for every base... what about binary? 2*(log2 bound) = 2*log2 10*(log10 bound), a clear win in conciseness and ease of generation, not to mention using convenient binary arithmetic:
double GetFractionalPart(double num) {

    var frac = num;
    // ...
    if(frac >= 32) {
        frac -= 32;
    }
    if(frac >= 16) {
        frac -= 16;
    }
    if(frac >= 8) {
        frac -= 8;
    }
    if(frac >= 4) {
        frac -= 4;
    }
    if(frac >= 2) {
        frac -= 2;
    }
    if(frac >= 1) {
        frac -= 1;
    }
    
    return frac;
    
}
This was enough to solve the asker's problem adequately. Hmmm... what if the language in question supported recursion?
double GetFractionalPart(double num) {
    return GetFractionalPart(num, Math.Pow(2,96));
}

double GetFractionalPart(double num, double max) {
    if(num >= max) {
        num -= max;
    }
    if(max > 0) {
        return GetFractionalPart(num, max /= 2);
    }
    else {
        return num;
    }
}
This could easily be written in completely statement-less style:
double GetFractionalPart(double num, double max) {
    max > 0 ? return GetFractionalPart(num >= max ? num - max : num, max /= 2)
            : num;
}
Having extracted the fractional part, getting the job done is trivial:
double Floor(double num) {

    var frac = GetFractionalPart(Math.Abs(num));
    if(num > 0) {
        num -= frac;
    }
    else {
        num += frac;
    }
    return num;
    
}
The person in question wasn't particularly grateful, but it was an interesting challenge nonetheless.

Thursday, May 9, 2013

Code drill 1: Factorial (Part 1)

The idea of this exercise is to come up with as many possible original solutions of a problem. Note that most of the solutions are intentionally terse, and therefore leave something to be desired when it comes to style. Statement: Write a program that calculates N! = N*(N-1)*...*2*1, for non-negative integer N.


Solution 1: straightforward
static int Fact(int n) {
    var ret = 1;
    for(var ii = 2; ii <= n; ++ii) {
        ret *= ii;
    }
    return ret;
}
Solution 2: oneliner
static int Fact(int n) {
    return Enumerable.Range(1,n).Aggregate(1,(x,y) => x*y);
}
Solution 3: recursion
static int Fact(int n) {
    return n == 0 ? 1 : n*Fact(n-1);
}
Solution 4: hidden multiplication
static int Fact(int n) 
{

    var sb = new StringBuilder("*");
    for(var ii = 1; ii < n; ++ii) {
        var str = sb.ToString();
        for(var jj = 0; jj < ii; ++jj) {
            sb.Append(str);
        }
    }
    return sb.Length;
}
Solution 5: query comprehension abuse #1
static public int Fact(int n) 
{
    if (n == 0)
        return 1;
       
    return from n1 in n 
           where n1 - 1
           select n1*n;
}

static public int Where(this int n, Func f) 
{
   return f(n);
}

static public int Select(this int n1, Func f)
{
    return f(Fact(n1));
}
Solution 6: brute-force
static public int Included(int n, int k) {
    if (k<=1) return 0;
    if (n < k) return 0;
    return (n / k) + Included(n/k, k);
}
static public int Fact(int n) 
{
    if(n == 0) {
        return 1;
    }

    for(int ii = n, jj; ; ++ii) {
        for(jj = 2; jj <= n; ++jj) {
            for(int kk = 0, temp = ii; kk < Included(n,jj); ++kk) {
                if(temp != jj*(temp /= jj)) {
                    jj = n+1;
                    break;
                
                }
            }
        }
        if(jj == n+1) {
            return ii;
        }
    }
}

Friday, April 26, 2013

You know you're a software geek if you...

... need more non-letter characters on your keyboard.
... check your commit log to remind yourself how you spent your Sunday.
... understand what "It's all about the Pentiums" is about.
... know more programming languages than names of sports.
... find yourself jotting down programs on the subway.
... think everyone should be using hexadecimal.
... wish you had some free time so you could read more technical manuals.
... frequently use words like 'paradigm', 'implementation', 'iteration', 'overflow' and 'module'.
... think rainbow tables are SCARY.
... spend a large portion of your day optimizing the rest.
... when you hear "freedom from state", you think "Haskell"
... often repair things by rebuilding them from scratch.
... spend in a text editor or terminal the time other people spend watching TV.
... consider recursion a simple and elegant method for solving problems :-)

Friday, April 5, 2013

VerseLight

Allow me to present my most recent donationware app: VerseLight, a simple assistant for those who often look up Bible references. It sits quietly in your system tray and monitors your clipboard for verse references; whenever you copy one (say, Proverbs 13:20), it fetches the text from the Internet and presents it to you to read or copy. Currently, it only supports the New International Version, although that may change.

Download link

Screenshot: