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

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...

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.

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;
        }
    }
}

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 :-)

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:

Too much recursion!

Who am I to argue :-)

Software and IT Law

Finally, the slides from Telerik Academy's "Software and IT Law" presentation are up! Only in Bulgarian, unfortunately, but I might translate them at some point if the authors agree to that.

 

IT Copyright Law at Telerik Academy from Telerik Software Academy

Copyrigh 2013 (c) Georgi Dimitrov, Teodor Sarakchiev

Chlock

Another little donationware app. This time it's the chess clock simulator that I promised my sisters.

chlock.exe - A simple and convenient chess clock.

Readme: https://github.com/staafl/chlock/blob/master/README.md
Application: https://raw.github.com/staafl/chlock/master/build/chlock-latest.zip
Source: https://github.com/staafl/chlock

Making Sense of Endianness

Machine endianness is one of those tricky concepts that are easy enough to define, but hard to really understand and conceptualize - like numeral systems, polymorphism, pointers and recursion, to give a few more examples. In this brief meditation I hope to share some insights on the topic that I've managed to reach through learning from others and long reflection. Considering that even experienced IT professionals occasionally make false statements regarding what endianness is and how it affects - or doesn't - a particular situation or software component, this overview might help someone reach a comfortable level of understanding more quickly and with less pain and confusion along the way. 

Basics: The Definition of Endianness

Wikipedia defines endianness as "the ordering of components (such as bytes) of a data item (such as an integer), as stored in memory or sent on a serial connection." When a software professional talks about endianness, he is referring to some structured binary data which may be interpreted differently depending on how the individual bytes are ordered, just as date notation has a different meaning depending on whether you expect 01-12 to be the 1st of December or the 12th of January. This is the kind of thing most people don't normally think about until something unexpectedly goes wrong - in life and in software.

Whenever an Intel processor reads a 4-byte unsigned integer, it expects the first byte to represent the total number modulo 2^8, the second byte - over 2^8, modulo 2^8, etc. For example:

A0 FF 7D 14 = A0(16)
            + 256(10) * FF(16)
            + 65536(10) * 7D(16)
            + 16777216(10) * 14(16)
            = 343,801,760(10)

An AMD processor expects the opposite - there, the same byte sequence would signify the number 2,701,098,260. On the other hand, if the same bytes were read as two adjacent 2-byte unsigned integers, the result would be A0 + 256*FF, 7D + 256*14 on a Pentium and 256*A0 + FF, 256*7D + 14 on an Itanium or a PlayStation 3. The specific endianness-es of the various architectures and the reasons for the different conventions are well described elsewhere, so we will not dwell on them here. Note that in the example above, if the data was read as 4 adjacent single bytes, the result would be the same regardless of the CPU.

Standard networking protocols use big-endian notation for integer fields such as port numbers, while the data itself has no predefined endianness other than the one assumed by the application. Various data formats and devices have conventions about how numeric data (i.e., all data) is to be stored, which occasionally leads to painful complications for the unexpecting software engineers.

Insight: The Meaning of Endianness

In its essence, "endianness" is the way in which the CPU interprets binary sequences in memory. The processor has no concept of "number", unlike humans who associate numbers with intuition and experiences. However, if we design a bijective correspondence between numbers (which are interesting to us) and binary strings (which the CPU can handle), we can use the processor to manipulate the binary strings according to its instruction set, and then we can decode the results back into abstract numbers - or have IO devices help us by representing the bytes in some other fashion, e.g.. as characters on a screen.

In this sense, the endianness of a CPU is the way it handles strings of bytes with respect to the basic arithmetic operations - and some basic primitives such as comparison, jumping and memory addressing. Everything else is built on top of that - looping and branching, array indexing, functions, input and output, and operates correctly so long as the CPU's operations honor the bijection.

Basically, endianness is an encoding between (abstract) numbers and (concrete) binary strings in the same way that UCS is an encoding between (abstract) characters and (abstract) numbers and UTF-8 is an encoding between (abstract) numbers and (concrete) sequences of bytes.

This is why, just like a piece of text data is meaningless unless we know its encoding and language, binary data is meaningless without knowing the endianness with which it was encoded - even if we know that such and such bytes represent a 4-byte signed integer, we can't tell if it's the number 2 or 33,554,432.

Practical issues: When does endianness matter? 

Short answer, when doing IO. In the case of user input/output, it's not much of a concern, since your OS and device drivers will transparently take care of the matter and make sure you get the correct byte strings in memory. Regardless of the technology stack you're working in, a correctly working program working on properly represented input data will produce correct, properly represented output. No one (except for the OS), needs to know how the CPU does arithmetic on binary strings. Once you have a properly constructed data object, the logic will work.

However, when dealing with files and networks, if the data is in an endianness-sensitive format and originated on another computer with different or unknown endianness, you need to take steps to insure it's properly interpreted at your end. Just as for security you need to watch your input and sanitize possibly tainted data, for correctness you need to keep track of which data may have been encoded on a device with different endianness, and process it accordingly before feeding it into the business logic of your application - and you should also be aware when some supposedly helpful intermediate component does the conversion for you so you won't corrupt your data by processing it again.

The other case you need to keep endianness in mind is when for some you're reading raw memory. Here's a tiny C# program for testing your processor's byte endianness:

using System;

// OR use BitConverter.IsLittleEndian
class Program
{
    unsafe static void Main() {
        int num = 1;
        bool le = *(byte*)&num == 1;
        Console.WriteLine("{0} endian", le ? "LITTLE" : "BIG");
    }
}

I plan to give some examples of when endianness-related issues in practice a bit later later.

As a footnote, UTF-16 "Big Endian" and UTF-16 "Little Endian" have nothing to do with CPU endianness - they're two number-to-bytestring encodings. The fact that the bytestrings are related so that wrong assumed encoding and different CPU endianness cancel each other out is in this sense almost a coincidence - so stop being confused.

Edit history:
2013-03-14 - I'd wrongly stated that AMD processors tend to be big-endian. I now know that all x86/x64 CPUs are little-endian, as are most modern achitectures - in addition to bi-endian ones (sic) such as SPARC, ARM and PowerPC. Also corrected misleading statement about data endianness in network transmissions.

Mind Map - Input and Output in .NET

I love it when I get assigned to do something cool and meaningful. Here is the Mind Map I had to chart for Telerik Academy's "Teamwork and Knowledge Sharing" course, on the topic of "Input and Output in .NET" (click on the images to see them full-sized).

Overview, with images

Detailed, without images

Doing them was fun! I'm so glad I got introduced to this concept and had motivation to practice it. Not only is mind mapping a fun exercise, and great for getting a sense of the structure of a topic, it seems like a really good way to document API.

I have so many ideas for maps right now, perhaps I'll start with Ruby's standard library so I won't have to open the documentation so often.

PS: Apparently, Blogspot has decided there is a worldwide shortage of pixels and downscaled the detailed mind map. Here it is in its original HD glory.

Blink!

The third member of today's trilogy:

blink.exe - An extremely simple and lightweight utility that protects your eyes and helps you avoid Computer Vision Syndrome - by reminding you to blink more often!

Readme: https://github.com/staafl/blink/blob/master/README.md
Application: https://raw.github.com/staafl/blink/master/build/blink-latest.zip
Source: https://github.com/staafl/blink

Sched!

Aaaand another exciting little donationware program by yours truly:

sched.exe - an extremely simple and lightweight task scheduling utility

Readme: https://github.com/staafl/sched/blob/master/README.md
Application: https://raw.github.com/staafl/sched/master/build/sched-latest.zip
Source: https://github.com/staafl/sched

Wake Up!

My latest exciting donationware project is here: https://github.com/staafl/wakeup/blob/master/README.md

No more painful morning snooze marathons! Wake up when you want to!

Application: https://raw.github.com/staafl/wakeup/master/build/wakeup-latest.zip
Source: https://github.com/staafl/wakeup

C# Riddles - Part II - Common Mistakes

This time it's some nasty gotchas, some of them common, some of them obscure, that the C# compiler may or may not catch for you. The intended purpose of the code is described in the comments, you can try to figure out what goes wrong.

// replace A with B
var mystr = Console.ReadLine();
mystr.Replace("A", "B");
Console.WriteLine(mystr);

// has more than 1 second elapsed since last time?
var do_it_again = (DateTime.Now - last_time).Seconds > 1;

// replace sequences of vowels with "VOWELS"
words = Regex.Replace(words, "\b[aoeiu]+\b", "VOWELS");

// print out a matrix
for(var ii = 0; ii < rows; ++ii) {
    for(var jj = 0; jj < columns; ++ii) {
        
        Console.Write("{0} ", matrix[ii,jj]);
        
    }
    
    Console.WriteLine();
    
}

// rethrow exception

var can_recover = false;
try {
    DoStuff(ref can_recover);
}
catch(ApplicationException ex) {
    if(!can_recover) {
        throw ex;
    }
}

// spinwait for 100 ticks

long now = DateTime.Now.Ticks;
while((DateTime.Now.Ticks - now).Ticks < 100);
Retry();

// get a datestamp

DateTime.Today.ToString("dd/mm/yyyy")

// add items to work queue for processing

var list = GetDbValues();
lock(work_queue) {
    for(var ii = 0; ii < list.Count; ++ii)
        work_queue.Add(() => Process(list[ii]));
    }
}

// run an action after 60 seconds

var timer = System.Timers.Timer(60.0);
timer.Elapsed += (_sender, _args) => Console.WriteLine("60 seconds have elapsed!");

// let's try again

var timer = System.Windows.Forms.Timer();
timer.Interval = my_interval;
timer.Tick += (_sender, _args) => Console.WriteLine("Time's up!");

// remove unwanted elements from a collection

foreach(var elem in list) {
    if(ComplicatedLogic(elem)) {
        list.Remove(elem);
    }
}

// hash the contents of a dictionary

public long HashDict(Dictionary dict) {
    long ret = 0;
    unchecked {
        foreach(var kvp in dict) {
            ret += kvp.Key.GetHashCode() * kvp.Value;
            ret << 1;
        }
    }
    return ret;
}

// raise event

public event EventHandler StateChanged;

void OnStateChanged() {
    StateChanged(this, new EventArgs());
}

// did it work?

bool worked = DidItWork();

if(worked = true) {
    MessageBox.Show("Success!")
}
else {
    MessageBox.Show("Oops!")
}

// let's make a simple struct

public struct MyStruct
{
    int field1;
    bool field2;
    
    public override bool Equals(MyStruct struct2) {
        return field1 == struct2.field1 && 
               field2 == struct2.field2;
    }
    
}

// ok, let's try with a class

public class MyClass 
{
    public int field1;
    public bool field2;
    
    public int GetHashCode() {
        return field1;
    }
    public override bool Equals(MyClass obj2) {
        return field1 == obj2.field1 && 
               field2 == obj2.field2;
    }
}

// last try

public class MyClass 
{
    public readonly int field1;
    public readonly bool field2;
    
    public int GetHashCode() {
        return field1;
    }
    public override bool Equals(MyClass obj2) {
        return field1 == obj2.field1 && 
               field2 == obj2.field2;
    }
}

// order by item1, then by item2

var ordered = from x in enumerable
              orderby x.Item1
              orderby x.Item2
              select x;

// simple assignment

class Class
{
    public Struct Struct { get; private set; }
}
struct Struct
{
    public int field;
}

...

var obj = new Class();
obj.Struct.field = 5;

// find intersection between two users

int customerID = 12345;
var productsForFirstCustomer = from o in Orders
                               where o.CustomerID = customerID
                               select o.ProductID;

// change customer ID and compose another query...
customerID = 56789;
var productsForSecondCustomer = from o in Orders
                                where o.CustomerID = customerID
                                select o.ProductID;

if( productsForFirstCustomer.Any( productsForSecondCustomer ) )
{
    ...
}

// start a new worker thread after some time

void MyThreadMethod(object data) {
    var start_after = 100.0 + (double)data;

}
...
var thread_number = 10;
Thread.Start(MyThreadMethod, thread_number);

// set sender's text to default

(sender as TextBox).Text = default_text;

// simple time formatting

Console.WriteLine("{0:уууу-ММ-dd}", DateTime.Today);

// using a default format string
    
public void Print(object obj) {
    const string default_format = "<{0}>";
    Print(default_format, obj);
}

public void Print(string str, params object[] objs) {
    Console.WriteLine(str, objs);
}
...
Print("hello");

// read file 10 lines at a time

public IEnumerator ReadLines(string file) {
    
    using(var sr = new StringReader(file))
        while(!sr.EndOfStream)
            yield return sr.ReadLine();
            
}


public bool Print10(IEnumerator enm) {
    for(var ii = 0; ii < 10; ++ii) {
        if(!enm.MoveNext())
            return false;
        Console.WriteLine(enm.Current);
    }
    return true;
}

...
var enm = ReadLines("input.txt");
while(true) {
    if(!Print10(enm))
        break;
        
    if(Console.Read() != 'y' &&
       Console.Read() != 'Y')
       break;
    
}

// do something if conditions are met

if(SomethingIsTheCase() && IFeelLikeIt() && TheTimeIsRight(() => { return DateTime.Now.AddDays(10); })); {
    
    DoSomething();
    
}

// parse a datestamp
var date = dt.ToString("dd/MM/yyyy");
...
var day = int.Parse(date.Split('/')[0]);

// apply rotation transform
// mygraphics is http://msdn.microsoft.com/en-us/library/system.drawing.graphics.aspx

mygraphics.RotateTransform(-Math.Atan(tan));

// modify a list

struct Point { public int x; public int y;}
List mypoints = ...;

mypoints[i].x = 10;

// write files then delete them

var files = Enumerable.Range(0, 5)
    .Select(i => Path.GetTempFileName());

foreach (var file in files)
    File.WriteAllText(file, "HELLO WORLD!");

/* ... many lines of codes later ... */

foreach (var file in files)
    File.Delete(file);

// tracing logic

private void DumpError(Exception exception, Stack context)
{
    if (context.Any())
    {
        Trace.WriteLine(context.Pop());
        Trace.Indent();
        this.DumpError(exception, context);
        Trace.Unindent();
    }
    else
    {
        Trace.WriteLine(exception.Message);
    }
}

// run an action after 60 seconds

private void Schedule(Action action)
{
    new System.Threading.Timer(state => action, null, 60000, Timeout.Infinite);
}

// a serializable class

[Serializable]
class Hello
{
    readonly object accountsLock = new object();
}

// open a file

using(var sw = new StreamWriter("resources\temp\textfile.txt")) {
    ...
}

DateTime.ToString("dd/mm/yyyy")

// unit test

static IEnumerable CapitalLetters(string input)
{
    if (input == null)
    {
        throw new ArgumentNullException(input);
    }
    foreach (char c in input)
    {
        yield return char.ToUpper(c);
    }
}

// spinwait for 100 ticks

long now = DateTime.Now.Ticks;
while((DateTime.Now.Ticks - now).Ticks < 100);
Retry();

// Test that null input is handled correctly
CapitalLetters(null).ExpectThrows();

// just a property

private int myVar;
public int MyVar
{
    get { return MyVar; }
}

// get a path

var prefix = "C:\\MyFolder\\MySubFolder";
var suffix = "\\log\\";

var path = Path.Combine(prefix, suffix);

// vips = gold clients + some silver ones

Collection silver_clients = GetClientsVips(ClientStatus.Silver);
Collection gold_clients = GetClientsVips(ClientStatus.Silver)
Collection vips = new Collection(gold_clients);

foreach(var client in silver_clients) {
    if(ClientMatchesVipRequirements(client)) {
        vips.Add(client);
    }
}

Sources:
- my own experience
- http://blog.roboblob.com/tag/dotnetgotcha/
- http://stackoverflow.com/questions/3703681/common-linq-standard-query-operator-mistakes-mis-steps
- http://der-waldgeist.blogspot.com/2011/04/common-linq-mistakes.html
- http://stackoverflow.com/questions/241134/what-is-the-worst-gotcha-in-c-sharp-or-net

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.

C# Riddles - Part I

A few tricky riddles and corner cases for wannabe C# language gurus:

// what gets printed / happens?
Console.WriteLine(null is object);

Console.WriteLine(null is IDisposable);

Console.WriteLine(null is int);

Console.WriteLine(null is int?);

Console.WriteLine(null is Func<int>);

Console.WriteLine(null is FileMode);

Console.WriteLine(0 is FileMode);

Console.WriteLine(0 is int?);

Console.WriteLine((((short)10)/((short)5)).GetType());

Console.WriteLine(new Nullable() is bool);

Console.WriteLine(new Nullable(false) is bool);

Console.WriteLine(new Nullable(false) is Nullable);

Console.WriteLine(new Nullable() is Nullable);

Console.WriteLine(null  + (int?)100 + "");

Console.WriteLine(null  + ""  + (int?)100);

Console.WriteLine(20 + 45 + "A");

Console.WriteLine("A" + 20 + 45);

Console.WriteLine(-int.MinValue);

string x = new string(new char[0]);
string y = new string(new char[0]);
Console.WriteLine(object.ReferenceEquals(x, y));

Console.WriteLine(default(int?));

Console.WriteLine(default(int?).GetHashCode());

Console.WriteLine(default(int?).GetType());

var ii = 1;
Console.WriteLine(ii += ii += ii += ii);

var ii = 0;
Console.WriteLine(ii = ii++);

Foo(this object obj) { return DateTime.Now.Seconds; }
...
Console.WriteLine(null.Foo());

int Rec(int i) { return (i < int.MaxValue) ? Rec(i + 1) : i; }
...
Console.WriteLine(Rec(0));

var array = new string[] { "foo", "bar", "cons" };
var objs = (object[])array;
objs[0] = 1000;
Console.WriteLine(objs[0]);

enum Foo { Bar, Baz }
...
Foo f = 0.0;
Console.WriteLine(f);

void Foo(object x) { Console.WriteLine("object"); }
void Foo(params T[] x) { Console.WriteLine("params T[]"); }
...
Foo("Hello");

struct Test
{
    static Test instance;
    static public Test Instance { get { return instance; } }
    
    public int field;
}
...
Test.Instance.field = 1;
Console.WriteLine(Text.Instance.field);

for(int ii = 0; ii < 10; ++ii)
  Console.WriteLine(new Random().Next(0, Int32.MaxValue));

var nums = new List<Func<int>>();
for (int ii=0; ii < 10; ii++)
    nums.Add(() => ii);
foreach (var num in nums)
    Console.WriteLine(num());

var nums = new List<Func<int>>();
foreach(var ii in Enumerable.Range(0,10))
    nums.Add(() => ii);
foreach (var num in nums)
    Console.WriteLine(num());

abstract class Base
{
    public virtual void foo(string s = "base") { Console.WriteLine("base " + s); }
}

class Derived : Base
{
    public override void foo(string s = "derived") { Console.WriteLine("derived " + s); }
}
...
Base b = new Derived();
b.foo();

throw null;

Exception GetException() { return new Exception(); }
...
throw GetException();

throw ((() => new Exception())());

throw ((() => { throw new Exception();} )());

// can your computer do arithmetic?

Console.WriteLine(1.0 + 1.0 == 2.0);

Console.WriteLine(0.01 + 0.01 == 0.02);

Console.WriteLine(0.00000037 + 0.0000001 == 0.00000047);

Console.WriteLine(0.9999999+0.000001 == 1.0);

Console.WriteLine(1.000001-0.000001 ==1.0);

/* assume InvariantCulture */
Console.WriteLine(4.170404 == Convert.ToDouble("4.170404"));

Console.WriteLine(Convert.ToInt32(13.6) == (int)13.6);

// does this compile?

const string foo = "aaa" + "bbb";
const string bar = "aaa" + 123;
const string frob = null;
const string squawk = (string)'\0';

// riddles
When can execution leave a try { } finally { } without executing the finally code?
How can you lock across AppDomains?
How can a string.Compare() call cause an AssemblyLoadException?
How can you create an instance of System.Void?

Sources:
- my own experience
- http://dotnetgeek.tumblr.com/post/11303229042/c-nullable-gotcha
- http://stackoverflow.com/questions/194484/whats-the-strangest-corner-case-youve-seen-in-c-sharp-or-net
- http://www.yoda.arachsys.com/csharp/teasers.html
- http://ahuwanya.net/blog/post/C-Brainteasers-Part-I.aspx
- http://stackoverflow.com/questions/241134/what-is-the-worst-gotcha-in-c-sharp-or-net