## 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[] sumOfFactors = new Future[numberOfPartitions];

for (int i=0;i{

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;
}

}
```
And a Kilim based actor implementation:

```public class ActorsPerfectNumberUtil extends Task implements PerfectNumberUtil {

private Mailbox mailbox;
private Mailbox resultmailbox;
private SumOfFactorsActor sumOfFactors;

public ActorsPerfectNumberUtil() {
mailbox = new Mailbox();
resultmailbox = new Mailbox();
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;
}
}
```
The codebase along with the Spring Integration based implementation is available at this Git location:
`git://github.com/bijukunjummen/Perfect-Number.git`