Problem statement
Take a US state capital. Drop a letter. Re-arrange the remaining letters to get the name of a US city. There are two answers.
I know Wlll Shortz says he makes up problems that are not programmable, but he goofed up this time, big time. This one is eminently programmable. I am not even a programmer, more a scripter. I don’t want to have an unfair advantage so I’m sharing my Perl scripts that solve this problem.
The setup
Find a Linux machine. A Raspberry Pi makes a great economical choice if you don’t have anything like that.
Scrape the 50 state capitals from a web page after arriving at a page (I used Wikipedia) that lists them. By scrape I mean copy-and-paste into a file in a terminal window of your Linux server.
Same for US cities. I went to a more obscure listing and picked up the 666 of the largest cities from a listing of the top 1000.
Cleaning up the Capitals
Here’s a script for processing those capital cities. The input file contains lines like these first two:
Alabama AL 1819 Montgomery 1846 155.4 2 205,764 374,536 Birmingham is the s
tate's largest city
Alaska AK 1959 Juneau 1906 2716.7 3 31,275 Juneau is the largest capital by land area. Anchora
ge is the state's largest city.
... |
Alabama AL 1819 Montgomery 1846 155.4 2 205,764 374,536 Birmingham is the s
tate's largest city
Alaska AK 1959 Juneau 1906 2716.7 3 31,275 Juneau is the largest capital by land area. Anchora
ge is the state's largest city.
...
I called it cap-fltr.pl
#!/usr/bin/perl
while(<STDIN>) {
($cap) = /\d{4}\s+(\D+)\s+\d{4}/;
$cap = lc $cap;
$cap =~ s/\s//g;
print "$cap\n";
} |
#!/usr/bin/perl
while(<STDIN>) {
($cap) = /\d{4}\s+(\D+)\s+\d{4}/;
$cap = lc $cap;
$cap =~ s/\s//g;
print "$cap\n";
}
Create a clean listing of capitals like this:
$ ./cap-fltr.pl < capitals.orig > capitals
assuming, that is, that you dumped your paste buffer of scraped capitals and related information into a file called capitals.orig. So that creates a file called capitals looking like this:
montgomery
juneau
phoenix
littlerock
sacramento
denver
... |
montgomery
juneau
phoenix
littlerock
sacramento
denver
...
Cleaning our cities
My scraped cities file morecities.orig looks like this:
1 New York - city New York 8,491,079 5.9%
2 Los Angeles - city California 3,928,864 6.0%
3 Chicago - city Illinois 2,722,389 -5.9%
4 Houston - city Texas 2,239,558 13.2%
5 Philadelphia - city Pennsylvania 1,560,297 3.0%
6 Phoenix - city Arizona 1,537,058 15.8%
... |
1 New York - city New York 8,491,079 5.9%
2 Los Angeles - city California 3,928,864 6.0%
3 Chicago - city Illinois 2,722,389 -5.9%
4 Houston - city Texas 2,239,558 13.2%
5 Philadelphia - city Pennsylvania 1,560,297 3.0%
6 Phoenix - city Arizona 1,537,058 15.8%
...
These can be cleaned up with this script, which I call morecities-fltr.pl:
#!/usr/bin/perl
while(<STDIN>) {
($city) = /^\d+\s+([^-]+)\s-/;
$city = lc $city;
$city =~ s/\s//g;
if ($city =~ /st\./) {
$form1 = $city;
$form1 =~ s/\.//g;
print "$form1\n";
}
$city =~ s/st\./saint/;
print "$city\n";
} |
#!/usr/bin/perl
while(<STDIN>) {
($city) = /^\d+\s+([^-]+)\s-/;
$city = lc $city;
$city =~ s/\s//g;
if ($city =~ /st\./) {
$form1 = $city;
$form1 =~ s/\.//g;
print "$form1\n";
}
$city =~ s/st\./saint/;
print "$city\n";
}
Note in this and the capitals filter I get rid of space, lowercase everything and here I consider st and saint as alternate forms, just in case. Those puzzle-masters can be tricky!
So the cleanup goes into a cities file with a command like this:
$ ./morecities-fltr.pl < morecities.orig > cities
Finally the program that solves the puzzle…
The solution script, which I called sol2.pl, isn’t too bad if you know a tiny bit of Perl. It is this:
#!/usr/bin/perl
$DEBUG = 0;
open(CAPITALS,"capitals");
open(CITIES,"cities");
@cities = <CITIES>;
@capitals = <CAPITALS>;
foreach $capital (@capitals) {
chomp($capital);
print "capital: $capital\n" if $DEBUG;
$lenCap = length $capital;
foreach $city (@cities) {
chomp($city);
print "city: $city\n" if $DEBUG;
$lenCity = length $city;
next unless $lenCap == $lenCity + 1;
# put the individual letters of the city into an array
@citychars = split //, $city;
$capitalcopy = $capital;
# the following would be a more crude way to do it, leaving us results to be picked over by hand
#$capitalcopy =~ s/[$city]//g;
# this is the heart of it - eat the characters of the capital away, one-by-one, with the characters of the city
# this provides for an exact, no-thinking solution
foreach $citychar (@citychars) {
$capitalcopy =~ s/$citychar//;
}
print "capitalcopy: $capitalcopy\n" if $DEBUG;
# solution occurs when the copy of the capital is left with excatly one character
print "capital, city: $capital, $city\n" if $capitalcopy =~ /^\w$/;
}
} |
#!/usr/bin/perl
$DEBUG = 0;
open(CAPITALS,"capitals");
open(CITIES,"cities");
@cities = <CITIES>;
@capitals = <CAPITALS>;
foreach $capital (@capitals) {
chomp($capital);
print "capital: $capital\n" if $DEBUG;
$lenCap = length $capital;
foreach $city (@cities) {
chomp($city);
print "city: $city\n" if $DEBUG;
$lenCity = length $city;
next unless $lenCap == $lenCity + 1;
# put the individual letters of the city into an array
@citychars = split //, $city;
$capitalcopy = $capital;
# the following would be a more crude way to do it, leaving us results to be picked over by hand
#$capitalcopy =~ s/[$city]//g;
# this is the heart of it - eat the characters of the capital away, one-by-one, with the characters of the city
# this provides for an exact, no-thinking solution
foreach $citychar (@citychars) {
$capitalcopy =~ s/$citychar//;
}
print "capitalcopy: $capitalcopy\n" if $DEBUG;
# solution occurs when the copy of the capital is left with excatly one character
print "capital, city: $capital, $city\n" if $capitalcopy =~ /^\w$/;
}
}
With the comments it’s pretty self-documenting.
I’ll publish my answer after the deadline. you have to do some work after all!
Python approach
This hasn’t been thoroughly tested yet. A friend has suggested the following python code might work.
current_city = ""
current_capital = ""
missed_letters = 0
for count, capital in enumerate(capitals):
missed_letters = 0
current_capital = capital
print current_capital, "current capital"
for count, city in enumerate(cities):
current_city = city
print current_city, "current city"
for count, letter in enumerate(capital):
while missed_letters <2:
if missed_letters <2 and len(city)== count+1:
print current_capital, "Take one letter from this capital"
print current_city, "Rearrange the letters in the capital to get this city"
elif letter in city:
pass
print "letter in the capital matched the city"
elif letter not in city:
missed_letters+=1
print "letters didn't match any in the word" |
current_city = ""
current_capital = ""
missed_letters = 0
for count, capital in enumerate(capitals):
missed_letters = 0
current_capital = capital
print current_capital, "current capital"
for count, city in enumerate(cities):
current_city = city
print current_city, "current city"
for count, letter in enumerate(capital):
while missed_letters <2:
if missed_letters <2 and len(city)== count+1:
print current_capital, "Take one letter from this capital"
print current_city, "Rearrange the letters in the capital to get this city"
elif letter in city:
pass
print "letter in the capital matched the city"
elif letter not in city:
missed_letters+=1
print "letters didn't match any in the word"
My answer
$ ./sol2.pl
capital, city: trenton, renton
capital, city: salem, mesa
capital, city: salem, ames |
capital, city: trenton, renton
capital, city: salem, mesa
capital, city: salem, ames
Actual answer
salem -> mesa
st paul -> tulsa
This illustrates a good lesson. Program, yes, but don’t turn off your brain. I was aware of possible saint/st spelling pitfalls, but I only applied it to the cities list. For some reason I overlooked applying this ambiguity to the capitals list! If add stpaul to my capitals list the program finds tulsa instantly – I just tried it.
If there’s any satisfaction, very, very few people got the correct answer.
References and related
Audio clip of the puzzle
Another NPR puzzle amenable to simple computer tools, in this case shell commands, is documented here: puzzle
Raspberry Pis. Here we describe building a four-monitor display with Raspberry Pis.
A good python tutorial: https://docs.python.org/2/tutorial/