Code golf

2010-07-30 by mookid8000 Leave a comment

The result of Kodehoved’s code golf competition has been found, and I got a shared 5th place.

The task was to add two large integers together by representing the integers with arrays of their digits, thus allowing them to become extremely large.

My contribution looks like this (weighing in at 138 characters):

public static int[] Mookid8000_Add(int[] a,int[] b){
   var r="";
   for(int n=a.Length,m=b.Length,s,c=0;n+m+c>0;c=s/10)
      r=(s=(n>0?a[--n]:0)+(m>0?b[--m]:0)+c)%10+r;
   return r.Select(t=>t-48).ToArray();
}

public static int[] Mookid8000_Add(int[] a,int[] b){

var r="";

for(int n=a.Length,m=b.Length,s,c=0;n+m+c>0;c=s/10)

r=(s=(n>0?a[--n]:0)+(m>0?b[--m]:0)+c)%10+r;

return r.Select(t=>t-48).ToArray();

}

Asger‘s and Lars‘ contribution looks like this (135 characters):

public static int[] AsgerHallasOgLarsUdengaard_Add(int[] a,int[] b){
   var r="";
   for(int c=0,x=a.Length,y=b.Length;x+y>0|c>9;)
      r=(c=(x>0?a[--x]:0)+(y>0?b[--y]:0)+c/10)%10+r;
   return r.Select(s=>s-48).ToArray();
}

public static int[] AsgerHallasOgLarsUdengaard_Add(int[] a,int[] b){

var r="";

for(int c=0,x=a.Length,y=b.Length;x+y>0|c>9;)

r=(c=(x>0?a[--x]:0)+(y>0?b[--y]:0)+c/10)%10+r;

return r.Select(s=>s-48).ToArray();

}

And the winners’ (Mads and Peter Sandberg Brun) contribution looks like this (weighing in at an incredibly compact, but almost unreadable, 132 characters :)):

public static int[] MadsOgPeterSandbergBrun_Add(int[] a,int[] b){  
   var c="";  
   for(int o=a.Length,p=b.Length,s=0;-o-p<(s=s/10+(0<o?a[--o]:0)+(0<p?b[--p]:0));)  
      c=s%10+c;  
   return c.Select(i=>i-48).ToArray();  
}

public static int[] MadsOgPeterSandbergBrun_Add(int[] a,int[] b){

var c="";

for(int o=a.Length,p=b.Length,s=0;-o-p<(s=s/10+(0<o?a[--o]:0)+(0<p?b[--p]:0));)

c=s%10+c;

return c.Select(i=>i-48).ToArray();

}

I usually don’t compete in competitions like this, because I’ve always thought of myself as pretty lame when it comes to solving coding puzzles, but this time it was great fun – especially since I was pretty motivated by my desire to beat Asger (my little sister’s boyfriend), who pushed me several iterations further than I would have gone on my own. He ended up beating me though, but I am still pretty satisfied with my fairly compact and almost readable solution.

Fun with NoRM 4

2010-07-26 by mookid8000 Leave a comment

This time, a short post on how to model inheritance, which (at least in a class-oriented programming language) is one of the foundations of object-oriented programming.

Let’s take an example with a person, who has a home address that can be either domestic or foreign. Consider this:

public class Person
{
    public string FirstName { get; set; }
    public string LastName { get; set; }

    public Address HomeAddress { get; set; }
}

public abstract class Address
{
    public abstract string FormatAddress(string separator);
}

public class DomesticAddress : Address
{
    public string Street { get; set; }
    public string Number { get; set; }
    public string PostalCode { get; set; }
    public string City { get; set; }
    // and 17 other fields here, according to whatever is standard in your country

    public override string FormatAddress(string separator)
    {
        return string.Join(separator, new[] { Street + " " + Number, PostalCode + " " + City });
    }
}

public class ForeignAddress : Adress
{
    public string[] AddressLines { get; set; }

    public override string FormatAddress(string separator)
    {
        return string.Join(separator, AddressLines);
    }
}

public class Person

{

public string FirstName { get; set; }

public string LastName { get; set; }

public Address HomeAddress { get; set; }

}

public abstract class Address

{

public abstract string FormatAddress(string separator);

}

public class DomesticAddress : Address

{

public string Street { get; set; }

public string Number { get; set; }

public string PostalCode { get; set; }

public string City { get; set; }

// and 17 other fields here, according to whatever is standard in your country

public override string FormatAddress(string separator)

{

return string.Join(separator, new[] { Street + " " + Number, PostalCode + " " + City });

}

public class ForeignAddress : Adress

{

public string[] AddressLines { get; set; }

public override string FormatAddress(string separator)

{

return string.Join(separator, AddressLines);

}

Now, when I create a Person with a DomesticAddress and save it to my local Mongo, it looks like this:

var people = mongo.GetCollection<Person>();
people.Insert(new Person
{ 
    FirstName = "Mogens Heller", 
    LastName = "Grabe",
    HomeAddress = new DomesticAddress 
    { 
        Street = "Torsmark", 
        Number = "4", 
        // etc
    }
});

var people = mongo.GetCollection<Person>();

people.Insert(new Person

{

FirstName = "Mogens Heller",

LastName = "Grabe",

HomeAddress = new DomesticAddress

{

Street = "Torsmark",

Number = "4",

// etc

}

});

which is all fine and dandy – and in the db:

> db.Person.findOne();
{
    "FirstName": "Mogens Heller",
    "LastName": "Grabe",
    "HomeAddress": {
        "Street": "Torsmark",
        "Number": "4",
        // etc...
    }
}

> db.Person.findOne();

{

"FirstName": "Mogens Heller",

"LastName": "Grabe",

"HomeAddress": {

"Street": "Torsmark",

"Number": "4",

// etc...

}

which looks pretty good as well. BUT when I try to load the person again by doing this:

var people = mongo.GetCollection<Person>();
var me = people.FindOne();

1 2	var people = mongo.GetCollection<Person>(); var me = people.FindOne();

I get BOOM!!: Norm.MongoException: Could not find the type to instantiate in the document, and Address is an interface or abstract type. Add a MongoDiscriminatedAttribute to the type or base type, or try to work with a concrete type next time.

Why of course! JSON (hence BSON) only specifies objects – even though we consider them to be logical instances of some class, they’ re actually not! – they’re just objects!

So, we need to help NoRM a little bit. Actually the exception message says it all: Add a MongoDiscriminatedAttribute to the abstract base class, like so:

[MongoDiscriminated]
public abstract class Address
{
    public abstract string FormatAddress(string separator);
}

[MongoDiscriminated]

public abstract class Address

{

public abstract string FormatAddress(string separator);

}

That was easy. Now, if I do a db.People.drop(), followed by my people.Insert(...)-code from before, I get this in the db:

> db.Person.findOne();
{
    "FirstName": "Mogens Heller",
    "LastName": "Grabe",
    "HomeAddress": {
        "__type": "MongoTest.DomesticAddress, MongoTest",
        "Street": "Torsmark",
        "Number": "4",
        // etc...
    }
}

> db.Person.findOne();

{

"FirstName": "Mogens Heller",

"LastName": "Grabe",

"HomeAddress": {

"__type": "MongoTest.DomesticAddress, MongoTest",

"Street": "Torsmark",

"Number": "4",

// etc...

}

See the __type field that NoRM added to the object? As you can see, it contains the assembly-qualified name of the concrete type that resulted in that particular object, allowing NoRM to deserialize properly when loading from the db.

Now, this actually makes working with inheritance hierarchies and specialization pretty easy – just add [MongoDiscriminated] to a base class, resulting in concrete type information being saved along with objects of any derived type.

Only thing that would be better is if NoRM would issue a warning or an exception when saving something that could not be properly deserialized – this way, one would not easily get away with saving stuff that could not (easily) be retrieved again.

Fun with NoRM 3

2010-07-22 by mookid8000 Leave a comment

Third post in “Fun With NoRM” will be about how “the dynamism” of JavaScript and JSON is bridged into the rigid and statically typed world of C#. The thing is, in principle there’s no way to be certain that a JSON object returned from MongoDB will actually fit into our static object model.

Consider a situation where, for some reason, some of our orders have a field, PlacedBy, containing the name of the person who placed the order. Let’s see how things will go when adding the field and then querying all orders:

> use dbname
> var order = db.Order.findOne();
> order.PlacedBy = "El Duderino";
> db.Order.save(order);

> use dbname

> var order = db.Order.findOne();

> order.PlacedBy = "El Duderino";

> db.Order.save(order);

var orders = mongo.GetCollection<Order>();

foreach(var order in orders.Find())
{
    Console.WriteLine("Order #{0}", order.Number);
}

var orders = mongo.GetCollection<Order>();

foreach(var order in orders.Find())

{

Console.WriteLine("Order #{0}", order.Number);

}

– and BOOM ! – Cannot deserialize!: Norm.MongoException: Deserialization failed: type MongoTest.Order does not have a property named PlacedBy

This is actually pretty good, because this way we will never accidentally load a document with un-deserializable properties and save it back, thus truncating the document. But how can we handle this?

Well, NoRM makes it pretty easy: Make your model class inherit Expando, thus effectively becoming a dictionary. E.g. like so:

public class Order : Expando
{
   // ...
}

public class Order : Expando

{

// ...

}

Now we can do this:

var orders = mongo.GetCollection<Order>();

foreach(var order in orders.Find())
{
    Console.WriteLine("Order #{0}", order.Number);

    if (order.AllProperties().Any())
    {
        var props = order.AllProperties().Select(p => string.Format("{0}: {1}", p.PropertyName, p.Value));
        Console.WriteLine("\t{0}", string.Join(", ", props.ToArray()));
    }
}

var orders = mongo.GetCollection<Order>();

foreach(var order in orders.Find())

{

Console.WriteLine("Order #{0}", order.Number);

if (order.AllProperties().Any())

{

var props = order.AllProperties().Select(p => string.Format("{0}: {1}", p.PropertyName, p.Value));

Console.WriteLine("\t{0}", string.Join(", ", props.ToArray()));

}

– which yields:

Order #1
    PlacedBy: El Duderino
Order #2
Order #3

Order #1

PlacedBy: El Duderino

Order #2

Order #3

when run with a small DB containing three orders. Nifty, huh?

If you’re sad that you’ve given up your single opportunity to inherit something by deriving from Expando, just go ahead and implement IExpando instead. Then you need to suply a few members, but you can just redirect to an internal Expando in your class.

Next up, a post on how to model inheritance hierarchies… one of my favorites! 🙂

Fun with NoRM 2

2010-07-19 by mookid8000 Leave a comment

This second post in “Fun With NoRM” will be about querying…

How to get everything

Querying collections can be done easily with the anonymous types of C# 3 – e.g. the Order collection from my previous post can be queried for all orders like so:

var orders = mongo.GetCollection<Order>();

var allOrders = orders.Find();

var orders = mongo.GetCollection<Order>();

var allOrders = orders.Find();

How to use criteria

If we’re looking for some particular order, we can query by field values like so:

var orderNumber2 = orders.Find(new { Number = 2 });

1	var orderNumber2 = orders.Find(new { Number = 2 });

or by using the query operators residing in the static class Q:

var ordersWithNumberGreaterThan2 = orders.Find(new { Number = Q.GreaterThan(2) });

1	var ordersWithNumberGreaterThan2 = orders.Find(new { Number = Q.GreaterThan(2) });

More advanced criteria

The query operators can even be combined by combining criteria like so:

var ordersWithNumberBetween5And10 = orders.Find(new { Number = Q.GreaterThan(5).And.LessThan(10) });

1	var ordersWithNumberBetween5And10 = orders.Find(new { Number = Q.GreaterThan(5).And.LessThan(10) });

Now, what about the nifty dot notation? This an example where C#’s capabilities don’t cut it anymore, as everything on the left side in an anonymous type need to be valid identifiers – so no dots in property names!

This is solved in NoRM by introducing Expando! (not to be confused with ExpandoObject of .NET 4, even though they have similarities…)

Expando is just a dictionary, so to query by the field of an embedded object, do it like so:

var q = new Expando();
q["Items.Name"] = "beer";
var ordersWithBeer = orders.Find(q);

var q = new Expando();

q["Items.Name"] = "beer";

var ordersWithBeer = orders.Find(q);

As you can see, querying with NoRM is pretty easy – and I think the NoRM guys have found a pretty decent workaround in the case of dot notation, where C#’s syntax could not be bent further.

Stay tuned for more posts…

Fun with NoRM 1

2010-07-16 by mookid8000 Leave a comment

My previous posts on MongoDB have been pretty un-.NETty, in that I have focused almost entirely on how to work the DB through its JavaScript API. To remedy that, I shall write a few short posts on how to get rolling with MongoDB using NoRM, the coolest C# driver for MongoDB at the moment.

First post will be on how to connect and shove data into MongoDB.

Short introduction to NoRM

NoRM is “No Object-Relational Mapping”. It’s a .NET-driver, that allows you to map objects and their fields and aggregated objects into documents. I like NoRM because it’s successfully preserved that low-friction MongoDB-feeling, bridging C#’s capabilities nicely to those of JavaScript in the best possible way, providing some extra C#-goodies along the way. Please read on, you’ll see…

Connect to MongoDB

Easy – can be done like so:

using(var mongo = Mongo.Create("mongodb://hostname/dbname"))
{
   // go crazy in here!!1
}

using(var mongo = Mongo.Create("mongodb://hostname/dbname"))

{

// go crazy in here!!1

}

Inserting a few documents

Inserting documents with NoRM is easy – just create a class with fields and aggregated objects, and make sure the class either has a property named something like “Id” or has a property decorated with [MongoIdentifier], e.g. like so:

public class Order
{
    public Order()
    {
        Id = ObjectId.NewObjectID();
        Items = new List<Item>();
    }

    public ObjectId Id { get; set; }
    public int Number { get; set; }
    public List<Item> Items { get; set; }
}

public class Item
{
    public string Name { get; set; }
    public int Amount { get; set; }
}

public class Order

{

public Order()

{

Id = ObjectId.NewObjectID();

Items = new List<Item>();

}

public ObjectId Id { get; set; }

public int Number { get; set; }

public List<Item> Items { get; set; }

}

public class Item

{

public string Name { get; set; }

public int Amount { get; set; }

}

– and then go ahead and pull a strongly typed collection and insert documents into it:

var orders = mongo.GetCollection<Order>();

orders.Insert(new Order {
    Number = 1,
    Items = {
        new Item { Name = "beer" },
        new Item { Name = "nuts" },
    }
});

var orders = mongo.GetCollection<Order>();

orders.Insert(new Order {

Number = 1,

Items = {

new Item { Name = "beer" },

new Item { Name = "nuts" },

}

});

Now, to make this work I need to create five 200-line XML-files with mapping info etc. </kidding> no, seriously – that’s all it takes to persist an entire aggregate root!!

Pretty cool, eh? That’ s what I meant when I said low friction. Stay tuned for more posts, e.g. on how to query a collection…