A small victory

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

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.

The Floyd-Warshall Algorithm

The classic Floyd-Warshall algorithm solves the "All-pairs shortest-path" problem on a weighted graph, namely, efficiently finding the length of the shortest route between every pair of vertices. It rests on the observation that if we denote the shortest path between A and B with {A,B}, then for every intermediate vertex K in {A,B}, {A,B}<={A,K}+{K,B}. A trivial recursive implementation follows:

floyd_warshall

    for each unordered pair (A,B)
        seen = [] // empty set
        min_paths[A,B] = fw_step(A,B)
        
fw_step A, B, seen

    if min_paths[A,B] exists
        return min_paths[A,B]
        
    min_path = |A,B| // direct distance between nodes
                     // may be infinity
                     
    seen[A,B] += 1 // dictionary keyed by unordered pair
    
    for each vertex K where seen[A,K] <= 1
                      and   seen[B,K] <= 1
        min_path = min(min_path, 
                       fw_step(A,K,seen) + fw_step(K,B,seen))
    
    return min_path

This is very inefficient. However, if we use an enumeration of all paths between A and B, based on the set of possible intermediate points [[], [0], [0,1], [0,1,2], ...], we can use that to remold the algorithm into an efficient dynamic programming solution:

    for K in [1; vertices] // for every vertex K find the shortest path {K,A,B}
    for A in [0; vertices) // that uses only [0..K-1] as intermediate nodes
    for B in [0; vertices)
        min_path[K, A, B] = min(min_path[K-1,A,B], 
                                min_path[K-1,A,K-1] + min_path[K-1,K-1,B])
                                
    // minimal paths for every A,B are in min_path[vertices, A, B]

A simple and neat O(n^3) solution to a daunting problem! Note that because we are checking the distance between nodes so often, the algorithm is vastly more efficient when using adjacency matrices rather than adjacency lists or edge lists for our graphs. Also, since in every iteration we're only using the previous enumeration level, min_path need only be of size 2*vertices^2:

    for K in [1; vertices]
    for A in [0; vertices)
    for B in [0; vertices)
        min_path[K%2, A, B] = min(min_path[(K-1)%2,A,B], 
                                  min_path[(K-1)%2,A,K-1] + min_path[(K-1)%2,K-1,B])
    
    // minimal paths for every A,B are in min_path[vertices%2, A, B]

Of course, this is overkill if you're only interested in the distance between two particular points - in that case, just use Dijkstra's algorithm, or some less general approach based on the specifics of your problem.

An important thing to note is that since the algorithm prefers shorter paths, it immediately ignores paths with cycles and repetitions (at least in the absence of negative edges); thus, it is not immediately adaptable to finding the longest paths by replacing min() with max(). It is possible to modify it for that purpose, however that requires looking out for malformed paths.