Version 0 of Finding distances by querying MapQuest

Updated 2002-08-23 04:15:25

Michael A. Cleverly -- Occasionally I lurk on rec.puzzles [L1 ]. 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." [L2 ]

Since http://www.MapQuest.com is Tcl driven (it's running AOLserver!) I thought it'd be fun to build An HTTP Robot in Pure 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.

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} {
     set letter [format %c [expr [scan $from %c] -1]]
     set SQL "
         select city
           from zt_cities
          where city like '$letter%' and
                state = '$state'"

     db_foreach city $SQL {
         set distance [mapquest $from $state $city $state]
         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 'bots 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 'bot and letting it run someone else with an Atlas was able to identify a route in Ohio that only took 218.19 miles. Sigh. :^)