Place Name Puzzle Solver, aka 'City Match'

Dr. Phillip M. Feldman

# 1. Introduction

Most of us, at one time or another, have played a game or worked on a puzzle that involved finding the name of a city or country that satisfies certain conditions. This online solver solves a wide range of such problems.

Here are a few examples of problems that this solver can answer:

• Find all cities whose names begin with the letter a and are exactly five letters long.

• Find all cities whose names end with the letter c.

• Find all cities such that the name of the city and the name of the country, U.S. state, or Canadian province both begin with the letter a.

• Find all cities in the United States or Canada that begin with the letter t.

The city database that I'm using currently contains 720 cities. This number is expected to slowly grow over time. The current rules for deciding whether a given city is included are as follows:

1. Any city in North America, Europe, Australia, New Zealand, or Israel having a greater-metropolitan-area population of 300,000 or more is included.

2. In other areas of the world, any city having a greater-metropolitan-area population of 1,000,000 or more is included.

3. Certain cities that do not meet the above criteria, but that have some special historical, cultural, or political significance are also included. These are decided on a case-by-case basis.

For cities in the United States and Canada, the database contains the name of the city, the name of the U.S. state or Canadian province, and the name of the country. For cities in all other countries, the database stores only the names of the city and the country. The United States is always abbreviated as "U.S."; names of other countries and of U.S. states, Canadian provinces, and cities are never abbreviated.

The city database was constructed by hand. Errors are fixed as these come to my attention; undoubtedly that are many that have not yet been discovered. All specific error reports are welcome and will be promptly addressed.

# 2. Using City Match with Hangman-Style Templates

Inputs to the City Match program consist of two template fields and two checkboxes. When the Use Python Regular Expressions checkbox is unchecked, which is the default, the contents of the template fields are treated as hangman-style templates. This mode of operation is recommended for most users.

The first template specifies any restrictions on the name of the city. The second specifies any restrictions on the name of the county, U.S. state, or Canadian province.

Each template is a hangman-style string containing letters, spaces, and any of the following special characters:

• underscore (`_`): As in hangman, the underscore represents an unknown character (letter or a space).

• plus sign (`+`): This represents one or more unknown characters.

• asterisk (`*`): This represents zero or more unknown characters, i.e., the asterisk will match anything or nothing.

• question mark (`?`): This represents zero or one unknown characters, i.e., either a single letter may be substituted for the question mark, or the question mark may be deleted, closing up the space.

• vertical bar (`|`): This symbol separates alternative patterns. A match to any of the alternatives is considered a match to the entire template.

Here are a few examples:

• To find all cities whose names begin with the letter a and are exactly five letters long, specify `a____` for the city template and leave the country template blank.

• To find all cities whose names end with the letter c, specify `*c` for the city template, leave the country template blank, and make sure that the first check box is checked.

• To find all cities such that the name of the city and the name of the country, U.S. state, or Canadian province both begin with the letter a, specify `a*` for both the city template and country template.

• One could find all cities in the United States or Canada that begin with the letter t by performing two separate searches, but this would be inconvenient. One can obtain the same information with the following single search: Specify `t*` for the city template, and `u.s.|canada` for the country template.

Some city names contain the word city; examples are Guatemala City and Mexico City. Depending on the rules of the game or puzzle, one may wish to ignore the word city for purposes of determining whether a given city name matches the specified template. If, for example, if one wishes to find city names that end with the letter y, one probably does not want Guatemala City and Mexico City to be returned as matches. A check box (see below) allows one to control whether the presence of the word city in the name of a city is counted as significant.

Note:

• If a template field is empty, this is equivalent to putting an asterisk in that field, i.e., that template will match everything. (See exception below).

• If both template fields are empty, the program will generate an error.

• One may put an asterisk (or something equivalent, e.g., some combination of underscores and asterisks) in each of the two template fields. In this case, the program will return the entire database! (This is typically not what is desired).

• Currently, there is no mechanism for restricting a search to a geographic region that includes multiple countries, other than via the vertical bar operator discussed above.

# 3. Using City Match with Python Regular Expressions

Python regular expressions, otherwise known as regexes, are much more powerful than the hangman-style templates described in the previous section, but are also more difficult to use. A full exposition on regexes is beyond the scope of this document, but many excellent references are available. I recommend starting with the link that appears at the beginning of this paragraph. Here are a couple of examples that illustrate the kinds of things that one can do with regular expressions:
• To find cities whose names contain only the letters a-h, specify `[a-h]*\$` for the city regex, leave the country regex blank, and check the "Use Python regular expressions" checkbox. The expression `[a-h]` in the regex is an example of what is known as a character class; this defines a set of characters. (There is only one city in the database that matches this template).

• Suppose that we wish to find cities whose names begin and end with the same letter, where this letter is not a. This can be done using a character class together with something known as a back reference. Specify `([b-z]).*\1\$` for the city regex, leave the country regex blank, and check the "Use Python regular expressions" checkbox.

# 4. Run City Match Solver Online

To run city_match.py online:

1. In each box, either enter a template or clear (remove) the template.

• If a box is left empty, no filtering of results is done based on the corresponding database field. (If, for example, one enters 'Russia' into the second field and leaves the first field empty, the program will return a list containing all Russian cities in the database).

• Upper- and lower-case can be used interchangeably.

• One can move from the first box to the second by pressing the tab key.

2. Make sure that the checkbox settings are as desired.

3. Click on the green button.

City:        Country, U.S. State, or Canadian Province:

Ignore the word 'City' in city name     Use Python regular expressions

Last update: 19 July, 2015