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!