teaching machines

CS 145 Lecture 18 – Common array algorithms

April 5, 2012 by Chris Johnson. Filed under cs145, lectures, spring 2012.

Agenda

• summarizing
• optimizing
• filtering
• linear search
• state-capital lookup

TODO

• Read sections 7.3-7.4.

Reverse Engineering

Code

CapitalLookup.java

package preexam2;

import java.util.Scanner;

public class CapitalLookup {
  private static String[] states = {
    "Alabama",
    "Alaska",
    "Arizona",
    "Arkansas",
    "California",
    "Colorado",
    "Connecticut",
    "Delaware",
    "Florida",
    "Georgia",
    "Hawaii",
    "Idaho",
    "Illinois",
    "Indiana",
    "Iowa",
    "Kansas",
    "Kentucky",
    "Louisiana",
    "Maine",
    "Maryland",
    "Massachusetts",
    "Michigan",
    "Minnesota",
    "Mississippi",
    "Missouri",
    "Montana",
    "Nebraska",
    "Nevada",
    "New Hampshire",
    "New Jersey",
    "New Mexico",
    "New York",
    "North Carolina",
    "North Dakota",
    "Ohio",
    "Oklahoma",
    "Oregon",
    "Pennsylvania",
    "Rhode Island",
    "South Carolina",
    "South Dakota",
    "Tennessee",
    "Texas",
    "Utah",
    "Vermont",
    "Virginia",
    "Washington",
    "West Virginia",
    "Wisconsin",
    "Wyoming",
  };
  
  private static String[] capitals = {
    "Montgomery",
    "Juneau",
    "Phoenix",
    "Little Rock",
    "Sacramento",
    "Denver",
    "Hartford",
    "Dover",
    "Tallahassee",
    "Atlanta",
    "Honolulu",
    "Boise",
    "Springfield",
    "Indianapolis",
    "Des Moines",
    "Topeka",
    "Frankfort",
    "Baton Rouge",
    "Augusta",
    "Annapolis",
    "Boston",
    "Lansing",
    "St. Paul",
    "Jackson",
    "Jefferson City",
    "Helena",
    "Lincoln",
    "Carson City",
    "Concord",
    "Trenton",
    "Santa Fe",
    "Albany",
    "Raleigh",
    "Bismarck",
    "Columbus",
    "Oklahoma City",
    "Salem",
    "Harrisburg",
    "Providence",
    "Columbia",
    "Pierre",
    "Nashville",
    "Austin",
    "Salt Lake City",
    "Montpelier",
    "Richmond",
    "Olympia",
    "Charleston",
    "Madison",
    "Cheyenne",
  };
  
  public static void removeSixOrLess() {
//    states[1] = null;
    
    int nFittest = 0;
//    for (int i = 0; i < states.length; ++i) {
    for (String state : states) {
      if (state.length() > 6) {
        ++nFittest;
      }
    }
    
    String[] theFittest = new String[nFittest];
    int j = 0;
    for (int i = 0; i < states.length; ++i) {
      if (states[i].length() > 6) {
        theFittest[j] = states[i];
        ++j;
      }
    }
    
    states = theFittest;
  }
  
  public static String getCapital(String state) {
   
    for (int i = 0; i < states.length; ++i) {
      if (state.equals(states[i])) {
        // we've got it!
        return capitals[i];
      }
    }
    
    return "Fooville";
  }
  
  public static void main(String[] args) {
    
    removeSixOrLess();
    Scanner in = new Scanner(System.in);
    
    while (in.hasNextLine()) {
      String needle = in.nextLine();
      System.out.println(getCapital(needle));
    }
  }
}

Haiku