The Java Program: North.java

  1 // North.java
  2 
  3 import java.util.Iterator;
  4 import java.util.Set;
  5 import java.util.HashSet;
  6 import java.util.HashMap;
  7 import java.util.StringTokenizer;
  8 import java.io.IOException;
  9 import java.io.InputStreamReader;
 10 import java.io.BufferedReader;
 11 
 12 public class North {
 13 
 14    /*
 15      The main data structure is a hash table of sets.  Associated with
 16      (southern) cities is a set of all cities directly to the north.
 17      Essentially, this is a directed graph with unordered edges.
 18    */
 19    static final HashMap HM = new HashMap ();
 20 
 21    public static void add_north (String c, String n) {
 22       if (HM.containsKey (c)) {
 23          final Set s = (Set) HM.get (c);
 24          s.add(n);
 25       } else {
 26          final HashSet hs = new HashSet ();
 27          HM.put (c, hs);
 28          hs.add (n);
 29       }
 30    }
 31 
 32    public static boolean is_north (String c, String n) {
 33       if (HM.containsKey (c)) {
 34          final HashSet hs = (HashSet) HM.get (c);
 35          if (hs.contains (n)) {
 36             return true;   // n is directly north of c
 37          } else {
 38             // look for some city north of c and south of n
 39             for (Iterator i=hs.iterator(); i.hasNext(); ) {
 40                if (is_north ((String) i.next(), n)) return true;
 41             }
 42             return false;
 43          }
 44       }
 45       return (false);
 46    }
 47 
 48    private static String beg = "The relative position of ";
 49    public static void relate (String c, String n) {
 50       String msg = beg;
 51       if (is_north (c,n)) {
 52          msg = c + " is south of " + n;
 53       } else if (is_north (n, c)) {
 54          msg = c + " is north of " + n;
 55       } else {
 56          msg = beg + c + " and " + n + " is unknown";
 57       }
 58       System.out.println (msg+".");
 59    }
 60 
 61    public static void main (String[] args) throws IOException {
 62 
 63       final BufferedReader br = new BufferedReader (
 64          new InputStreamReader (System.in));
 65 
 66       for (;;) {
 67          final String line = br.readLine();
 68          if (line==null) break;
 69          final StringTokenizer st = new StringTokenizer (line, " #");
 70          if (st.countTokens()!=2) break;
 71          final String city1 = st.nextToken(), city2=st.nextToken();
 72          add_north (city1, city2);
 73       }
 74 
 75       for (;;) {
 76          final String line = br.readLine();
 77          if (line==null) break;
 78          final StringTokenizer st = new StringTokenizer (line, " #");
 79          if (st.countTokens()!=2) break;
 80          final String city1 = st.nextToken(), city2=st.nextToken();
 81          relate (city1, city2);
 82       }
 83    }
 84 }