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 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:
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:
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 ...]