Statically Typed

because Hindley-Milner rocks

Dynamic Problem Solution in Scala


First of all, thanks Ittay for your comment, it helped me to formulate a solution.  I’m not exactly happy about this solution and still think there’s a better way for overcome the limitations generics imposed upon me.  That’s for another time, I suppose.  Let me first describe why I went the direction I did then go on to how I did it.

Looking back at the two previous Python solutions I noticed that neither was ideal.  The first cost more computationally but used very little additional memory as long as the GC was on top of things.  The second solution created the entire table before traversing that table.  In reality all I needed to hold between each step was the list of the last iteration of subsequences and something describing the current best solution.  Then I’d have a lower memory imprint, retain the dynamic qualities which reduced effort, and avoided needing to traverse a large collection of objects twice.

First, I needed to create a bridge between some undefined type, A, and the functions “+” and “>.”  This is the part I’m not too thrilled about.  It feels like a lot of boilerplate just to get things working.  Maybe I’m doing something wrong here.

object Ops{
   def more[A<:AnyVal]( _1:A, _2:A ) = ( _1, _2 ) match {
      case ( _1:Int, _2:Int ) => _1 > _2
      case ( _1:Double, _2:Double ) => _1 > _2
      case ( _1:Short, _2:Short ) => _1 > _2
      case ( _1:Float, _2:Float ) => _1 > _2
   }

   def add[A<:AnyVal]( _1:A, _2:A ) = ( _1, _2 ) match {
      case ( _1:Int, _2:Int ) => _1 + _2
      case ( _1:Double, _2:Double ) => _1 + _2
      case ( _1:Short, _2:Short ) => _1 + _2
      case ( _1:Float, _2:Float ) => _1 + _2
   }
}

Then we get down to the heart of the solution.  I’ll need three functions.  The first just wraps the first two

def calcMaxSubsequence[A<:AnyVal]( _input:List[A] ) ={
   val ( start, length ) = maxSubsequence( _input, _input, _input head, 0, 1, 1 )
   length match {
      case 1 => _input( start ) :: Nil
      case _ => _input slice( start, start + length + 1 )
   }
}

Then a recursive method to calculate an optimal solution using the last calculated solution:

def maxSubsequence[A<:AnyVal]( _input:List[A], _previous:List[A], _max:A,
                               _start:Int, _length:Int, _count:Int ):(Int,Int) ={
   _input match {
      case head :: Nil => Ops.more( Ops.add( head, _previous head ), _max ) match {
         case true => ( 0, _count )
         case false => ( _start, _length )
      }
      case head :: tail =>
         val values = List.map2( _input, _previous )( (x,y) => Ops.Add( x, y ) )
         val currentMax = maxValue( values zipWithIndex, ( values head, 0 ) )
         Ops.more( currentMax._1, _max ) match {
            case true => maxSubsequence( tail, values, currentMax._1, currentMax._2, _count, _count + 1 )
            case false => maxSubsequence( tail, values, _max, _start, _length, _count + 1 )
         }
      case Nil => ( _start, _length )
}

Which probably shows that I abuse Scala’s pattern matching even when an if-else statement would suffice.  I find the match against true and false much easier to grok, personally.  YMMV.

Finally I come to the last of the three functions I need, a recursive call to figure out the largest value within the list:

def maxValue[A<:AnyVal]( _input:List[(A,Int)], _max: (A,Int) ):(A,Int) ={
   _input match{
      case head :: tail => Ops.more( head._1, _max._1 ) match {
         case true => maxValue( tail, head )
         case false => maxValue( tail, _max )
      }
      case Nil => _max
   }
}

Now you see why I’m not happy?  That’s a lot of code for a problem so simple.  Yes, I’ve gone the extra mile to make a “better” solution but in comparison the Python code was a mere 14 lines.  That’s a 3 fold increase.  Scala is a very expressive language and some how I messed it up.  I’ll get there eventually.

Btw, in 2.8 Scala has added a Numeric[A] type.  See this SO post.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Information

This entry was posted on April 18, 2010 by in Intervew Questions, Scala.
%d bloggers like this: