Thursday, April 24, 2014

Solving a programming puzzle with lambda, or, writing confusing functional code.

Thinking in terms of lambdas is difficult for some so I'm hoping to explain how I approach it step by step.

The other evening while trying to think of some material to inspire me to write, I thought of an online programming puzzle that I received as an interview screening process many months back.  I went back through old mail to try and reincarnate the test question, but the link was inactive.  My searches on google using certain aspects that I could remember found me the exact interview question on StackOverflow.com.

Note, the question was downvoted as it was identified as an interview question, the person asking marked an answer correct which isn't, and another person used his ability to see deleted answers to repost one. All sorts of "what not to do on stackoverflow" types of things here, but I won't let that detract from the point of this post...

Here's the question verbatim:
In a race, you bet using the following strategy. Whenever you lose a bet, you double the value of the bet for the next round. Whenever you win, the bet for the next round will be one dollar. You start the round by betting one dollar.
For example, if you start with 20 dollars, and you win the bet in the first round, lose the bet in the next two rounds and then win the bet in the fourth round, you will end up with 20+1-1-2+4 = 22 dollars.
You are expected to complete the function, getFinalAmount, which takes two arguments:
  1. The first argument is an integer initialAmount which is the initial money we amount we have when we start the betting.
  2. The second argument is a string betResults. The ith character of outcome will be either 'W' (win) or 'L' (lose), denoting the result of the ith round. Your function should return the amount of money you will have after all the rounds are played.
If at some point you don't have enough money in your account to cover the value of the bet, you must stop and return the sum you have at that point.
The solution to this question is simple enough with some loops and tests, but after solving it, the code golfer and functional programmer in me wanted to show off.

Code Golf is when you try to solve a particular programming problem in the least number of characters.  Currently my solution requires 127 characters - including only the body of the method that takes the arguments.  It and many other people's solutions in various languages can be seen here.  Some maniac typically will put in a brainfuck solution just to show off, which is impressive.

*The purpose of this exercise for me in this blog was to solve the problem in one line of code. Real code golf is the least number of chars.

I enjoy pushing the envelope and making things look more mysterious then they are, and playing code golf in general forces you to be creative.  Here it is completely code golfed, and here's a .NET Fiddle of it.:
That's the complete solution to the problem above, and it passes all unit tests for the question.

That looks impossibly horrible to wrap your head around, and that's because i't compressed as much as possible.  Let's back up and take it step by step...  First off, in order to make this a one liner, I'm going to have to somehow loop through the characters in the string one by one, and maintain state between each.

Right away I'm thinking the Aggregate extension method which has a handful of overloads, but the one I'm most familiar with and used will start with a seed item, then go through the IEnumerable and pass each item into a function which does something and returns a new element of the same type to be handed into the next, the last element being the final result (some overloads change this behavior).

So we're going to need to start off with a seed object that can carry through each step maintaining state.  We don't have to define a class because anonymous classes can be used as long as the definition matches every time they're created within the context of a function(?). This is key - we're defining new variables because we're defining new types.  So our class upon first inspection needs two things - the (b)et, and the (c)urrent balance.
betResults.Aggregate(new { b = 1, c = initialAmount}, ...
Next we need a lambda that takes 2 arguments - the (l)ast result (our anony class), and the (o)utcome of the 'race'.
(l, o) =>
Keep in mind that we're in the Framework's aggregate function now.  It will call this lambda repeatedly for each element in the sequence.  The sequense is out race outcomes.  Now it's a simple if then statement around the 'W' or 'L' building a new result based on the simple game rules:
o == 'W'    //if the outcome was a win...
        ? new {b = 1, c = l.c + l.b} //create a new result with the bet at 1 and the current balance as the last current balance plus the last bet
         : new {b = l.b*2, c = l.c - l.b} //otherwise we lost, so a new result is the old bet times two, and the balance is the old balance minus the bet
Expland the variable names if you're having trouble...  So this method works, and is identical to some of the answers on the related StackOverflow.com question.  However, what it's missing it the short circuit way out if we go broke.  This is what makes it real tough to shrink down the functional approach with lambda - we can't run an extra statement to break out of a loop.

In this case, what I did (but someone in the comments or related posts will most likely do better) is to check if we're going to have enough to wager on the next race, and if not, set a (x)cancel flag in our anonymous class.  Because we're changing that class we have to adjust the seed as well.  Here's the whole thing commented thoroughly:

I apologize for any formatting issues, I'll work them out.  Also, no I did not submit a lambda solution to this programming puzzle to the employer who gave it to me.  I was going to do it as a comment but felt that was too cocky.  Also, no I didn't get that job - I was just taking the test as a prescreen for a future position, which I don't think that I'll look into.  I'll also let the employer know that this and the related StackOverflow question is up.  Finally, code golf it here!

EDIT: I replaced the bool 'flag' with an int of the bet minus balance result, for golf purposes the word "false" was too long.

Cheers!

Tuesday, September 23, 2008

ADO.NET Data Services + Oracle

Wow - this is wicked cool stuff.

ADO.NET Data Services allow you to expose IQueryable objects as RESTful endpoints in ATOM, POX, and JSON. Here's my brain dump of how cool this can be used for RAD purposes...

ADO.NET Data Services is being plugged as just a endpoint for ADO.NET Entities, and thus just SQL Server's LINQ to SQL implementation. Microsoft themselves are doing most of that damage - but I want to point out how it's much bigger than that!

If you're like me, you have the pleasure (yes, pleasure) of working with Oracle instead of SQL Server. Many times this leaves you feeling high and dry with all this cool new LINQ stuff. There is no realy good LINQ to Oracle implementation out there - but the team at NHibernate has come to the rescue.

NHibernate is a .NET port of the years old Java Hibernate project - providing ORM for your software. The importance of this framework in the RAD world is big - it allows you to very easily map a database to objects.

LINQ to NHibernate is almost a year old now, and is in the process of being implemented in the main trunk of NHibernate (currently it's there, but throws a NotImplementedException after mocking you by showing you the SQL it knows that it should use). However, in the NContrib trunk, I have found a quite functional version of LINQ to NHibernate!

Why do I bring this up? Because some kind people in the project have even gone so far as to implement the System.Data.Services.IUpdateable interface within the LINQ.NHibernate project. This means fully functional ADO.NET Data Services for your Oracle database.

With only a couple lines of code, you can expose your NHibernate objects as queryable JSON, ATOM, POX RESTful services. Simply extend NHibernateContext, provide a ProvideSession() implementation, and expose public IQueryable properties on your object. Use this class as the type parameter of a new System.Data.Services.DataService class, and you'll be all set.

ADO.NET data services provides the RESTful interface which is flexible enough to pass pagnation, ordering, filtering, etc straight through the web layer to the database layer. So a javascript request for:

http://server/someobject?$filter=someid eq '1'&$orderby=somefield

produces SQL sent straight to Oracle of

select *
from someobject
where someid = 1
order by somefield

It's also fully updatable (through the IUpdateable implementation) which means that POST, PUT, DELETE requests work in a similar fashion.  It provides it in a JSON format, allowing you to use your database tables as javascript collections.... wow... Again, the RAD implications are huge.

The only issue that I have is with performance - NHibernate doesn't seem to stream resultsets (instead building the object array all at once), and the wordy ATOM/JSON formats don't suit some applications. ADO.NET Data Services is NOT pluggable with custom serialization - I've decompiled and searched for an entry point for literally DAYS.

One other point to make, is that referencing these new data services from VS2008 SP1 provides you with a client side LINQ object which translates linq queries to filtered HTTP requests (as in the filter/order/etc format above, which then translates to SQL... So, cool.

I'd provide some detailed examples and implementations - but that'd ruin all the fun ;)

Tuesday, June 3, 2008

More Linq - Find all methods having an attribute

Not much time tonight, but here a little helper method that I wrote today. It's just another example of my Linq addiction of late.

I've had to search all loaded assemblies for methods or classes with certain custom attributes on them dozens of times when writing some generic framework for something or such... So I linqified it today, and came up with this:

public static List<MethodInfo>
GetMethodsWithAttribute(Type t, bool inherit)
{
return (from ass in AppDomain.CurrentDomain
.GetAssemblies()
from c in ass.GetExportedTypes()
from m in c.GetMethods()
from a in m.GetCustomAttributes(t, inherit)
select m).ToList();
}


This sample just prints out all methods with the SecurityPermission attribute. Notice my continued "abuse" of lambda as well...

GetMethodsWithAttribute(
typeof(SecurityPermissionAttribute),
true)
.ForEach((a) =>
Console.WriteLine("{0}.{1}",
a.DeclaringType.Name,
a.Name));

Wednesday, May 28, 2008

LINQing the Fibonacci Sequence

I've never been one for algorithms and/or academic type of questions/examples. However, while interviewing for my latest job I was asked to write code to generate the Fibonacci sequence... I struggled through it as much as my poor interviewing skills allowed. It was only my second job interview ever (for my second job ever) so I guess that means I'm batting a 1.000, even if I suck at interviewing ;)

Thinking of something to blog about tonight I figured I could make a FibonacciSequence generator that implemented IEnumerable just for shits and giggles (and I'll send the link to Johnny Mac for possible redemption).

There are a dozen ways to generate the sequence (albeit in the interview I could barely find one - lol), but I chose this way because it easily allowed for the "yield" keyword.

Also, then we can use LINQ over it... Our final code can do this:

//an enumerator over every Fibonacci
//number divisible by 3
var qry = (from ulong i
in new FibonacciSequence()
where i % 3 == 0
select i);


What's even better, is now I'm prepared for that next interview question, which could be "create an enumeration over a distinct ascending ordered list of every Fibonacci number divisible by 3 times every Fibonacci number divisible by 5 whose product is divisible by 17:

var qry = (from ulong i
in new FibonacciSequence()
from ulong j
in new FibonacciSequence()
where j % 5 == 0
&& i % 3 == 0
let res = (double)i*j
where res % 17 == 0
orderby res
select res).Distinct();


Amazingly, the above code will print out all elements of the enumeration in under 1 second.

And finally, here's the FibonacciSequence class.

public class FibonacciSequence : IEnumerable<ulong>
{

public IEnumerator<ulong> GetEnumerator()
{
yield return 0;
yield return 1;
ulong a = 0;
ulong b = 0;
ulong c = 1;
checked
{
while (true)
{
a = b;
b = c;
try
{
c = a + b;
}
catch (OverflowException)
{
yield break;
}
yield return c;
}
}
}

System.Collections.IEnumerator
System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}


As a final disclaimer - yes, the ulong to double conversion in the first example does result in a loss of precision, so please don't comment on that.

Cheers!

Wednesday, May 21, 2008

Extension Methods

I've been having a good time with extension methods in C# 3.0 lately. You know, kids to bed, having a beer, reading digg.com and thinking, "What am I doing?!?! I wanna write some extension methods! Hell Yes!!!" </sarcasm>

If you don't know about, or understand extension methods - google it. This post is NOT for the beginning developer. I'm not providing complete examples that you can just pop in your code. You need to understand where to put these extension methods (in some static class in a special namespace that isn't ALWAYS included). I'm not catering to the script kiddies here (script kiddies: go back to the IRC #hak5 chat room please).

The first thing everyone seems to want to do is take all of the static methods from the static "Convert" class and apply them to the appropriate objects. Certainly a reasonable approach. However, instead of writing it all out, we can just codegen all of the methods. The Jedi is lazy - most of you know that already.
This code will popup a messagebox that you can copy the code for all 100+ (I'm not counting) conversion methods. The end result is that all primitives have a "ToWhatever()" method that makes it easy to do conversions.

static void Main()
{
StringBuilder code = new StringBuilder();
foreach (var m in typeof(Convert).GetMethods(
BindingFlags.Public |
BindingFlags.Static))
{
ParameterInfo[] parameters =
m.GetParameters();
code.AppendFormat("public static {0} {1}(",
m.ReturnParameter.ParameterType.Name,
m.Name);
bool first = true;
foreach (var p in parameters)
{
if (first)
{
code.Append("this ");
first = false;
}
code.AppendFormat("{0} {1}, ",
p.ParameterType.Name,
p.Name);
}
code.Remove(code.Length - 2, 2);
code.AppendFormat(") {{ return Convert.{0}(",
m.Name);
foreach (var p in m.GetParameters())
{
code.AppendFormat("{0}, ", p.Name);
}
code.Remove(code.Length - 2, 2);
code.Append("); }");
code.AppendLine();
}
MessageBox.Show(code.ToString());
}

Sweet... But, that code will throw on exceptions... What if we wanted a "TryParse" type of equivalent for every single one? Time for another approach.
All of these objects are IConvertible.... Hmmmm... how about this approach!

public static T To<T>(this IConvertible obj)
{
return (T)Convert.ChangeType(obj, typeof(T));
}

Sweet! Now we can do

int i = myString.To<int>();

So adding a couple helper methods is easy as pie.

public static T ToOrDefault<T>
(this IConvertible obj)
{
try
{
return To<T>(obj);
}
catch
{
return default(T);
}
}

public static bool ToOrDefault<T>
(this IConvertible obj,
out T newObj)
{
try
{
newObj = To<T>(obj);
return true;
}
catch
{
newObj = default(T);
return false;
}
}

public static T ToOrOther<T>
(this IConvertible obj,
T other)
{
try
{
return To<T>obj);
}
catch
{
return other;
}
}

public static bool ToOrOther<T>
(this IConvertible obj,
out T newObj,
T other)
{
try
{
newObj = To<T>(obj);
return true;
}
catch
{
newObj = other;
return false;
}
}

public static T ToOrNull<T>
(this IConvertible obj)
where T : class
{
try
{
return To<T>(obj);
}
catch
{
return null;
}
}

public static bool ToOrNull<T>
(this IConvertible obj,
out T newObj)
where T : class
{
try
{
newObj = To<T>(obj);
return true;
}
catch
{
newObj = null;
return false;
}
}

Now we can ask for default (calls blank constructor or "0" for numerics) on failure, specify a "default" value (I call it "other"), or ask for null (where T : class). I've also provided both silent exception models, and a typical TryParse model that returns a bool indicating the action taken, and an out param holds the new value.
So our code can do things like this

string a = myInt.ToOrDefault<string>();
//note type inference
DateTime d = myString.ToOrOther(DateTime.MAX_VALUE);
double d;
//note type inference
bool didItGiveDefault = myString.ToOrDefault(d);
string s = myDateTime.ToOrNull<string>();

Oddly type inference doesn't pickup on expected return types. I'd think it would. Thoughts?

So - I'd think that's about the best you can get. I couldn't get Nullable types to roll into the whole thing very cleanly. I tried for about 20 minutes before I threw in the towel.

Enjoy!

Wednesday, May 14, 2008

4 nasty C# 3.5 code "changes" for your last day at work

I recently left my job of over 8 years, and it got me to thinking about the fun I could have had with the millions of lines of code that I had access to. Of course, I didn't do any of these things (though I wish I had done some of the funny ones), and I won't be doing them in the future at my new job either. Let me clearly state that this post is meant to be read as humor. However, it is meant to be informative regarding .NET 3.5 / C# 3.0.

Leaving your job? Being laid off? Here's 4 fun/annoying/destructive things to leave behind!




4. Refactor random methods into operator overloads
(rated: annoying)


Find some methods throughout the code that match operator parameter lists and replace them with operator overloads.

Example:
change this:

public void MyMethod() 
{ 
    //does something 
}
into this:
public static int operator ~ (TheClass c) 
{ 
    //do the same thing referencing "c" instead of "this" 
}
or change this:
public string MyOtherMethod(string something)  
{  
    //does something  
}
into this:
public static string operator + (TheClass c, string something)  
{  
    //do the same thing referencing "c" instead of "this"  
}
Then go through all the broken code and adjust it to use the overloads instead of the methods. This would make the code TERRIBLY confusing!

I
magine seeing:
MyClass m = new MyClass();
~m;
string answer = m + "Jedi";
Greatest part about this annoyance is that "Find References" doesn't work on overloads, so beginner programmers are left stumped; Especially with the "~" overload as many people have never even seen that before outside of destructors!



3. Create Extension methods with hilarious names on base objects
rated: funny


Find some obscure cs file deep within the code, and add this at the bottom:


namespace System
{
    public static class HaHa
    {        public static void ThatsWhatYourMotherSaid(this object o)        {
        }    }}

Now every object in the entire codebase has a useless method called "ThatsWhatYourMotherSaid". Maybe I'm a geek, but that's hilarious. Note: this is easily findable with a "Go to definition" context option.
If you'd rather be annoying instead of funny, do the same thing, but write a program to generate code creating methods for every English word in the dictionary. That would render Intellisense useless - and possibly even cause major IDE slowdown (I didn't try!).

This works well because we put the class "HaHa" in the namespace "System". This namespace is included in every C# file ("using System;"), unless it's been strangely removed. Extension methods are only revealed on objects if the namespace in which they are defined is included (yeah, that's why you have "using System.Linq;" in your code!).




2. Create seemingly useful extension methods which do nothing, or worse...
rated: annoying at the least, possibly destructive

Once again, find some obscure file to hide this in. Similar to above, create an extension method but this time make it sound useful. New people, or beginners joining the project may think, "Wow! That's great!". Here's some examples I can think of:


namespace System
{    public static class HaHa
    {        public static bool EqualsCaseInsensitive(this string s1, string s2)        {
            return true;
        }        public static void ShowOnTop(this Form f)        {            f.Close();
        }
    }
}

Now your strings have a "EqualsCaseInsensitive" method which always returns true, and your forms have a "ShowOnTop" method that closes the form (which also calls Dispose() I believe)! Evil....



1. Replace a widely used core library class with a creatively destructive decorator class
rated: Extremely destructive

Creating a decorator (aka wrapper) class for a core framework class which has the exact same name will allow existing code to compile, but you gain control over it's behavior. The issue here is that if you define a class in local code under the same namespace as a framework class, it will be used instead of the framework class. Here's an INCOMPLETE example:



namespace System.Threading
{
    public class Thread
    {
        private global::System.Threading.Thread _wrappedThread;
        public Thread(ThreadStart start)        {            _wrappedThread = new global::System.Threading.Thread(start);        }
        .
        .
        .
        public void Start()
        {
            if (new Random().Next(1, 101) >= 99)
            {
                return;
            }
            else
            {
                _wrappedThread.Start();
            }
        }        .        .        .
    }
}

To make this example complete, you'd have to decorate every method, property, and event on the Thread class. Tedious, but not too bad with a program to generate the code. Note the usage of "global::" which makes it use the REAL Thread class.
Bottom line is, with the above example (if completed), you'd end up with System.Threading.Thread.Start() only starting 98% of the time. Now THAT is a bitch!

Cheers,
The Software Jedi