Return Statements in Closures

I found an interesting little "quirk" that I was not expecting with Groovy today having to do with return statements in a closure.

Let's say I have some code like this:

String someMethod(){
 def myList = ["1", "a", "test", "z"]
 myList.each{
  println "in each loop for: " + it
  if(it == "test"){
   println "\tfound"
   return it
  }
  println "\tafter if"
 }
}

def value = someMethod()
println value;

The output is:

in each loop for: 1
 after if
in each loop for: a
 after if
in each loop for: test
 found
in each loop for: z
 after if
[1, a, test, z]

I was hoping for this:

in each loop for: 1
 after if
in each loop for: a
 after if
in each loop for: test
 found
test

Where it would return from the method once the value is found. It turns out each{} doesn't work this way. I am sure there are good (complicated) reasons for this, but for now I'm just going to change my method to use a good old for loop.

String someMethod2(){
 def myList = ["1", "a", "test", "z"]
 for(int i = 0; i < myList.size; i++){
  println "in each loop for: " + myList[i]
  if(myList[i] == "test"){
   println "\tfound"
   return myList[i]
  }
  println "\tafter if"
 }
}

Read more...

Groovy Stopwatch

Groovy Stopwatch

Before I started using Groovy, I had created a simple little stopwatch Swing application that basically had one button (Start/Stop) and displayed a time. If you are interested, that is here. I wanted to improve it a bit so I could put a countdown so it would give me a few seconds before it started to time. As a little background, I needed that "feature" so when I was timing this UI I was working on it would give me some time to click "start" on my stopwatch and then switch to the UI I was testing. Not the most advanced tool, but it works fine for my needs.

Instead of updating my Java class, which was already fairly complicated due to the nature of Swing programming, I decided to use Groovy's SwingBuilder.

Here is the final result

Download the Groovy code here.

It was interesting to find that my original Java class for this simple app was 80 lines and my enhanced application in Groovy was only 61, even though I added new features. I probably could have made each of them a little shorter if I really cared about lines of code, but for comparison sake I thought it was interesting how much shorter Groovy was.

For the application itself, here is the code that sets up and displays the Swing UI:

import groovy.swing.SwingBuilder;
import java.awt.BorderLayout as BL
import javax.swing.JFrame

startTime = 0
started = false

swing = new SwingBuilder()
myFrame = swing.frame(title:'Stopwatch', show: true, size:[200,130], defaultCloseOperation: JFrame.EXIT_ON_CLOSE){
 panel (layout: new BL()){
  panel(constraints: BL.NORTH){
   label 'Countdown time'
   countdownField = textField (text:'5', columns:4)
  }
  panel(constraints: BL.CENTER){
   startStopButton = button (text: 'Start/Stop', actionPerformed: {
    if(!started){
     countdownThenStart()
    } else {
     stopTimer()
    }
   })
  }
  panel(constraints: BL.SOUTH){
   messages = label (text:'Click Start')
  }
 }
}

The countdownThenStart() and stopTimer() methods are explained below. One interesting thing I found out was that if I wanted to reference a button (like "startStopButton"), label (like "messages"), or text field (like "countdownField") again, all I had to do was assign it to a variable. If I didn't need it, then I didn't assign it.

I could have made this even simplier if I didn't use the BorderLayout (remove the "constraints: BL.NORTH") or explicitly set the size. I could have just used "pack: true" in place of size. However, since I was learning how to do this, I added them in.

Also, be sure to put the "defaultCloseOperation: JFrame.EXIT_ON_CLOSE" in the frame. I forgot and ended up with dozens of instances of Java running.

To do the countdown, here is the method I used:

def countdownThenStart(){
 int secondsInt = Integer.parseInt(countdownField.text)
 enableFields(false)
 
 def th = Thread.start{
  for(int i = secondsInt; i > 0; i--){   
   messages.text = i
   sleep(1000);
  }
  messages.text = "Go..."
  startTimer()
 }
}

This was a little tricky. I had a problem displaying the countdown. It would just display "Go..." and no digits. It turns out I had to wrap those messages in a separate thread and then it worked like a charm.

Finally, the rest of the helper methods look like this:

def startTimer() {
 started = true
 startTime = new Date().getTime()
 enableFields(true)
}

def stopTimer() {
 stopTime = new Date().getTime()
 started = false
 messages.text = ((stopTime - startTime) / ((double)1000)) + " seconds"  
}

def enableFields(def enable){
 countdownField.enabled = enable
 startStopButton.enabled = enable
}

Nothing surprising or confusing here I hope.

Overall, the SwingBuilder was very easy to use. I've written a number of little Swing apps in the past, and I doubt I will ever need to use anything other than Groovy's SwingBuilder for them again.

Read more...

Word Frequency for YouTube Videos

YouTube has a feature where you can browse the top viewed videos over a specific time-frame (today, this week, this month, or all time). I thought it would be interesting to see which words (if any) pop up more than others. By just glancing at the list I guessed that "justin" and "beiber" would top the list. I thought I'd write some quick Groovy code to see if I was right.

The Stats:

Here is what I found when I looked at the top 160 most viewed videos of all time (as of today):

Top 25 Words:

Word	Count	Freq
official	19	3%
music	12	1%
song	7	1%
cyrus	7	1%
miley	7	1%
version	6	0%
gaga	6	0%
lady	6	0%
bieber	6	0%
justin	6	0%
jason	5	0%
feat	5	0%
dance	5	0%
love	5	0%
baby	5	0%
high	4	0%
david	4	0%
best	4	0%
this	4	0%
sean	3	0%
nuki	3	0%
iglesias	3	0%
enrique	3	0%
goes	3	0%
like	3	0%

Other Stats:
Total words: 619
Total unique words: 424

The Code:

All the source code is located here (box.net)

Here are the guts of the program:

def html = new XmlSlurper(new SAXParser()).parse(urlString)
html.'**'.findAll{ it.@class == 'video-title'}.each {nextVideo ->
 //split the title using regex on non-word characters
 nextVideo.text().split(/\W/).each{nextWord ->
  def lowerCase = nextWord.toLowerCase()
  //limit the results to "interesting" words
  if(lowerCase.length() >= minWordLength && !(lowerCase in ignoreList)){
   wordFreq[lowerCase] = wordFreq[lowerCase] == null ? 1 : wordFreq[lowerCase] + 1
  }
 }
}

Here is what it does:
1. Parse the YouTube URL using XmlSlurper
2. Find all the titles on the page
4. Split the title to get individual words
5. Convert it to lower case to make comparisons easier
7. Limit the words by a minimum length (to get rid of stuff like "of", "and", "the") and ignore other words (like "video")
8. Update the wordFreq map

I am not very comfortable with minimum length and ignoring words, but without that the top 10 words were: video, the, official, ft, music, i, t, you, in, on. That is much less interesting that the filtered list, in my opinion.

Read more...

Google Calendar - When Was That Event Created?

Usually I don't care, but occasionally I need to know when I created an event on my Google Calendar. It is not the easiest piece of information to find, but it is out there and here is how you find it.

1. Go to Settings (Calendar Settings) > Calendars tab
2. Select (click on) the calendar with the event you want
3. Under the Private Address, click on the ICAL icon
4. The address will pop up, just save and open that file
5. In your editor, just search for the name of the event.
6. Look for the CREATED attribute. There is also a LAST-MODIFIED attribute if you are interested in that.

Read more...

Use ConfigSluper Instead Of Properites Files

I often use Java property files as configuration for prototypes, proofs of concepts, utility applications, etc. Groovy has a more powerful way of doing this called a ConfigSlurper (JavaDoc).

A ConfigSlurper just uses a Groovy script as input instead of a .properties file. This lets you do better (in my opinion) configuration like having typed properties (instead of them all being Strings you have to convert) including lists and maps, tree-structures of properties, even deriving a property value based on some calculation or closure.

Here are some examples. All the code can be downloaded here (box.net)

//Config1.groovy
stringProperty="Some string"
numberProperty=42
booleanProperty=false
listProperty=["Monday", "Tuesday", "Wednesday"]

Here is a basic configuration file using some different types. Here is how to read and use it:

def config = new ConfigSlurper().parse(new File('src/Config1.groovy').toURL())

assert "Some string" == config.stringProperty
assert config.stringProperty.class == String

assert 42 == config.numberProperty
assert config.numberProperty.class == Integer

assert false == config.booleanProperty
assert config.booleanProperty.class == Boolean

assert ["Monday", "Tuesday", "Wednesday"] == config.listProperty
assert 3 == config.listProperty.size()
assert config.listProperty.class == ArrayList

Another powerful feature is being able to use trees of data like this:

//Config2.groovy
teams {
 packers {
  quarterback="Aaron Rodgers"
  recievers=["Greg Jennings", "Donald Driver"]
 }
 vikings { 
  quarterback="Brett Favre" 
 }
}

And then reading them like this:

def config = new ConfigSlurper().parse(new File('src/Config2.groovy').toURL())

assert "Aaron Rodgers" == config.teams.packers.quarterback
assert ["Greg Jennings", "Donald Driver"] == config.teams.packers.recievers
assert "Brett Favre" == config.teams.vikings.quarterback

Along those lines, there is a special configuration called "environment." This allows you to use different configurations based on what "environment" you are in.

//Config3.groovy
website {
 //default values
 url = "http://default.mycompany.com"
 port = 80
 user = "test"
}

environments {
 development {
  website {
   url = "http://dev.mycompany.com"
   port = 8080
  }
 }
 production {
  website {
   url = "http://www.mycompany.com"
   user = "prodUser"
  }
 }
}

In this example, there are some default values for the website properties. Then, the different environments overwrite some of the defaults. Here is how you call the ConfigSlurper to use the different environments.

//defaults
def config = new ConfigSlurper().parse(new File('src/Config3.groovy').toURL())

assert config.website.url=="http://default.mycompany.com"
assert config.website.port==80
assert config.website.user=="test"

//development environment
config = new ConfigSlurper("development").parse(new File('src/Config3.groovy').toURL())

assert config.website.url=="http://dev.mycompany.com"
assert config.website.port==8080
assert config.website.user=="test"

//production environment
config = new ConfigSlurper("production").parse(new File('src/Config3.groovy').toURL())

assert config.website.url=="http://www.mycompany.com"
assert config.website.port==80
assert config.website.user=="prodUser"

Finally (for this article), here are a few fun things you can do with a ConfigSlurper including calculated values and merging configs.

//Config4.groovy

//set the value as some calculation
calculation = 2+2

//base the value off of some other property
calc2 = calculation * 2

//set the value using a closure
doubling = 1
5.times{ doubling = doubling * 2 }

And using those values:

def config = new ConfigSlurper().parse(new File('src/Config4.groovy').toURL())

assert 4 == config.calculation
assert 8 == config.calc2

assert 32 == config.doubling

//merge config files
def config1 = new ConfigSlurper().parse(new File('src/Config1.groovy').toURL())
def config2 = new ConfigSlurper().parse(new File('src/Config2.groovy').toURL())
config1 = config1.merge(config2)
assert 42 == config1.numberProperty
assert "Aaron Rodgers" == config1.teams.packers.quarterback

Leave a comment if you have any questions or suggestions!

Read more...

Running an Ant Script in Groovy

I recently wanted to test the execution of an Ant script and I wanted to use Groovy. There are a lot of blogs about using AntBuilder to run Ant tasks in Groovy, but that isn't what I needed. I actually needed to test the Ant script itself.

This was not to hard, but the concept is tricky. I used AntBuilder to execute an external process (using the exec task). In this case, the external process is ant. Lost yet? Here is the code, maybe that will make it easier:

File antExecutable = new File("C:/Ant/bin/ant.bat")
assert antExecutable.exists()

File antScript = new File("C:/antscripts/build.xml")
assert antScript.exists()

def ant = new AntBuilder()
ant.exec(executable: antExecutable.getAbsolutePath(),
 outputproperty:"cmdOutput",
 errorproperty:"cmdError"){
  arg(value: "-f")
  arg(path: antScript.getAbsolutePath())
}
assert ant.project.properties.cmdOutput.contains("BUILD SUCCESSFUL")
assert ant.project.properties.cmdError == ""

Hopefully this is pretty straight-forward. Basically this is equivalent to calling "ant -f C:\antscripts\build.xml" from a command line. If you want to know more about how to use AntBuilder, go here.

The output gets stored in a property called "cmdOutput" which can be tested using the "ant.project.properties.cmdOutput" variable. In a similiar way, the standard error gets stored in "cmdError." If you just want to display the output, remove the outputproperty and errorproperty from the exec task.

There are a couple other things you might need to do.

First, if you want to pass additional arguments to the script (for example, setting some ant properties), you can just add additional "arg" lines like this:

ant.exec(executable: antExecutable.getAbsolutePath(),
 outputproperty:"cmdOutput",
 errorproperty:"cmdError"){
  arg(value: "-f")
  arg(path: antScript.getAbsolutePath())
  arg(value: "-DsomeProperty=someValue)  
}

Second, if the ant script needs to know about some classpath variables, just add an "env" line like this:

ant.exec(executable: antExecutable.getAbsolutePath(),
 outputproperty:"cmdOutput",
 errorproperty:"cmdError"){
  arg(value: "-f")
  arg(path: antScript.getAbsolutePath())
  env(key: "CLASSPATH", path: "C:/jars/;C:/project/files")  
}

Leave a comment if you have any questions or suggestions

Read more...

Scrape Powerball Number Frequency

I know that buying lottery tickets is a total waste of money. I also know that there is nothing you can do to increase the odds of hitting a Powerball jackpot (1 in 195,249,054). However, just for fun, I thought I'd fire off a quick groovy script that will read the frequencies from the Powerball website.

Once I have all the numbers I could sort the lists to find out which numbers are most frequently picked (or least frequently picked). I'm sure there is other statistical analysis that you could do too if you wanted. You could also watch the frequency trends over time (though this historic list of numbers may be better at that)

Here's the simple script:

import org.cyberneko.html.parsers.SAXParser;

//initialize
def maxPowerBall = 39
def whiteBallFreq = [:]
def pbFreq = [:]

//read the numbers
def url = 'http://powerball.com/powerball/pb_frequency.asp'
def html = new XmlSlurper(new SAXParser()).parse(url)

//create the lists from the HTML
html.BODY.TABLE.TBODY.TR[3].TD[1].TABLE.TBODY.TR[4].TD[1].TABLE.TBODY.TR[2..-2].each{nextRow ->
 def cols = nextRow.children()
 def ball = Integer.parseInt(cols[0].text())
 
 whiteBallFreq[ball] = parsePossiblyBlankNumber(cols[1].text())
 if(ball <= maxPowerBall){
  pbFreq[ball] = parsePossiblyBlankNumber(cols[2].text())
 }
}

def int parsePossiblyBlankNumber(String value) {
 if(value.trim().length() == 0){
  return 0;
 } else {
  return Integer.parseInt(value)
 }
}

The import is found here. The long "html.BODY.TABLE..." line is needed because of how the Powerball website is set up.

I put in the parsePossiblyBlankNumber method since the website uses blanks instead of 0s when there are no frequencies.

Leave a comment if you have any questions or suggestions!

Read more...

Code Formatting in Blogger Using SyntaxHighlighter

I wanted to use SyntaxHighlighter, but it turns out it takes a little tweaking on Blogger. I found a number of blogs that had instructions, but none of them seemed to work. Here is what I did to get the code formatting.

1. Upload files to Google Sites (Optional)
You need to link to a few javascript and css files. It looks like SyntaxHighlighter has a hosted version, but I decided to host the specific files I wanted. Here are the files you need:

1. shCore.js
2. shCore.css
3. shCoreDefault.css (or your theme, I used shCoreEclipse.css)
4. Brushes (for type of code). I used shBrushPlain.css, shBrushJava.css, and shBrushGroovy.css

2. Edit your Blogger template
Go to Design > Edit HTML. Add this code towards the bottom:

The "trick" for blogger is to set the "bloggerMode" to true.

3. Wrap your code in "pre"
For example, if I wanted to use blog about this code in Java, I would use class="brush: java" like this:

public static void main(String[] args){
 System.out.println("Hello World!");
}

And it would look like this:

public static void main(String[] args){
 System.out.println("Hello World!");
}

Read more...

Fantasy Football Cheat Sheet Scraper

With my fantasy football draft coming up, I thought I would create a quick Groovy script to scrape a couple Fantasy Football cheat sheets. If you don't know, a cheat sheet has a ranking of players that you can use to make your draft picks. There are a bunch available online, and they are updated frequently (like now that Brett Favre is back with the Vikings I assume he will move up and Tarvaris Jackson will move down in rank).

Since I wanted the most up-to-date ones on the day of my draft, I wrote a couple classes in Groovy to read the webpages and print out the results in a common format. This turned out the be pretty easy to do.

For example, here is one from http://www.fftoolbox.com:

import org.cyberneko.html.parsers.SAXParser;

class FFToolbox {
    public List getPlayerList(){
        def playerList = []
        
        //read the XML
        ['http://www.fftoolbox.com/football/2010/overall.cfm?page=1',
                'http://www.fftoolbox.com/football/2010/overall.cfm?page=2',
                'http://www.fftoolbox.com/football/2010/overall.cfm?page=3',
                'http://www.fftoolbox.com/football/2010/overall.cfm?page=4'].each{url ->
                    def html = new XmlSlurper(new SAXParser()).parse(url)
                    def table = html.BODY.'**'.findAll{ it.name() == 'TABLE'}[0]
                    def rows = table.TBODY.children()[1..-2]
                    
                    //convert to my BO
                    rows.each{ nextRow ->
                        def columns = nextRow.children()
                        playerList.add(new CheatSheetEntry(
                                rank: columns[0],
                                name: columns[1],
                                position: columns[2],
                                team: columns[3],
                                byeWeek: columns[4])
                                )
                    }
                }
        return playerList
    }
}

Note that the import is from here and provides an HTML parser

Here is another example from ESPN.com:

class ESPN {
    public List getPlayerList(){
        def playerList = []
        
        def url = 'http://sports.espn.go.com/fantasy/football/ffl/story?page=NFLDK2K10rankstop200'
        def html = new XmlSlurper(new SAXParser()).parse(url)
        
        def table = html.BODY.'**'.findAll{ it.name() == 'TABLE'}[0]
        def rows = table.TBODY.children()
        
        rows.each{nextRow ->
            def columns = nextRow.children()
            def positionMatcher = columns[3].text() =~ /\D+/
            playerList.add(new CheatSheetEntry(
                    rank: columns[0],
                    name: columns[1].text().substring(0, columns[1].text().indexOf(",")),
                    position: positionMatcher[0],
                    team: columns[1].text().substring(columns[1].text().indexOf(",") + 2),
                    byeWeek: columns[2])
                    )
        }
        
        return playerList
    }
}

Basically they do the same things: Connect to and parse the url(s), find the table with the cheat sheet, and then go through the rows and columns assigning the correct values to a GroovyBean called CheatSheetEntry.

Now I just need to combine the lists somehow to get an average ranking of the players.

Read more...

My Facebook Privacy Settings

There has been a lot of talk in the news about Facebook and their privacy/security settings. Here is how I have set up my account to make sure only certain people can see certain parts of my Facebook profile.

Step 1 - Create Friend Lists

All of the privacy settings are based on which lists of people can see which parts of your profile, so the first step is to create those lists. The two lists we want to create now are:

• Full Access: used for your friends that can see all of your profile.
• No Access: used for the "friends" that you don't want to see anything on your page

Everyone who falls between these two lists will just get "default" access, and we don't need to create a list for them since they are part of your "all friends" list.

To create a list, click on "Friends" on the right side


Then click on "+ Create a List," give it a name and pick which people you want in the list.

Step 2 - Set Up Privacy

Go to the privacy settings. Then choose "Custom" and then "Customize Settings"

For each item that you want to restrict (I do all of them), select the drop down, and choose "Custom"



Then say "Specific People" and choose the "Full Access" list (or whatever you called it)

You can choose what you want each group to see. If you only want the "Full Access" people to see something, do what I mentioned above.

If you want all of your friends except the "No Access" group, do this:

Note: if you say "Everyone" that is everyone in the world, not just your friends.

Repeat this for all the items under "Things I share," "Things others share," and "Contact information."

Step 3 - Protect your pictures

Privacy for your photos is set up per album. Go to this link to change the privacy settings for each album.

Step 4 - Preview your changes

One useful tool Facebook provides is allowing you to see your profile as your friends see it. Go back to the privacy setting in step 2 and click the button at the top labeled "Preview My Profile." Click that and you will be able to type in a friend's name and see what they will see of your profile. Try it with people in your new lists.


If you see something that doesn't look right, go back and update your privacy settings.

Summary

This should be enough to get you started. If you want to be more specific, just create more than two friend lists. For example, I have a "Work People" list that can see my employers and education, but most of those people aren't in the "Full Access" list so they can't see all my pictures.

If you have any questions, let me know.

Read more...

Route Finding Code

I uploaded the full source-code for the Route Finding Problem and the Touring Problem.

Source Code (box.net)

Read more...

Extending to Traveling Salesman Problem

My next step in my A.I. investigation was to extend the route-finding problem to do a touring problem. This is basically a simplified traveling salesman problem where you pick a starting node and have to visit each node one time.

This turned out to be pretty easy with the code I already had. I first created a new interface called Goal with just one method:

public interface GoalInterface {
  public boolean goalMet(State currentState);
}

For the existing route finding problem, I moved the goalTest method to an implementation of this interface:

@Override
public boolean goalMet(State currentState) {
  return currentState.getCurrentNode().getNodeName()
          .equalsIgnoreCase(goalNode.getNodeName());
}

Note that the constructor for this goal takes in the goalNode

Then I just updated the RouteFindingProblem to take a Goal (described below) instead of an goalNode.

The new signature for solve:

public Path solve(final Node initialNode, final GoalInterface goal) { }

And instead of calling the goalTest method, I just call goal.goalMet(). At this point the initial route-finiding problem produces the same results and all the tests still pass.

For the touring problem, I just had to create a new goal. The goalMet() method just checks if every node has been visited by calling this method:

private boolean isEveryNodeVisited(final State currentState) {
  boolean tourComplete = true;
  final List<Action> currentPathActions = currentState.getCurrentPath()
          .getActions();
  final Set<Node> currentlyVisitedNodes = new HashSet<Node>();
  for (Action nextPathAction : currentPathActions) {
      currentlyVisitedNodes.add(nextPathAction.resultOfAction(allNodes));
  }

  // make sure all nodes were visited
  for (Node nextNode : allNodes) {
      if (!currentlyVisitedNodes.contains(nextNode)
              && !nextNode.getNodeName().equalsIgnoreCase(
                      initialNode.getNodeName())) {
          tourComplete = false;
          break;
      }
  }
  return tourComplete;
}

A couple things about this. First, it is not very efficient, but for my testing that is not a big deal. Next, I had to add an extra check for the initialNode since the path that is stored in currentState has a list of actions after the initialNode, but does not include the initialNode.

The last thing I had to do was simplify the map. Since my map of Romania had a few branches that had only one route, there was no way to visit each city only one time. I just "trimmed" the branches and ended up with these segments:

segments = [
      new Segment(start:"Arad", end:"Zerind", cost:75),
      new Segment(start:"Arad", end:"Sibiu", cost:140),
      new Segment(start:"Arad", end:"Timisoara", cost:118),
      new Segment(start:"Bucharest", end:"Fagaras", cost:211),
      new Segment(start:"Bucharest", end:"Pitesti", cost:101),
      new Segment(start:"Craiova", end:"Drobeta", cost:120),
      new Segment(start:"Craiova", end:"Pitesti", cost:138),
      new Segment(start:"Craiova", end:"Rimnieu Vilcea", cost:146),
      new Segment(start:"Drobeta", end:"Mehadia", cost:75),
      new Segment(start:"Fagaras", end:"Sibiu", cost:99),
      new Segment(start:"Lugoj", end:"Mehadia", cost:70),
      new Segment(start:"Lugoj", end:"Timisoara", cost:111),
      new Segment(start:"Oradea", end:"Sibiu", cost:151),
      new Segment(start:"Oradea", end:"Zerind", cost:71),
      new Segment(start:"Pitesti", end:"Rimnieu Vilcea", cost:97),
      new Segment(start:"Rimnieu Vilcea", end:"Sibiu", cost:80)
  ];

Then I ran these tests in Groovy:

//make sure each node results in a path
nodes.each {assert problem.solve(it, new TouringGoal(it, nodes)) != null}
//check a couple paths
assert 1327 == (problem.solve(findNode(nodes, "Arad"), new TouringGoal(findNode(nodes, "Arad"), nodes))).getPathCost();
assert 1294 == (problem.solve(findNode(nodes, "Sibiu"), new TouringGoal(findNode(nodes, "Sibiu"), nodes))).getPathCost();

And finally I did a test to display the results in Groovy:

Node testNode = findNode(nodes, "Bucharest");
Path resultPath = problem.solve(testNode, new TouringGoal(testNode, nodes));
//display the results
println("Shortest tour from " + testNode.toString());
if(resultPath == null){
  println("No route found");
} else {
  for (Action nextAction : resultPath.getActions()) {
      println(nextAction.toString());
  }
}

With the results:

Shortest tour from In(Bucharest)
Go(Pitesti)(101)
Go(Rimnieu Vilcea)(97)
Go(Craiova)(146)
Go(Drobeta)(120)
Go(Mehadia)(75)
Go(Lugoj)(70)
Go(Timisoara)(111)
Go(Arad)(118)
Go(Zerind)(75)
Go(Oradea)(71)
Go(Sibiu)(151)
Go(Fagaras)(99)

Let me know if you have any questions or suggestions on improvements!

Update 7/27/10: Uploaded the source code.

Read more...

Route Finding Applied

Now that I implemented a simple route-finding agent, I thought I would try to apply it to a real-world situation: the shortest route to my office.

I created a new map that looks like this:
My house is at node "P" and work is node "A." The weights are based on the distance and speed limits and are basically the amount of time in minutes * 10 (just to get some rounded numbers).

To my surprise, the shortest route is not the route I typically take to work. The path ended up being:

P -> O -> N -> M -> L -> K -> J -> I -> D -> C -> B -> A

I will have to try this new route on the way to work on Monday!

This does not take into account things like stoplights, which I'm sure will have an effect on the overall time.

Read more...

Adding Segments

I made a small update to my previous solution to the problem-solving agent. The developer in me hated the duplicate "code" of when I defined the nodes. For example, when I defined that Arad was 75 units from Zerind, I also had to define that Zerind was 75 units from Arad. For this example that was not huge, but it could lead to errors.

Here is what it was:

nodes = [
   createNode("Arad", ["Zerind":75, "Sibiu":140, "Timisoara":118]),
   ...
   createNode("Zerind", ["Oradea":71, "Arad":75])
];

To make it a little less error-prone, I added the idea of a "segment." Now I just have to define each segment one time instead of twice. It looks like this:

segments = [
   new Segment(start:"Arad", end:"Zerind", cost:75),
   new Segment(start:"Arad", end:"Sibiu", cost:140),
   new Segment(start:"Arad", end:"Timisoara", cost:118),
   new Segment(start:"Bucharest", end:"Fagaras", cost:211),
   new Segment(start:"Bucharest", end:"Giurgiu", cost:90),
   new Segment(start:"Bucharest", end:"Pitesti", cost:101),
   new Segment(start:"Bucharest", end:"Urziemi", cost:85),
   new Segment(start:"Craiova", end:"Drobeta", cost:120),
   new Segment(start:"Craiova", end:"Pitesti", cost:138),
   new Segment(start:"Craiova", end:"Rimnieu Vilcea", cost:146),
   new Segment(start:"Drobeta", end:"Mehadia", cost:75),
   new Segment(start:"Eforie", end:"Hirsova", cost:86),
   new Segment(start:"Fagaras", end:"Sibiu", cost:99),
   new Segment(start:"Hirsova", end:"Urziemi", cost:98),
   new Segment(start:"Iasi", end:"Neamt", cost:87),
   new Segment(start:"Iasi", end:"Vaslui", cost:92),
   new Segment(start:"Lugoj", end:"Mehadia", cost:70),
   new Segment(start:"Lugoj", end:"Timisoara", cost:111),
   new Segment(start:"Oradea", end:"Sibiu", cost:151),
   new Segment(start:"Oradea", end:"Zerind", cost:71),
   new Segment(start:"Pitesti", end:"Rimnieu Vilcea", cost:97),
   new Segment(start:"Rimnieu Vilcea", end:"Sibiu", cost:80),
   new Segment(start:"Urziemi", end:"Vaslui", cost:142),
];

Then in the Segment class I created a method to convert a list of Segments into a list of Nodes so I just needed to do this in my groovy script to have the same information I did before:

nodes = Segment.convertSegmentsToNodes(segments);

I also had to move the createActionList and createNode methods into the Segment class, which helped clean up my groovy script.

Read more...

Groovy/Java Problem Solving Agent

Today I'm going to look at implementing a simple problem-solving agent using Java and Groovy. This is based on chapter 3 in my old A.I. textbook, "Solving Problems By Searching." I am going to tackle the route-finding problem which takes a number of cities in Romania (p 68 on Google Books) with paths between them with the goal of having to find the shortest route between any two cities.

Let's get started. First, I created a few simple Java classes to represent a Node (a city), an Action (go from one node to another), a Path (list of Actions that have gotten me where I am now), and a State (what Node am I at and how did I get here). These classes are not that interesting, but here are the basics of each one without the implementations:

Node:

public class Node {
  public Node(String nodeName, List availableActions) {  }
  public String getNodeName() {  }
  public List getAvailableActions() {  }
}

Action:

public class Action {
  public Action(String actionName, int stepCost) { }
  public Node resultOfAction(List availableNodes) {
      //if I execute this action, where am I?
  }
  public int getStepCost() { }
}

Path:

public class Path {
  public void addAction(Action action) {  }
  public int getPathCost() {  }
  public List<action> getActions() {  }
  public Path clone() {  }
}

State:

public class State {
  public State(Node currentNode, Path currentPath, List closedNodes){ }
  public Node getCurrentNode() { }
  public Path getCurrentPath() { }
  public List getClosedNodes() { }
}

I also created a couple simple data structures to represent a Queue and a Stack (called SimpleQueue and SimpleStack). When searching for the solution, I needed to decide if I wanted to do a Depth-first search (using a Stack - LIFO) or a Breadth-first search (Queue - FIFO). I decided to use a depth-first search since I tried to be a little smart about only finding solutions that are shorter than any others I've already found. By doing a depth-first search, I tried to expand the search tree until I found a solution, then went back and tried to find other solutions that were shorter.

Now is where the actual searching happens. I created another Java class called RouteFindingProblem. I'll describe each part of that class starting with the "solve" method:

solve:

public Path solve(final Node initialNode, final Node goalNode) {
  if (initialNode.getNodeName().equalsIgnoreCase(goalNode.getNodeName())) {
      resultPath = new Path(new Action("Stay" + initialNode.getNodeName(), 0));
  } else {
      resultPath = null;
      lowestPathCost = Integer.MAX_VALUE;

      // find the paths
      doSearch(initialNode, goalNode);
  }
  return resultPath;
}

This is the entry point into the solving logic. It will return the shortest path from the initialNode to the goalNode. The first check is just to make sure the initialNode is not the same as the goalNode. If it is I am done and I'll just create a new "stay" action. Next (in the else statement) I initialize some variables and then call doSearch.

doSearch:

private void doSearch(final Node initialNode, final Node goalNode) {
  stateDataStructure = new SimpleStack<State>();

  // create the first state
  stateDataStructure
      .put(new State(initialNode, new Path(), new ArrayList<node>()));

  while (!stateDataStructure.isEmpty()) {
      if (goalTest(stateDataStructure.peek(), goalNode)) {
          handleGoalReached(stateDataStructure.get());
      } else {
          successorFunction(stateDataStructure.get(), goalNode);
      }
  }
}

I basically create the first state and add it to the stack. Then I keep going until the stack is empty. If I've reached the goal, then I just check if this is the shortest path (in handleGoalReached). If I haven't reached the goal, then I find all the successors of this state and add them to the Stack.

The last interesting piece of code in this class is the successorFunction method. I don't love this name, but that is what they call it my book. It would be more appropriately called "addSubStates" or something.

successorFunciton:

private void successorFunction(final State currentState, final Node goalNode) {
  // make a copy of the closed list for each sub state
  final List<Node> cloneClosedList = cloneClosedList(currentState
      .getClosedNodes());
  cloneClosedList.add(currentState.getCurrentNode());

  // for each action after this, add it to the queue
  for (Action nextAction : currentState.getCurrentNode()
      .getAvailableActions()) {
      final Node nextNode = nextAction.resultOfAction(nodes);
      // make sure I haven't already checked this node (circular)
      if (!cloneClosedList.contains(nextNode)) {
          final Path clonePath = currentState.getCurrentPath().clone();
          clonePath.addAction(nextAction);

          // only add the next state if the current path is
          // lower than any previous paths
          if (clonePath.getPathCost() < lowestPathCost) {
              stateDataStructure.put(new State(nextNode, clonePath,
                  cloneClosedList));
          }
      }
  }
}

In a nutshell, this just finds the next set of states and adds them to the stack.

All that is left is to set up the actual data and run some tests. To do this I used Groovy, partly because I thought it would be easier to script some of the setup and tests, and partly because I don't know much about Groovy so this was a chance for me to learn more about it.

First off, I created some helper methods (closures) to use in my Groovy script.

createActionList = {actionMap ->
  List<Action> actions = new ArrayList<Action>();
  actionMap.each {place,cost -> actions.add(new Action("Go(" + place + ")", cost)) };
  return actions;
}

createNode = {nodeName, actionMap ->
  return new Node("In(" + nodeName + ")", createActionList(actionMap));
}

findNode = {nodeList, nodeToFind ->
  for(nextNode in nodeList){
      if(nextNode != null && nextNode.getNodeName().equalsIgnoreCase("In(" + nodeToFind + ")")){
          return nextNode;
      }
  }
}

Then I set up all the nodes in this problem (cities in Romania):

nodes = [
  createNode("Arad", ["Zerind":75, "Sibiu":140, "Timisoara":118]),
  createNode("Bucharest", ["Pitesti":101, "Fagaras":211, "Giurgiu":90, "Urziemi":85]),
  createNode("Craiova", ["Drobeta":120, "Rimnieu Vilcea":146, "Pitesti":138]),
  createNode("Drobeta", ["Mehadia":75, "Craiova":120]),
  createNode("Eforie", ["Hirsova":86]),
  createNode("Fagaras", ["Sibiu":99, "Bucharest":211]),
  createNode("Giurgiu", ["Bucharest":90]),
  createNode("Hirsova", ["Urziemi":98, "Eforie":86]),
  createNode("Iasi", ["Vaslui":92, "Neamt":87]),
  createNode("Lugoj", ["Timisoara":111, "Mehadia":70]),
  createNode("Mehadia", ["Lugoj":70, "Drobeta":75]),
  createNode("Neamt", ["Iasi":87]),
  createNode("Oradea", ["Zerind":71, "Sibiu":151]),
  createNode("Pitesti", ["Rimnieu Vilcea":97, "Craiova":138, "Bucharest":101]),
  createNode("Rimnieu Vilcea", ["Sibiu":80, "Craiova":146, "Pitesti":97]),
  createNode("Sibiu", ["Oradea":151, "Arad": 140, "Fagaras":999, "Rimnieu Vilcea":80]),
  createNode("Timisoara", ["Arad":118, "Lugoj":70]),
  createNode("Urziemi", ["Bucharest":85, "Vaslui":142, "Hirsova":98]),
  createNode("Vaslui", ["Urziemi":142, "Iasi":92]),
  createNode("Zerind", ["Oradea":71, "Arad":75])
];

Update:See this post about defining Segments instead of Nodes.

Then I set up some Groovy unit tests to make sure this was working as expected:

RouteFindingProblem problem = new RouteFindingProblem(nodes);

//same initial/goal
assert 0 == (problem.solve(findNode(nodes, "Arad"), findNode(nodes, "Arad"))).getPathCost();
//neighbors
assert 75 == (problem.solve(findNode(nodes, "Arad"), findNode(nodes, "Zerind"))).getPathCost();
assert 75 == (problem.solve(findNode(nodes, "Zerind"), findNode(nodes, "Arad"))).getPathCost();
//2 hops
assert 215 == (problem.solve(findNode(nodes, "Zerind"), findNode(nodes, "Sibiu"))).getPathCost();
//one end to the other
assert 698 == (problem.solve(findNode(nodes, "Oradea"), findNode(nodes, "Eforie"))).getPathCost();

Finally I did a test to print out the path from one end of Romania to the other:

Path resultPath = problem.solve(findNode(nodes, "Oradea"), findNode(nodes, "Eforie"));
//display the results
println("Shortest path from " + findNode(nodes, "Oradea").toString() + " to " + findNode(nodes, "Eforie").toString());
for (Action nextAction : resultPath.getActions()) {
  println(nextAction.toString());
}

The output is:

Shortest path from In(Oradea) to In(Eforie)
Go(Sibiu)(151)
Go(Rimnieu Vilcea)(80)
Go(Pitesti)(97)
Go(Bucharest)(101)
Go(Urziemi)(85)
Go(Hirsova)(98)
Go(Eforie)(86)

Next Steps:
This is just one simple problem-solving agent. I tried to make this fairly generic, but to implement the other examples from the book (sliding block puzzle, 8-queens problem, touring problem), it will take a little work.


Update 7/27/10: Uploaded the source code.

Read more...

A.I. Reference Book

While doing my graduate work, I took a class on Artificial Intelligence. It was very interesting though I haven't had much time until now to look into it more. I am looking back though the textbook: Artificial Intelligence: A Modern Approach (2nd Edition).



There is a limited version of the book at Google Books here.

Read more...

Geek vs. Nerd vs. Dork

I am a geek. Not to be confused with a "nerd," "dork," or "dweeb." If you are confused, check out the Venn diagram at this site.

Read more...