20-CS-694 Advanced Programming Techniques Spring 2012
Homework Assignment 2

Interfaces, Exceptions, Graphics, Animation, Threads, Reflection, Networking, RMI, JDBC, JNI

Exceptions for Control - Declarative Style

Due: April 17, 2012 (submit instructions: here)

Rationale:
   

Declarative languages such as Prolog have the advantage of requiring no control information from the coder. We can write Java classes to support a declarative style of coding. The idea is to write a class Chooose for assigning possible values to variables, a class for searching over all possible values variables can take, and a class containing a method assert_ which takes a boolean expression as argument and causes a backtrack if the expression evaluates to false.

 
Homework Problem:
Write Java classes and interfaces to support a declarative style of coding. Call the result a "declarative system." Your system should be designed to solve problems using Choose and assert_. The class below is an example of how a user would solve a problem using the declarative system. The problem it intends to solve is known as the Kalotan problem and is stated as follows:

     The Kalotans are a tribe with a peculiar quirk: their males always tell the truth. Their females never make two consecutive true statements, or two consecutive untrue statements.

An anthropologist (let's call him Worf) has begun to study them. Worf does not yet know the Kalotan language. One day, he meets a Kalotan (heterosexual) couple and their child Kibi (also called "kid"). Worf asks the kid: ``Are you a boy?'' The kid answers in Kalotan, which of course Worf doesn't understand.

Worf turns to the parents (who know English) for explanation. One of them says: "Kibi said: `I am a boy.'" The other adds: "Kibi is a girl. Kibi lied."

What is the sex of the parents and Kibi?

 
The Class:

class KalotanPuzzle /* may extend a class and implement interfaces */ {
   // Define the variables of the problem
   Choose parent1, parent2, kid, kid_lied;

   // Define possible values for variables of the problem
   public void solve () {
      parent1  = new Choose("male female", this);
      parent2  = new Choose("male female", parent1);
      kid      = new Choose("male female", parent2);
      kid_lied = new Choose("true false", kid);

      // Check the constraints
      try { 
         kid_lied.check_constraints(); 
      } 
      catch (Exception e) { System.out.println("Done"); }
   }

   public void check_constraints () /* may throw exceptions */ {
      // Parents must be of different sex
      assert_(!parent1.value().equals(parent2.value()));
      // If the first parent responding is male then either
      // the kid is male and did not lie or
      // the kid is female and lied
      assert_(parent1.value().equals("female") ||
              (kid.value().equals("male") &&
               kid_lied.value().equals("false")) ||
              (kid.value().equals("female") &&
               kid_lied.value().equals("true")));
      // If the second parent responding is male then
      // the kid is female and lied
      assert_(parent2.value().equals("female") ||
              (kid.value().equals("female") &&
               kid_lied.value().equals("true")));
      // If the second parent responding is female then
      // either the kid is male and lied or
      // the kid is female and did not lie
      assert_(parent2.value().equals("male") || 
              (kid.value().equals("male") && 
               kid_lied.value().equals("true")) ||
              (kid.value().equals("female") &&
               kid_lied.value().equals("false")));
      // If all assertions are true, print the values of parents, and kid
      System.out.println("Parent1:"+parent1.value()+" "+
                         "Parent2:"+parent2.value()+" "+
                         "Kid:"+kid.value());
      ...			 
   }
}

The following can be a class containing a main procedure for running the above code:

public class Kalotan {
   public static void main (String args[]) {
      KalotanPuzzle k = new KalotanPuzzle();
      k.solve();
   }
}

Note: The Choose constructor has two arguments. The first is the string containing possible values and is necessary. The second is intended to tie all the Choose variables together for searching. It may be possible to dispense with the second argument. If you do, you get extra points.

Note: Creativity will be rewarded. I would be happy if another system is proposed provided it meets the requirement of no control information in user-defined problem formulations.

By the way, you can use your code to color a map of Europe with four colors so that no adjacent countries have the same color. The following shows code to do that:

// Color coutries of Europe
class ColorPuzzle /* may extend a class and implement interfaces */ {
   Choose
      portugal, spain, germany, austria, italy, switzerland,
      france, belgium, luxemburg, holland;

   public void check_constraints () throws Up, Out {
      assert_(!portugal.value().equals(spain.value()));
      assert_(!spain.value().equals(france.value()));
      assert_(!france.value().equals(italy.value()));
      assert_(!france.value().equals(switzerland.value()));
      assert_(!france.value().equals(belgium.value()));
      assert_(!france.value().equals(germany.value()));
      assert_(!france.value().equals(luxemburg.value()));
      assert_(!belgium.value().equals(holland.value()));
      assert_(!belgium.value().equals(germany.value()));
      assert_(!belgium.value().equals(luxemburg.value()));
      assert_(!holland.value().equals(germany.value()));
      assert_(!germany.value().equals(switzerland.value()));
      assert_(!germany.value().equals(austria.value()));
      assert_(!germany.value().equals(luxemburg.value()));
      assert_(!italy.value().equals(switzerland.value()));
      assert_(!italy.value().equals(austria.value()));
      assert_(!switzerland.value().equals(austria.value()));

      // If all assertions are true, print the colors
      System.out.println("Portugal:"    +portugal.value()    +" "+
			 "Spain:"       +spain.value()       +" "+
			 "France:"      +france.value()      +" "+
			 "Belgium:"     +belgium.value()     +" "+
			 "Holland:"     +holland.value()     +" "+
			 "Germany:"     +germany.value()     +" "+
			 "Luxemburg:"   +luxemburg.value()   +" "+
			 "Italy:"       +italy.value()       +" "+
			 "Switzerland:" +switzerland.value() +" "+
			 "Austria:"     +austria.value()     +" ");
      ...
   }

   public void solve () {
      portugal    = new Choose("red green blue yellow", this);
      spain       = new Choose("red green blue yellow", portugal);
      france      = new Choose("red green blue yellow", spain);
      belgium     = new Choose("red green blue yellow", france);
      holland     = new Choose("red green blue yellow", belgium);
      germany     = new Choose("red green blue yellow", holland);
      luxemburg   = new Choose("red green blue yellow", germany);
      italy       = new Choose("red green blue yellow", luxemburg);
      switzerland = new Choose("red green blue yellow", italy);
      austria     = new Choose("red green blue yellow", switzerland);
      try { austria.check_constraints(); } 
      catch (Exception e) { System.out.println("Done"); }
   }
}

public class Colors {
   public static void main (String args[]) {
      ColorPuzzle k = new ColorPuzzle();
      k.solve();
   }
}

OK, that was an easy one. But you can try the next puzzle on your own:

No owners have the same pet, smoke the same brand of cigar, or drink the same beverage. The question is: Who owns the fish?

Hints:
* the Brit lives in the red house
* the Swede keeps dogs as pets
* the Dane drinks tea
* the green house is on the left of the white house
* the green house's owner drinks coffee
* the person who smokes Pall Mall rears birds
* the owner of the yellow house smokes Dunhill
* the man living in the center house drinks milk
* the Norwegian lives in the first house
* the man who smokes blends lives next to the one who keeps cats
* the man who keeps horses lives next to the man who smokes Dunhill
* the owner who smokes BlueMaster drinks beer
* the German smokes Prince
* the Norwegian lives next to the blue house
* the man who smokes blend has a neighbor who drinks water

   

Kalotan Puzzle
   

Color Europe Puzzle
 

Five Pet Owners Puzzle