Showing posts with label programming. Show all posts
Showing posts with label programming. Show all posts

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

Saturday, March 30, 2013

Saturday, March 2, 2013

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

Thursday, February 28, 2013

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.

Tuesday, February 19, 2013

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