Saturday, January 7, 2012

Object Messaging in Java

One of the great things about Objective-C in MacOS is its dynamic messaging and delegation capabilities. Any object can delegate its messages to any other object. Java on the other hand is very strongly typed to detect and avoid problems at runtime.

I was thinking, if it would be possible to implement something like a dynamic messaging system in Java where any message can be posted to any object at runtime and if that object wants, it can optionally pre-process it, delegate it, or post process it. So, I made an abstract class called MessageDelegate and any class that implements it can receive, process and/or delegate messages.

Any object can register itself as a delegate of another object and that object would not have to know about it. Any object can choose not to implement pre or post processing, in which case the chain would continue. Any if one object has actually dealt with a particular message and wants to stop further processing, it can indicate with a return type.

This allows for a nice lazy programming style in java. However, there is a dark side to it as well. The problems include:
  • Not very flexible because most classes one writes are already extended from some interface or the other.
  • Cyclic messaging infinite loops.
  • Runtime exceptions. I've dealt with it by making sure messages are only string maps.
I've put up the classes on GitHub here. But you can see the following code on how it might be used in your code. Note that its not thread safe yet. If anyone wants to improve it, feel free to make your own fork and push any changes back to me :)

Next time maybe dynamic messaging in C++. I think C++ (much closer to Objective-C is much better suited for this kind of thing with void pointers and easy casting. Much riskier at runtime as well.





package com.fahdrafi.messagetest;

import com.fahdrafi.Messaging.Message;
import com.fahdrafi.Messaging.MessageDelegate;

public class DelegationTest extends MessageDelegate {
private String name = new String("unassigned");
// Optionally implement pre-processing method
public boolean PreProcess(Message msg) {
// first check to see if the message type is something you want to process
if (!msg.get(Message.MSG_TYPE).equals("PrintAction")) return false;
// do any processing you want here
//
//
//
System.out.println(name + " pre-processing: " + msg.get("PrintMessage"));
// return true if you have processed it and do not want further processing
// return false if you have not processed it
return false;
}
// similar post-processing after delegation
public boolean PostProcess(Message msg) {
if (!msg.get(Message.MSG_TYPE).equals("PrintAction")) return false;
System.out.println(name + " post-processing: " + msg.get("PrintMessage"));
return false;
}
DelegationTest(String newName) {
this.name = newName;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// Create any objects
DelegationTest o1 = new DelegationTest("Object 1");
DelegationTest o2 = new DelegationTest("Object 2");
DelegationTest o3 = new DelegationTest("Object 3");
DelegationTest o4 = new DelegationTest("Object 4");

// Add delegation to them
o1.AddDelegate(o2);
o2.AddDelegate(o3);
o3.AddDelegate(o4);
// Make a new message (its essentially a hashmap which returns "" if nothing is assigned to a key)
Message m = new Message("PrintAction");
m.put("PrintMessage","Hello Messaging!");
// Delegate(message) or Post(message) (Post only delegates and does not pre/post process messages
o1.Delegate(m);
}

}



Wednesday, January 4, 2012

Looking for Adventure

This was another interesting word puzzle I came across that I thought might be an interesting problem to solve:

Nine friends, looking for adventure, decided to race down a nearby highway. They had three cars: a Ferrari, a Mercedes, and a BMW. They divided themselves into three groups of three each. A destination was identified and they started the race. 


One car had an accident. Another car had an engine failure. Only the third car managed to reach the destination. 

  • Okum, Olfum, and Ogum were not in the Mercedes. Also, all three were not in the same car. 
  • Ofrum was not in the car that had the accident. 
  • Obum and Okum were in the same car. It was not the one that had engine failure. 
  • Ovum, whose car didn't have an accident, was not in the same car as either Ogum or Okum. 
  • Ogum was in the BMW along with Oskum. 
  • Opum and Odum were in the same car. It was not the one that had engine failure. 

Based on the above information, which friends were in which car and how did the each car perform in the race? 

Regardless of who won the race, they certainly had very silly names!

Now for the interesting part, the Prolog solution:


Sol = [[merc, [ovum, opum, odum], success], [ferrari, [okum, olfum, obum], accident], [bmw, [ogum, ofrum, oskum], engine]]

Translated into english as follows:
  • Ovum, Opum and Odum finished the race in their Merc.
  • Okum, Olfum and Obum crashed their Ferrari.
  • Ogum, Ofrum and Oskum broke down in their BMW.
The code listing below finds the solution.

not(Thing) :- call(Thing),!,fail.
not(Thing).

start(Sol):- Sol=[[merc,Mpeople,_],[ferrari,Fpeople,_],[bmw,Bpeople,_]],
Mpeople=[_,_,_],Fpeople=[_,_,_],Bpeople=[_,_,_],
member([_,Apeople,accident],Sol),
member([_,Epeople,engine],Sol),
member([_,Speople,success],Sol),
(member(okum,Mpeople);member(okum,Fpeople);member(okum,Bpeople)),
(member(olfum,Mpeople);member(olfum,Fpeople);member(olfum,Bpeople)),
(member(ogum,Mpeople);member(ogum,Fpeople);member(ogum,Bpeople)),
(member(obum,Mpeople);member(obum,Fpeople);member(obum,Bpeople)),
(member(ovum,Mpeople);member(ovum,Fpeople);member(ovum,Bpeople)),
(member(opum,Mpeople);member(opum,Fpeople);member(opum,Bpeople)),
(member(ofrum,Mpeople);member(ofrum,Fpeople);member(ofrum,Bpeople)),
(member(odum,Mpeople);member(odum,Fpeople);member(odum,Bpeople)),
(member(oskum,Mpeople);member(oskum,Fpeople);member(oskum,Bpeople)),
not(member(okum,Mpeople)), not(member(olfum,Mpeople)), not(member(ogum,Mpeople)),
not((member(okum,Bpeople),member(olfum,Bpeople),member(ogum,Bpeople))),
not((member(okum,Fpeople),member(olfum,Fpeople),member(ogum,Fpeople))),
not(member(ofrum,Apeople)),
(member(Somepeople,[Apeople,Speople]), member(okum,Somepeople), member(obum,Somepeople)),
not(member(ovum,Apeople)),
not((member(Somepeople1,[Speople,Epeople]),member(ovum,Somepeople1),member(ogum,Somepeople1))),
not((member(Somepeople2,[Speople,Epeople]),member(ovum,Somepeople2),member(okum,Somepeople2))),
member(ogum,Bpeople),
member(oskum,Bpeople),
(member(Somepeople3,[Apeople,Speople]), member(opum,Somepeople3), member(odum,Somepeople3)),
!.

Jim Lies, Prolog Doesn't!

This is a rather famous puzzler, the answer to which is available on many websites. However, solving problems on a piece of paper is not always as interesting as writing a program to solve it. Prolog seems to be the best suited language to solve such constraint based problems. For those of you who do not know the problem and came to this blog anyway, here is the problem:


Jim lies a lot. He tells the truth only one day in a week. One day he said: "I lie on Mondays and Tuesdays." The next day he said: "Today is either Sunday, Saturday or Thursday." The next day he said: "I lie on Fridays and Wednesdays." On which day of the week does Jim tell the truth?

As we can see, trying to write C or Java code might get a little complicated. Here is the Prolog code that solves the problem on the predicate "start(Day)".

not(P) :- call(P),!,fail.
not(_).

dayone([false,false,Wednesday,Thursday,Friday,Saturday,Sunday]).
daytwo([Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday]) :-
(Sunday=true;Saturday=true;Thursday=true).
daythree([Monday,Tuesday,false,Thursday,false,Saturday,Sunday]).
dayafter([D1,D2,D3,D4,D5,D6,D7],[D2,D3,D4,D5,D6,D7,D1]).

start(Day) :- (
Day =[true,false,false,false,false,false,false];
Day =[false, true,false,false,false,false,false];
Day =[false,false, true,false,false,false,false];
Day =[false,false,false, true,false,false,false];
Day =[false,false,false,false, true,false,false];
Day =[false,false,false,false,false, true,false];
Day =[false,false,false,false,false,false, true]
),
dayafter(Day,Dayafter), dayafter(Dayafter,Day2After),
(
not(dayone(Day)),not(daytwo(Dayafter)),not(daythree(Day2After));
(dayone(Day)),not(daytwo(Dayafter)),not(daythree(Day2After));
not(dayone(Day)),(daytwo(Dayafter)),not(daythree(Day2After));
not(dayone(Day)),not(daytwo(Dayafter)),(daythree(Day2After))
).

Yes .. its Tuesday!

Yet Another AVL Tree Implementation in C/C++

I recently was asked to do an AVL Tree implementation in C/C++. I've kept this implementation rather simple with no AVL Tree class and focus on the algorithm itself. So the tree is represented by a pointer to the HEAD Node and modifying functions take a double pointer to this node.

The main() function tests the tree by adding and deleting random numbers into and from the tree.


/*
 * Tree.cpp
 * AVL Tree - Always balanced with maximum left and right sub-tree height difference of 1!
 *  Created on: Oct 14, 2011
 *      Author: Fahd
 */

#include <iostream>

using namespace std;

// utility
#define MAX(X,Y) (X>Y?X:Y)

// node structure
struct node {
int data;
node* left;
node* right;

int height; // interim use .. value not necessarily consistent with state
};

// returns pointer to pointer to node with "data", if not then NULL
node** avlLookup(node** tree, int data) {
node** current = tree;
while (*current) {
if ((*current)->data == data) return current;
if (data < (*current)->data) current = &((*current)->left);
else current = &((*current)->right);
}
return NULL;
}

// new node with required data set
node* newNode(int data) {
node* n = new node;
n->data = data;
n->left = NULL;
n->right = NULL;
n->height = -1;
return n;
}

// computes tree heights at each node (given subtree heights are done)
int avlComputeHeight(node* tree) {
if (!tree) return 0;
int leftHeight = (tree->left)?(tree->left->height):0;
int rightHeight = (tree->right)?(tree->right->height):0;
tree->height = MAX(leftHeight,rightHeight)+1;
return tree->height;
}

// returns difference between left and right subtree heights
int avlHeightDifference(node** ppNode) {
if (!(*ppNode)) return 0;
int rightHeight = ((*ppNode)->right)?(*ppNode)->right->height:0;
int leftHeight = ((*ppNode)->left)?(*ppNode)->left->height:0;
return rightHeight - leftHeight;
}

// Balances an unbalanced tree
void avlRebalance(node** balancePoint) {

if (!(*balancePoint)) return;

// balance subtrees first
avlRebalance(&((*balancePoint)->right));
avlRebalance(&((*balancePoint)->left));

// compute height of self node
avlComputeHeight(*balancePoint);

// if height difference is less than 2 then return
if (abs(avlHeightDifference(balancePoint))<2)
return;

// test which subtree is heavier
if (avlHeightDifference(balancePoint)>0) {
// if right subtree is heavier
node* newRoot = (*balancePoint)->right;
node* newLeftRight = (*balancePoint)->right->left;
node* newLeft = *balancePoint;
*balancePoint = newRoot;
newRoot->left = newLeft;
newRoot->left->right = newLeftRight;
} else {
// if left subtree is heavier
node* newRoot = (*balancePoint)->left;
node* newRightLeft = (*balancePoint)->left->right;
node* newRight = *balancePoint;
*balancePoint = newRoot;
newRoot->right = newRight;
newRoot->right->left = newRightLeft;
}
}

// inserts a new node into tree and balances if needed
void avlInsert(node** tree, int data) {
node** insertionPoint = tree;
// find where to insert into tree
while (*insertionPoint) {
if (data == (*insertionPoint)->data) {
// if already in tree, ignore insert
cout<<"Data ["<<data<<"] already in tree, ignoring insert"<<endl;;
return;
}
if (data < (*insertionPoint)->data) {
// insert into left subtree
insertionPoint = &((*insertionPoint)->left);
}
else {
// insert into right subtree
insertionPoint = &((*insertionPoint)->right);
}
}

// insert new node
*insertionPoint = newNode(data);

// balance if needed
avlRebalance(tree);

return;
}

// recursive print tree (for testing only)
void avlPrint(node* tree) {
if (!tree) return;
cout<<"Node: "<<tree->data;

cout<<", Left: ";
if (tree->left) cout<<tree->left->data;
else cout<<"-";

cout<<", Right: ";
if (tree->right) cout<<tree->right->data;
else cout<<"-";

cout<<endl;

avlPrint(tree->left);
avlPrint(tree->right);
}

// get right most node (predecessor of node about to be deleted)
node** avlRightMost(node** tree) {
node** result = tree;
while ((*result)->right) {
result = &((*result)->right);
}
return result;
}

// delete node with "data" in "tree"
void avlDelete(node** tree, int data) {
if (!(*tree)) return;

// find which node to delete
node** ppRequiredNode = avlLookup(tree, data);

// if node found
if (ppRequiredNode) {
node* pNode = *ppRequiredNode;
if (!(pNode->left) && !(pNode->right)) {
// if leaf node
delete pNode;
*ppRequiredNode = NULL;
} else if (pNode->left && pNode->right) {
// if node has both left and right subtrees
node** rightMost = avlRightMost(&(pNode->left));
pNode->data = (*rightMost)->data;
node* toDel = *rightMost;
*rightMost = (*rightMost)->left;
delete toDel;
} else if (pNode->left) {
// if only left subtree exists
*ppRequiredNode = pNode->left;
delete pNode;
} else {
// if only right subtree exists
*ppRequiredNode = pNode->right;
delete pNode;
}

// rebalance if needed after delete
avlRebalance(tree);
} else {
// if node is not in tree
cout<<"Nothing to delete."<<endl;
}
}


// main function to setup test environment
int main() {
// make tree
node* tree = NULL;

srand(0);

// randomly insert and delete nodes into and from tree (nodes 0~14)
for (int i=0; i<100; i++) {
if (rand()%2) {
avlInsert(&tree, rand()%15);
} else {
avlDelete(&tree, rand()%15);
}
}

// print tree after operations
avlPrint(tree);

// lookup all nodes in tree
for (int reqData = 0; reqData<15; reqData++) {
node** requiredNode = avlLookup(&tree, reqData);
if (requiredNode) {
cout<<reqData<<" Found."<<endl;
} else {
cout<<reqData<<" Not found."<<endl;
}
}

return 0;
}



Scala Divisibility

So I was looking for some simple yet interesting problems to solve that would help me explore the power of Scala. That lead me to ProjectEuler.net. I would highly recommend this site to anyone interested in puzzle solving. The problem I started with was as follows:

"What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?"

The problem is simple enough, but I the goal was to solve the problem in a "Functional" way so as to utilize the power of Scala. So no loops!

Following is the final code listing that solves this problem without using any loops. Also, I tried to avoid any "var"iables but some "val"use are used for efficiency. But then that is the power of Scala to combine functional with non-functional code!


import scala.collection.mutable.HashMap

object Divisibility {
  val range = 2 to 20 // Range of numbers we are working on
  val primes = range.filter(prime(_)) // Prime numbers in the range

  // Test for prime number (Note: can be faster if tested until sqrt(n) instead of n/2
  def prime(n:Int): Boolean = n match {
    case 1 => false
    case _ => !(2 to scala.math.ceil(n/2).toInt).exists( n % _ == 0)
  }
  
  // Function that returns a list of prime factors of a given integer
  def factorize(n:Int): List[Int] = primes.find(n%_==0) match {
    case Some(p) => p::factorize(n/p)
    case None => Nil
  }
  
  // Function that returns the powers of prime factors of a number
  def factorCount(n:Int): List[Int] = {
    val factors = factorize(n)
    return primes.map(p => factors.count(_==p)).toList
  }
  
  // Element-wise maximum list for two lists
  def listMax(l1:List[Int], l2:List[Int]): List[Int] = (l1 zip l2).map(x => scala.math.max(x._1,x._2))
  
  // Main function to calculate the required value "v"
  def main(args: Array[String]): Unit = {
    val maxFactors = (range.map(factorCount(_))).reduce(listMax(_,_))
    val v = (primes zip maxFactors).map(x => scala.math.pow(x._1,x._2).toInt).reduce(_*_)
    
    println(v)
  }
}