Friday, November 20, 2009

Can we use a computer from Nature to attack the Traveling Salesman Problem?


The traveling salesman problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem) tries to find the shortest route covering all points in a plane.


If all points are on a circle, it seems that the shortest route passes from point to point in the order that they are on the circle. Of course, not following the curve, but the straight line between two adjacent cities on the curve.

So I wondered if a general solution would be to find the circle that is a best fit for all points, and then travel along the circle picking the next point to visit - from the previous one.

How about a system from Nature that can simultaneously compute this?

Have a circular coil of wire on a sheet of plastic. The diameter should be in the approximate range of the points. The points are represented by small powerful permanent magnets each with a electromagnetic coil and a bulb - or an ammeter to measure current. The magnets are positioned in a vessel of water, and in the same relative coordinates as in the real world problem.

The sheet of plastic floats over the magnets below. Passing an electric current through the coil moves the floating sheet around and produces a best-fit position for the circle.

Now anchor the sheet so the coil does not move.

Now have a magnet travel around the track, the dog, at relatively high speed. It starts closest to the origin point. Mark this. A current is generated in each coil. The bulb that lights up first - the sensor that picks up the strongest reading - is the point to move next to. And so on.

Of course, you can do this in sophisticated ways, but this is all I know, and is easy to explain to a high school kid. The idea is to use a Natural computer.

(background: I wrote a toy program to solve the Robot Tour Optimization exercise problem in Steven Skiena's book, "The Algorithm Design Manual" and got this idea).

Friday, July 24, 2009

How to handle nested beans using Commons-dbutils

Background:
When we query data from the database, we fill it into objects. These objects are called beans and conform to certain guidelines to make them easy to manipulate automatically by the GUI and other components. The data fields of a bean are called properties and have a getter and setter method for each property.
We use the open source database utility software, commons-dbutils from the Apache Project, to query the database. Each field in the SQL query is aliased to have the same name as the bean property so that the bean can be automatically created and filled in when the query is executed.

Problem:
Some of our beans contain object references to other beans. Those nested beans may have properties that are intended to be filled in by one or more fields from a query. However, since it is not on the surface, Dbutils cannot find where the property is and so the nested property remains unfilled.

Example:
Consider a table Moods to track our demeanor while we engage in an activity. So it has two columns; face (demeanor) and activity.

Face Activity
huffing Jog
smile Work
engrossed movie
sad Cry
distant distracted
bored waiting


Bean Foo contains an object reference to an instance – a bean- of class Bar. Foo contains data field or property ‘face’, and Bar contains the property ‘activity’, that we want to fill from this query:
“select face, activity from Mood”

public class Foo {
private String face;
private Bar bar;
public String getFace() {return face;}
public void setFace(String face) {this.face = face;}
public void setBar(Bar bar) {this.bar = bar;}
public Bar getBar() {return bar;}
}
public class Bar {
private String activity;
public String getActivity() {return activity;}
public void setActivity(String activity) {this.activity = activity;}
}

Old way:
QueryRunner runner = new QueryRunner();
BeanHandler bh = new BeanHandler(Foo.class);
Foo foo = (Foo) runner.query(connection,
"select face, activity from Mood", bh);

Result:
Foo.bar is null and its fields are unpopulated.

Solution:
1) For each nested bean, users will provide a mapping of property to nested object reference so that the property can be found. In the above example, that would be: “bar”ßà [‘activity’, Bar.class]
2) A new class, NestedBeanProcessor inherits from the BeanProcessor class in Dbutils. It overrides the toBean() method. When this method is called to populate a bean from a result set, it asks the superclass to fill in the data. Then it examines each mapping. Using Java Reflection, it retrieves the nested reference. If this is null, it creates the nested bean. Next, it retrieves the value of the field in the result set and calls the setter method on the bean.
3) To fill a list of Foo beans with singly nested member(s), use a BeanListHandler.
4) In the case where Foo contained a list of nested beans:
for example
ArrayList bar;
There is no way to specify this one-many relationship in Dbutils for automatic filling of bar.activity from the top-level query. Dbutils cannot discern whether a ResultSet row is a new instance of a top-level bean to be created, or whether it must retrieve the reference of a bean previously created and add a new bean to the nested list it contains.
In other words, you must provide an object reference for the level below it to be filled. We would in this case, fill in the fields of Foo and then use this instance to run a second query, using the BeanListHandler to fill in the bar list and any nested fields of Bar.

Constraint:
1) For now, we shall handle nesting that is one level deep.
2) As in 4) above,

New way: (How users will call it):

Hashtable ht = new Hashtable();
PropertyDescriptor prop = new PropertyDescriptor("activity", Bar.class);
ht.put(prop, "bar");
NestedBeanProcessor nbp = new NestedBeanProcessor(ht);
QueryRunner runner = new QueryRunner();
BasicRowProcessor burp = new BasicRowProcessor(nbp);
BeanHandler bh = new BeanHandler(Foo.class, burp);
Foo foo = (Foo) runner.query(connection, "select face, activity from Mood", bh);
System.out.println(foo.getFace() + " during this activity: " + foo.getBar().getActivity());

Result:
huffing during this activity: jog

Note: we used a BeanHandler. To fill in all the beans, use a BeanListHandler.

Design:

public class NestedBeanProcessor extends BeanProcessor {

…relevant methods shown…

Hashtable propertyForBeanMember;

public NestedBeanProcessor(
Hashtable propertyForBeanMember) {
super();
this.propertyForBeanMember = propertyForBeanMember;
}
@Override
public Object toBean(ResultSet rs, Class type) throws SQLException {
Object bean = super.toBean(rs, type);
Enumeration keys = propertyForBeanMember.keys();
while (keys.hasMoreElements()) {
PropertyDescriptor property = keys.nextElement();
Class beanClass = bean.getClass();
try {
String fieldName = propertyForBeanMember.get(property);
String fieldNameCapitalized = fieldName.substring(0, 1)
.toUpperCase()
+ fieldName.substring(1);
String fieldGetterName = "get" + fieldNameCapitalized;
String fieldSetterName = "set" + fieldNameCapitalized;
Method fieldGetterMethod = beanClass
.getDeclaredMethod(fieldGetterName);
Method fieldSetterMethod = null;
// we have to go thru all the methods because
// PropertyDescriptor doesn't seem to provide a way to retrieve
// the fieldClass
// i.e. we would have liked to simply do
// fieldSetterMethod = beanClass.getDeclaredMethod(fieldSetterName, Bar.class);
Method[] allMethods = beanClass.getDeclaredMethods();
for (Method m : allMethods) {
String mname = m.getName();
if (mname.equals(fieldSetterName)) {
fieldSetterMethod = m;
break;
}
}
Field beanField = beanClass.getDeclaredField(fieldName);
Class nestedBeanType = beanField.getType();
Object nestedBeanValue = fieldGetterMethod.invoke(bean);
// nestedBeanValue is the value in the reference
if (nestedBeanValue == null) {
// create
nestedBeanValue = nestedBeanType.newInstance();
// set value to new instance
fieldSetterMethod.invoke(bean, nestedBeanValue);
}
System.out.println(" property :" + property
+ " target nested Bean: " + nestedBeanValue);
Class propType = property.getPropertyType();
Object targetValue = this.processColumn(rs, rs
.findColumn(property.getName()), propType);
if (propType != null && targetValue == null
&& propType.isPrimitive()) {
targetValue = primitiveDefaults.get(propType);
}
this.callSetter(nestedBeanValue, property, targetValue);
} catch (Exception e) {
e.printStackTrace();
throw new SQLException(e.getMessage());
}
}
return bean;
}

Sunday, June 7, 2009

Understanding why George Tiller performed partial birth abortions with an untroubled conscience

“These are the things we do,” he said, pointing to color snapshots of aborted fetuses. “Hydrocephalus, spina bifida, fused legs, open spine, lethal chromosome abnormality. Nature makes mistakes.”
George Tiller, Wichita abortion doctor, shot dead in June 2009.

Reading this quote in the newspaper article by Judy Thomas, I suddenly understood how someone who performed late term abortions could live with an untroubled conscience. Even though he was an usher at his liberal Lutheran church, he apparently believed that babies were created by Nature, not God. He believed that a woman, and the planet, should not be burdened by one of Nature's grotesque mistakes. In contrast, the pro-lifer believes that even deformed babies were created by God for a purpose, and that we do not have the authority to decide what the cutoff point should be - to grant life or death. Who knows what wonders God can do with a seemingly worthless lump of clay?
This is consistent with pro-life support for the death penalty. God, as described in the major religions, requires man to administer justice - even to the point of taking life.

Monday, May 11, 2009

Memories of Cedar Lake

"Fond memories from my boyhood..." (Chris said)

Sunday, March 8, 2009

iphone or android development?

For those wondering whether to chose iphone or android development, here is a great blow-by-blow narrative by Ed Burnette

He also has this website androidandme
Personally, I am trying to decide whether to switch to iphone development as I have lost much due to android, but there will be a significant learning curve as I have never touched MacOS nor Objective C.

Thursday, February 26, 2009

Before you startup, count the cost

Update: Praise God for a job offer I received from a company that is implementing a project
at the US Dept of Agriculture in Kansas City, MO. It is a web based project for farmers to apply for disaster relief.
Honestly, I was not looking to work in that domain area and server side but we see God's hand in it and know that I must fit in with His plan. Also, He sees things that I do not.


Jesus said, "Before you follow me, count the cost".

I found that none of the startup evangelists - Guy Kawasaki, Paul Graham etc. mention this aspect of counting the cost.

Can you get a decent job again if your startup fails?

"Oh, sure" you think, "My startup experience broadened my technical and business perspective and should be valuable to any employer". I am finding out it isn't true.

1. "I am suspicious of you"

No one says it so bluntly, but employers wonder if I will be "double-dipping" as a recruiter explained to me. They wondered if I would remain passionate about juwo and work it on the side. The problem is, it is on my resume and so when asked about it, I do explain what it does and then it goes downhill from there. Whether my belief in the validity of the idea it is a giveaway, I don't know. It is almost like marrying someone who recently had a girlfriend and still has feelings for her! I have since removed the website content at juwo.com.

2. Is the technology you use in your startup exactly the same as what employers use in your city?

juwo uses Java in general, and specifically: Swing for the desktop version, and Google Android for the mobile version. Employers in Kansas City are mostly back-end server side. So they need stuff like Spring, Hibernate, JSP, Struts, J2EE and Java Faces, Ajax for the server client. It is not sufficient to learn these from a tutorial; one must have actual project experience to be considered. My JSP/J2EE experience is about 4 years old. So as a contractor, employers prefer someone who worked in it just yesterday.

3. How old are you? or to put it another way, how many years of experience do you have.

The ideal age is someone with 5 years of relevant experience - someone who can be moulded and who will "grow with the company" as another recruiter said. I have 18 years of software development. Too old it seems, as an employee. As a contractor? As I said above, now my experience is too old.

So what now? As I search and wait, I have been reimplementing a new version of juwo and is a few weeks from completion. It will hopefully, be easier to use and also renamed to List Of Blocks.
I simply want to fill up this gaping hole of failure and at least get users who will use it and find it useful.