all and sundry: September 2010

Sunday, September 12, 2010

Karate Chop - An Imperative and Functional implementation

Karate Chop is a Kata about implementing binary search five different ways. I could come up with 2 obvious ways - an imperative style with iteration and a functional style based on the solution inspired by this site . So here goes:

Imperative:

package org.bk.karatechop
 
class KarateChop {
 def chop(aNumber:Int, anArray:Array[Int]):Int = {
  var minIndex=0
  var maxIndex = anArray.length-1
  while(minIndex<=maxIndex){
   var midIndex = (minIndex+maxIndex)/2
   var atMidIndex = anArray(midIndex)
   if (aNumber>atMidIndex){
    minIndex=midIndex+1
   }else if(aNumber<atMidIndex){
    maxIndex=midIndex-1
   }else{
    return midIndex
   }
  }
   
  -1
   
 }
}

Functional:

package org.bk.karatechop
 
class KarateChopRecursive {
 def chop(aNumber:Int, anArray:Array[Int]):Int = {
   
  def recurse(low:Int, high:Int):Option[Int] = { 
   (low + high)/2 match {
    case _ if high < low => None
    case mid if aNumber < anArray(mid)  => recurse(low, mid - 1)
    case mid if aNumber > anArray(mid)  => recurse(mid + 1, high)
    case mid => Some(mid)
   }   
  }
   
  recurse(0,anArray.length-1).getOrElse(-1)
   
   
 }
}

Tuesday, September 7, 2010

Perfect Number implementation using Scala Actor, Spring Integration, Java Executors, Kilim based Actor

A Simple non-threaded (and non-optimized) java implementation for figuring out if a number is a perfect number is the following:

public class SimplePerfectNumberUtil implements PerfectNumberUtil{
 
 @Override
 public boolean isPerfect(int aNumber) {
  return sumOfFactors(aNumber)==2*aNumber;
    }
  
 private int sumOfFactors(int aNumber){
  int sum = 0;
  for (int i=1;i<=aNumber;i++){
   if (aNumber%i==0){
    sum+=i;
   }
  }
   
  return sum;
 }
 
}

Programming Scala book provides a sample scala actor implementation for this by breaking up the task of determining whether a large number is a perfect number by breaking up the large number into a range of smaller numbers - eg. a number like 3000 can be split up into say 0-1000, 1001-2000, 2001-3000, with a task responsible for summing up the factors in each of these ranges and summing up the result.

A slightly modified implementation based on the Programming Scala book is the following:

class PerfectUtilScala {
 
  def isPerfect(candidate: Int) = {
    val RANGE = 10000000
    val numberOfPartitions = (candidate.toDouble / RANGE).ceil.toInt
    val caller = self
     
     
    val sumoffactorsActor = actor{
     loop {
      react {
    case msg:FactorsRangeForCandidate =>
     caller ! sumOfFactorsInRange(msg.lower, msg.upper, msg.candidate)
   }  
  } 
    }
 
 
    for (i <- 0 until numberOfPartitions) {
      val lower = i * RANGE + 1;
      val upper = candidate min (i + 1) * RANGE
       
      sumoffactorsActor ! new FactorsRangeForCandidate(lower, upper, candidate)
    }
 
    val sum = (0 /: (0 until numberOfPartitions)) { (partialSum, i) =>
      receive {
        case sumInRange: Int => partialSum + sumInRange
      }
    }
 
    2 * candidate == sum
  }
 
  private def sumOfFactorsInRange(lower: Int, upper: Int, number: Int) = {
    (0 /: (lower to upper)) { (sum, i) => if (number % i == 0) sum + i else sum }
  }
 
}
 
 
class FactorsRangeForCandidate(val lower:Int, val upper:Int, val candidate:Int)

A Java Executors based implementation is the following:

public class ThreadPoolPerfectNumberUtil implements PerfectNumberUtil{ 
 private ExecutorService threadpool = Executors.newFixedThreadPool(3);
 @SuppressWarnings("unchecked")
    public boolean isPerfect(int aNumber) {
     int RANGE = Constants.RANGE;
     int numberOfPartitions = new Double(Math.ceil(aNumber * 1.0 / RANGE)).intValue();
     Future<integer>[] sumOfFactors = new Future[numberOfPartitions];
      
     for (int i=0;i<numberofpartitions;i++) (anumber="" *="" +="" 1;="" if="" int="" lower="i" range;="" range="" upper="(i+1)*" {=""><upper) (exception="" (int="" (sum="=2*aNumber)" +="sumOfFactors[i].get();" callable="" catch="" class="" e)="" false;="" for="" i="0;i<numberOfPartitions;i++)" if="" implements="" int="" new="" return="" runtimeexception(e);="" sum="0;" sumoffactors[i]="threadpool.submit(new" sumoffactorstask(lower,upper,anumber));="" sumoffactorstask="" throw="" true;="" try="" upper="aNumber;" {="" }=""><integer>{
 
 private final int lower;
 private final int upper;
 private final int anumber;
  
  
 public SumOfFactorsTask(int lower, int upper, int anumber){
  this.lower = lower;
  this.upper = upper;
  this.anumber = anumber;
 }
  
  
 @Override
    public Integer call() {
  int sum=0;
  for (int i=lower;i<=upper;i++){
   if (anumber%i==0){
    sum+=i;
   }
  }  
   
  return sum;
    }
 
}
</integer></upper)></numberofpartitions;i++)></integer>

And a Kilim based actor implementation:

public class ActorsPerfectNumberUtil extends Task implements PerfectNumberUtil {
 
 private Mailbox<factorsrange> mailbox;
 private Mailbox<integer> resultmailbox;
 private SumOfFactorsActor sumOfFactors;
 
 public ActorsPerfectNumberUtil() {
  mailbox = new Mailbox<factorsrange>();
  resultmailbox = new Mailbox<integer>();
  sumOfFactors = new SumOfFactorsActor(mailbox, resultmailbox);
  sumOfFactors.start();
 
 }
 
 public boolean isPerfect(int aNumber) {
  int RANGE = Constants.RANGE;
  int numberOfPartitions = new Double(Math.ceil(aNumber * 1.0 / RANGE)).intValue();
 
  for (int i = 0; i < numberOfPartitions; i++) {
   int lower = i * RANGE + 1;
   int upper = (i + 1) * RANGE;
   if (aNumber < upper)
    upper = aNumber;
   mailbox.putnb(new FactorsRange(lower, upper, aNumber));
  }
 
  int sum = 0;
  for (int i = 0; i < numberOfPartitions; i++) {
    sum += resultmailbox.getb();
  }
 
  if (sum == 2*aNumber)
   return true;
 
  return false;
 }
}
</integer></factorsrange></integer></factorsrange>

The codebase along with the Spring Integration based implementation is available at this Git location:

git://github.com/bijukunjummen/Perfect-Number.git