Skip to content

Instantly share code, notes, and snippets.

@0xhaven

0xhaven/country_paths.py

Created April 3, 2019 22:13
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save 0xhaven/2dbf6811ccf47a20a08a9ad7c1c9f3f6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save 0xhaven/2dbf6811ccf47a20a08a9ad7c1c9f3f6 to your computer and use it in GitHub Desktop.
Download ZIP
Searching the graph of country land borders.
Raw
country_paths.py
from collections import defaultdict
#
# What are the minimum number of land border crossing between any two countries?
# Based on this reddit question: https://redd.it/b8vjzp
#
# From https://www.cia.gov/library/publications/resources/the-world-factbook/fields/281.html
countries = {
"Afghanistan": {"China", "Iran", "Pakistan", "Tajikistan", "Turkmenistan", "Uzbekistan"},
"Akrotiri": {"Cyprus"},
"Albania": {"Greece", "Kosovo", "Macedonia", "Montenegro"},
"Algeria": {"Libya", "Mali", "Mauritania", "Morocco", "Niger", "Tunisia", "Western Sahara"},
"Andorra": {"France", "Spain"},
"Angola": {"Democratic Republic of the Congo", "Republic of the Congo", "Namibia", "Zambia"},
"Argentina": {"Bolivia", "Brazil", "Chile", "Paraguay", "Uruguay"},
"Armenia": {"Azerbaijan", "Georgia", "Iran", "Turkey"},
"Austria": {"Czech Republic", "Germany", "Hungary", "Italy", "Liechtenstein", "Slovakia", "Slovenia", "Switzerland"},
"Azerbaijan": {"Armenia", "Georgia", "Iran", "Russia", "Turkey"},
"Bangladesh": {"Burma", "India"},
"Belarus": {"Latvia", "Lithuania", "Poland", "Russia", "Ukraine"},
"Belgium": {"France", "Germany", "Luxembourg", "Netherlands"},
"Belize": {"Guatemala", "Mexico"},
"Benin": {"Burkina Faso", "Niger", "Nigeria", "Togo"},
"Bhutan": {"China", "India"},
"Bolivia": {"Argentina", "Brazil", "Chile", "Paraguay", "Peru"},
"Bosnia and Herzegovina": {"Croatia", "Montenegro", "Serbia"},
"Botswana": {"Namibia", "South Africa", "Zambia", "Zimbabwe"},
"Brazil": {"Argentina", "Bolivia", "Colombia", "French Guiana", "Guyana", "Paraguay", "Peru", "Suriname", "Uruguay", "Venezuela"},
"Bulgaria": {"Greece", "Macedonia", "Romania", "Serbia", "Turkey"},
"Burkina Faso": {"Benin", "Cote d'Ivoire", "Ghana", "Mali", "Niger", "Togo"},
"Burma": {"Bangladesh", "China", "India", "Laos", "Thailand"},
"Burundi": {"Democratic Republic of the Congo", "Rwanda", "Tanzania"},
"Cambodia": {"Laos", "Thailand", "Vietnam"},
"Cameroon": {"Central African Republic", "Chad", "Republic of the Congo", "Equatorial Guinea", "Gabon", "Nigeria"},
"Canada": {"US"},
"Central African Republic": {"Cameroon", "Chad", "Democratic Republic of the Congo", "Republic of the Congo", "South Sudan", "Sudan"},
"Chad": {"Cameroon", "Central African Republic", "Libya", "Niger", "Nigeria", "Sudan"},
"Chile": {"Argentina", "Bolivia", "Peru"},
"China": {"Afghanistan", "Bhutan", "Burma", "India", "Kazakhstan", "North Korea", "Kyrgyzstan", "Laos", "Mongolia", "Nepal", "Pakistan", "Russia", "Tajikistan", "Vietnam"},
"Colombia": {"Brazil", "Ecuador", "Panama", "Peru", "Venezuela"},
"Congo": {"Democratic Republic of the", "Angola", "Burundi", "Central African Republic", "Republic of the Congo", "Rwanda", "South Sudan", "Tanzania", "Uganda", "Zambia"},
"Congo": {"Republic of the", "Angola", "Cameroon", "Central African Republic", "Democratic Republic of the Congo", "Gabon"},
"Costa Rica": {"Nicaragua", "Panama"},
"Cote d'Ivoire": {"Burkina Faso", "Ghana", "Guinea", "Liberia", "Mali"},
"Croatia": {"Bosnia and Herzegovina", "Hungary", "Montenegro", "Serbia", "Slovenia"},
"Cyprus": {"Akrotiri", "Dhekelia"},
"Czechia": {"Austria", "Germany", "Poland", "Slovakia"},
"Denmark": {"Germany"},
"Dhekelia": {"Cyprus"},
"Djibouti": {"Eritrea", "Ethiopia", "Somalia"},
"Dominican Republic": {"Haiti"},
"Ecuador": {"Colombia", "Peru"},
"Egypt": {"Gaza Strip", "Israel", "Libya", "Sudan"},
"El Salvador": {"Guatemala", "Honduras"},
"Equatorial Guinea": {"Cameroon", "Gabon"},
"Eritrea": {"Djibouti", "Ethiopia", "Sudan"},
"Estonia": {"Latvia", "Russia"},
"Eswatini": {"Mozambique", "South Africa"},
"Ethiopia": {"Djibouti", "Eritrea", "Kenya", "Somalia", "South Sudan", "Sudan"},
"European Union": {"Albania", "Andorra", "Belarus", "Bosnia and Herzegovina", "Holy See", "Liechtenstein", "Macedonia", "Moldova", "Monaco", "Montenegro", "Norway", "Russia", "San Marino", "Serbia", "Switzerland", "Turkey", "Ukraine"},
"Finland": {"Norway", "Sweden", "Russia"},
"France": {"Andorra", "Belgium", "Germany", "Italy", "Luxembourg", "Monaco", "Spain", "Switzerland"},
"Gabon": {"Cameroon", "Republic of the Congo", "Equatorial Guinea"},
"Gambia": {"Senegal"},
"Gaza Strip": {"Egypt", "Israel"},
"Georgia": {"Armenia", "Azerbaijan", "Russia", "Turkey"},
"Germany": {"Austria", "Belgium", "Czech Republic", "Denmark", "France", "Luxembourg", "Netherlands", "Poland", "Switzerland"},
"Ghana": {"Burkina Faso", "Cote d'Ivoire", "Togo"},
"Gibraltar": {"Spain"},
"Greece": {"Albania", "Bulgaria", "Macedonia", "Turkey"},
"Guatemala": {"Belize", "El Salvador", "Honduras", "Mexico"},
"Guinea": {"Cote d'Ivoire", "Guinea-Bissau", "Liberia", "Mali", "Senegal", "Sierra Leone"},
"Guinea-Bissau": {"Guinea", "Senegal"},
"Guyana": {"Brazil", "Suriname", "Venezuela"},
"Haiti": {"Dominican Republic"},
"Holy See (Vatican City)": {"Italy"},
"Honduras": {"Guatemala", "El Salvador", "Nicaragua"},
"Hungary": {"Austria", "Croatia", "Romania", "Serbia", "Slovakia", "Slovenia", "Ukraine"},
"India": {"Bangladesh", "Bhutan", "Burma", "China", "Nepal", "Pakistan"},
"Iran": {"Afghanistan", "Armenia", "Azerbaijan", "Iraq", "Pakistan", "Turkey", "Turkmenistan"},
"Iraq": {"Iran", "Jordan", "Kuwait", "Saudi Arabia", "Syria", "Turkey"},
"Ireland": {"UK"},
"Israel": {"Egypt", "Gaza Strip", "Jordan", "Lebanon", "Syria", "West Bank"},
"Italy": {"Austria", "France", "Holy See (Vatican City)", "San Marino", "Slovenia", "Switzerland"},
"Jordan": {"Iraq", "Israel", "Saudi Arabia", "Syria", "West Bank"},
"Kazakhstan": {"China", "Kyrgyzstan", "Russia", "Turkmenistan", "Uzbekistan"},
"Kenya": {"Ethiopia", "Somalia", "South Sudan", "Tanzania", "Uganda"},
"Korea": {"North", "China", "South Korea", "Russia"},
"Korea": {"South", "North Korea"},
"Kosovo": {"Albania", "Macedonia", "Montenegro", "Serbia"},
"Kuwait": {"Iraq", "Saudi Arabia"},
"Kyrgyzstan": {"China", "Kazakhstan", "Tajikistan", "Uzbekistan"},
"Laos": {"Burma", "Cambodia", "China", "Thailand", "Vietnam"},
"Latvia": {"Belarus", "Estonia", "Lithuania", "Russia"},
"Lebanon": {"Israel", "Syria"},
"Lesotho": {"South Africa"},
"Liberia": {"Guinea", "Cote d'Ivoire", "Sierra Leone"},
"Libya": {"Algeria", "Chad", "Egypt", "Niger", "Sudan", "Tunisia"},
"Liechtenstein": {"Austria", "Switzerland"},
"Lithuania": {"Belarus", "Latvia", "Poland", "Russia"},
"Luxembourg": {"Belgium", "France", "Germany"},
"Macedonia": {"Albania", "Bulgaria", "Greece", "Kosovo", "Serbia"},
"Malawi": {"Mozambique", "Tanzania", "Zambia"},
"Malaysia": {"Thailand"},
"Mali": {"Algeria", "Burkina Faso", "Cote d'Ivoire", "Guinea", "Mauritania", "Niger", "Senegal"},
"Mauritania": {"Algeria", "Mali", "Senegal", "Western Sahara"},
"Mexico": {"Belize", "Guatemala", "US"},
"Micronesia": {"Federated States of "},
"Moldova": {"Romania", "Ukraine"},
"Monaco": {"France"},
"Mongolia": {"China", "Russia"},
"Montenegro": {"Albania", "Bosnia and Herzegovina", "Croatia", "Kosovo", "Serbia"},
"Morocco": {"Algeria", "Western Sahara", "Spain"},
"Mozambique": {"Malawi", "South Africa", "Eswatini", "Tanzania", "Zambia", "Zimbabwe"},
"Namibia": {"Angola", "Botswana", "South Africa", "Zambia"},
"Nepal": {"China", "India"},
"Netherlands": {"Belgium", "Germany"},
"Nicaragua": {"Costa Rica", "Honduras"},
"Niger": {"Algeria", "Benin", "Burkina Faso", "Chad", "Libya", "Mali", "Nigeria"},
"Nigeria": {"Benin", "Cameroon", "Chad", "Niger"},
"Norway": {"Finland", "Sweden", "Russia"},
"Oman": {"Saudi Arabia", "UAE", "Yemen"},
"Pakistan": {"Afghanistan", "China", "India", "Iran"},
"Panama": {"Colombia", "Costa Rica"},
"Paraguay": {"Argentina", "Bolivia", "Brazil"},
"Peru": {"Bolivia", "Brazil", "Chile", "Colombia", "Ecuador"},
"Poland": {"Belarus", "Czech Republic", "Germany", "Lithuania", "Russia", "Slovakia", "Ukraine"},
"Portugal": {"Spain"},
"Qatar": {"Saudi Arabia"},
"Romania": {"Bulgaria", "Hungary", "Moldova", "Serbia", "Ukraine"},
"Russia": {"Azerbaijan", "Belarus", "China", "Estonia", "Finland", "Georgia", "Kazakhstan", "North Korea", "Latvia", "Lithuania", "Mongolia", "Norway", "Poland", "Ukraine"},
"Rwanda": {"Burundi", "Democratic Republic of the Congo", "Tanzania", "Uganda"},
"Saint Helena": {"Ascension", "and Tristan da Cunha "},
"Saint Martin": {"Sint Maarten"},
"San Marino": {"Italy"},
"Saudi Arabia": {"Iraq", "Jordan", "Kuwait", "Oman", "Qatar", "UAE", "Yemen"},
"Senegal": {"Gambia", "Guinea", "Guinea-Bissau", "Mali", "Mauritania"},
"Serbia": {"Bosnia and Herzegovina", "Bulgaria", "Croatia", "Hungary", "Kosovo", "Macedonia", "Montenegro", "Romania"},
"Sierra Leone": {"Guinea", "Liberia"},
"Sint Maarten": {"Saint Martin"},
"Slovakia": {"Austria", "Czech Republic", "Hungary", "Poland", "Ukraine"},
"Slovenia": {"Austria", "Croatia", "Hungary", "Italy"},
"Somalia": {"Djibouti", "Ethiopia", "Kenya"},
"South Africa": {"Botswana", "Lesotho", "Mozambique", "Namibia", "Eswatini", "Zimbabwe"},
"South Sudan": {"Central African Republic", "Democratic Republic of the Congo", "Ethiopia", "Kenya", "Sudan", "Uganda"},
"Spain": {"Andorra", "France", "Gibraltar", "Portugal", "Morocco"},
"Sudan": {"Central African Republic", "Chad", "Egypt", "Eritrea", "Ethiopia", "Libya", "South Sudan"},
"Suriname": {"Brazil", "French Guiana", "Guyana"},
"Sweden": {"Finland", "Norway"},
"Switzerland": {"Austria", "France", "Italy", "Liechtenstein", "Germany"},
"Syria": {"Iraq", "Israel", "Jordan", "Lebanon", "Turkey"},
"Tajikistan": {"Afghanistan", "China", "Kyrgyzstan", "Uzbekistan"},
"Tanzania": {"Burundi", "Democratic Republic of the Congo", "Kenya", "Malawi", "Mozambique", "Rwanda", "Uganda", "Zambia"},
"Thailand": {"Burma", "Cambodia", "Laos", "Malaysia"},
"Togo": {"Benin", "Burkina Faso", "Ghana"},
"Tunisia": {"Algeria", "Libya"},
"Turkey": {"Armenia", "Azerbaijan", "Bulgaria", "Georgia", "Greece", "Iran", "Iraq", "Syria"},
"Turkmenistan": {"Afghanistan", "Iran", "Kazakhstan", "Uzbekistan"},
"Uganda": {"Democratic Republic of the Congo", "Kenya", "Rwanda", "South Sudan", "Tanzania"},
"Ukraine": {"Belarus", "Hungary", "Moldova", "Poland", "Romania", "Russia", "Slovakia"},
"United Arab Emirates": {"Oman", "Saudi Arabia"},
"United Kingdom": {"Ireland"},
"United States": {"Canada", "Mexico"},
"Uruguay": {"Argentina", "Brazil"},
"Uzbekistan": {"Afghanistan", "Kazakhstan", "Kyrgyzstan", "Tajikistan", "Turkmenistan"},
"Venezuela": {"Brazil", "Colombia", "Guyana"},
"Vietnam": {"Cambodia", "China", "Laos"},
"West Bank": {"Israel", "Jordan"},
"Western Sahara": {"Algeria", "Mauritania", "Morocco"},
"Yemen": {"Oman", "Saudi Arabia"},
"Zambia": {"Angola", "Botswana", "Democratic Republic of the Congo", "Malawi", "Mozambique", "Namibia", "Tanzania", "Zimbabwe"},
"Zimbabwe": {"Botswana", "Mozambique", "South Africa", "Zambia"},
}
paths = set()
for start in countries:
visited = set()
partial_paths = [[start]]
for path in partial_paths:
node = path[-1]
if node not in visited:
if tuple(path[::-1]) not in paths: # don't record [A...B] and [B...A]
paths.add(tuple(path))
visited.add(node)
for neighbor in countries[node]:
if neighbor in countries:
partial_paths.append(path + [neighbor])
paths_by_len = defaultdict(set)
for path in paths:
paths_by_len[len(path)].add(path)
for n, paths in sorted(paths_by_len.items()):#, reverse=True):
print(f"{len(paths)} paths of length {n}")
for path in paths:
print(path)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment