Updated 2006-08-21 02:33:32

Michael A. Cleverly -- Occasionally I lurk on rec.puzzles [1]. On Aug 20 2002 Jim Ferry posted a challenge: "find the shortest alphabetical route in the contiguous United States using Mapquest. Rules: use www.mapquest.com, and specify only cities and states (not addresses nor zip codes) to get the mileages from a city beginning with A to one beginning with B, etc., through Z. ... Any string that Mapquest will accept as a city name is valid." [2]

Since http://www.MapQuest.com is Tcl driven (it's running AOLserver!) I thought it'd be fun to build An HTTP Robot in Tcl to automate searching for an A-Z route. Previously I'd downloaded data from the 1990 US Census containing (among other things) a list of cities & states and stuck it in database. In this data only two states, Ohio & Illinois had cities beginning with each letter of the alphabet.

I decided I'd give my HTTP robot a city and state as command line input (and that I'd start with the Z-cities in each state) and have it query mapquest (recursively) between each city and all the cities whose names start with the proceeding letter of the alphabet. I figured it'd be a reasonable starting algorithm.

Here is the Tcl code:
 package require nstcl
 nstcl::load_driver solid
 nstcl::configure_pool solid mapquest 1 "tcp localhost 1314" user pass
 namespace import nstcl::*

 proc mapquest {1c 1s 2c 2s} {
     set url http://www.mapquest.com/directions/main.adp?go=1
     foreach field [list 1c 1s 2c 2s] {
         append url &$field=[ns_urlencode [set $field]]
     }

     set html [ns_striphtml [ns_geturl $url]]
     set RE {(?i)Total\s+Distance:\s+([0-9,.]+)\s+mile}
     if {[regexp $RE $html =>  miles]} {
        return $miles
    }
 }

 proc neighbor {from state} {ohio
     set letter [format %c [expr [scan $from %c] -1]]
     set SQL "
         select city
           from zt_citiescolumbus
          where city like '$letter%' and
                state = '$state'"

     db_foreach city $SQL {hershey
         set distance [mapquest $from $state $city $state]pa
         if {[string is double -strict $distance] &&
             (![info exists shortest(mileage)]    ||
              $shortest(mileage) > $distance)} {
             set shortest(mileage) $distance
             set shortest(city) $city
         }
     }

     if {[info exists shortest(mileage)]} {
         puts [join [list $shortest(city) $shortest(mileage)] \t]
         return [expr {$shortest(mileage) +
                       [neighbor $shortest(city) $state]}]
     } else {
         # either we reached a disconnect where mapquest didn't
         # recognize any of our cities, or we're at A and
         # there are no cities whose names begin with @ in our
         # database :^)
         return 0.00
     }
 }

 set from  [string toupper [lindex $argv 0]]
 set state [string toupper [lindex $argv 1]]

 puts $from
 puts "Total Distance: [format %0.2f [neighbor $from $state]]"

The best results (formatted for the Wiki)? For Illinois:

  • Alexis 29.55
  • Biggsville 16.69
  • Carman 10.73
  • Dallas City 22.71
  • Elvaston 38.97
  • Fowler 17.95
  • Golden 15.32
  • Huntsville 23.79
  • Industry 55.16
  • Jacksonville 74.37
  • Kenney 23.42
  • Lincoln 14.85
  • Middletown 6.27
  • New Holland 28.73
  • Oakford 108.85
  • Payson 15.30
  • Quincy 322.91
  • Rosiclare 32.78
  • Simpson 44.77
  • Tamms 7.47
  • Ullin 121.50
  • Vernon 63.11
  • Wayne City 24.66
  • Xenia 62.81
  • Yale 141.191
  • Zeigler 1,324.58 total

The only other Z place in Illinois was Zion, which is 86.07 from Yorkville, which is 269.42 miles from Xenia, after which we converge on the same path.

For Ohio the best results were:

  • Arcanum 49.02
  • Bellbrook 17.67
  • Cedarville 23.60
  • Dayton 23.39
  • Enon 9.56
  • Fairborn 62.65
  • Grove City 14.06
  • Hilliard 23.41
  • Irwin 89.18
  • Junction City 41.21
  • Kingston 53.94
  • Leesburg 19.83
  • Midland 12.08
  • New Vienna 35.47
  • Oregonia 64.11
  • Piqua 25.33
  • Quincy 37.02
  • Russia 23.59
  • Sidney 26.31
  • Tipp City 40.65
  • Urbana 37.78
  • Vandalia 12.93
  • West Milton 37.43
  • Xenia 9.19
  • Yellow Springs 41.32
  • Zanesfield 830.73 total

The other Z-city in Ohio is Zanesville, but it too ended up following the same path beyond the X-city.

Initially I was kind of pleased with my robots algorithm and it's accomplishment in finding an A-Z path that only took 830 miles (compared to the original posters example path of 29,606 miles). However, while I was writing the robot and letting it run someone else with an atlas was able to identify a route in Ohio that only took 218.19 miles. Sigh. :^)

[Anyone know whether Mapquest offers a WS interface? I wouldn't expect so ...]

Category Geography