minimum passports for worldwide visa free travel

the idea

Henley & Partners released their 2024 passport rankings earlier this year.

But I have more than one passport and I wanted to know the combined power of my passports, not just the power of a single nationality.

And it turns out that on the road to answering that question we can also figure out what the strongest pair and trio of passports are, just for fun.

We can even go so far as to try and answer the question: what’s the smallest number of passports you would need to travel to every destination in the world without a visa?

This happens to be the most challenging of the questions, given it’s an instance of the NP-complete Set cover problem. Luckily, The Algorithm Design Manual offers us some valuable suggestions to try…

getting the data

As far as web scraping goes, this is mercifully straightforward. A quick look at the ‘Fetch/XHR’ requests when loading the page provides us with the API endpoint to get some summary data on all the available countries, alongside the endpoint to hit when we want to get the data of a specific country.

For example, an Australian passport’s visa-free destinations are found at: https://api.henleypassportindex.com/api/v3/visa-single/AU. And accessing other countries' data only requires the final country code to be changed (eg: ‘AU’ before), country codes that are made available in the overview data at: https://api.henleypassportindex.com/api/v3/countries.

It’s as simple as that!

So, let’s just copy the overview data directly from the browser and save that in a countries.json file, before writing a scraper to get the visa free destinations of each country and combine them into a single passports.json file:

import json
from requests import Session
from requests.adapters import HTTPAdapter
from requests.packages.urllib3.util.retry import Retry
from concurrent.futures import ThreadPoolExecutor

requests_session = Session()

# session retries a request 3 times depending on response status code
retries = Retry(
    total = 3,
    backoff_factor=1,
    status_forcelist=[429,500,502,503,505]
)
requests_session.mount("https://",HTTPAdapter(max_retries=retries))

def my_request(url: str):
    '''
    A custom requests function that adds some basic but useful features.
    '''
    try:
        response = requests_session.get(url,headers=headers)
        if response.status_code == 200:
            data = json.loads(response.text)
            return data
        else:
            print(f'Request not 200 response for {url}, got instead: {response.status_code}')

    except Exception as e:
        print(f'Request failed for {url} with: {e}')

def get_visa_free_destinations(countries_file: str = './countries.json'):
    '''
    Requests the visa-free destinations json for each country in the countries.json file.
    '''
    base_url = 'https://api.henleypassportindex.com/api/v3/visa-single/'
    with open(countries_file) as f:
        data = json.load(f)
        links = [base_url + country['code'] for country in data['countries']]
        MAX_THREADS = 10
        with ThreadPoolExecutor(max_workers=MAX_THREADS) as executor:
            json_files = list(executor.map(my_request,links))
    return json_files

data = get_visa_free_destinations()
with open('passports.json','w') as f:
    json.dump(data, f)

answers

combined passport power

Taking a quick look, there are 227 destinations worldwide:

import json
with open('./passports.json', 'r') as f:
    data = json.load(f)
    data = {d['country']:d for d in data}
print(len(data))

227

To figure out how many of these destinations are visa free for a collection of passports, instead of just one, we can write a general function that aggregates all the visa_free_access, visa_on_arrival, and electronic_travel_authorisation¹ destinations for a collection of passports:

def visa_free_destinations(*passports: list) -> set:
    '''
    Gets the set of destination names that are visa free for a collection
    of passports.
    '''
    if not passports:
        return None
    visa_types = {'visa_free_access', 'visa_on_arrival', 'electronic_travel_authorisation'}
    destinations = set()
    for passport in passports:
        for visa_type in visa_types:
            if visa_type in data[passport]: # same 'data' as before (it's global)
                destinations |= {destination['name'] for destination in data[passport][visa_type]}
    return destinations
print(len(visa_free_destinations('United States')))
print(len(visa_free_destinations('South Korea')))
print(len(visa_free_destinations('United States', 'South Korea')))

188
193
198

So, for example, having both a US and a South Korean passport gives one visa free access to a total of 198 of the 227 destinations worldwide, an extra 10 over an American passport and only an extra 5 over a South Korean one, but 4 more than the highest ranked passports!

best passport pairs

Is there a pair of passports stronger than a US passport paired with a South Korean one?

To check, we can just test every combination of pairs of passports. Given there are 227 passport, we will only need to test \((227 \times 226) / 2= 25651\) pairs, which is still reasonable; we can even just sort them from most visa free destinations to least.

def passport_pairs() -> dict:
    '''
    Computes the visa free destinations of all combinations of passport pairs.
    '''
    passports = sorted(data) # same as before
    pairs = {}
    for i, passport in enumerate(passports):
        for other_passport in passports[i+1:]:
            pairs[(passport, other_passport)] = visa_free_destinations(passport, other_passport)
    return pairs
pairs = passport_pairs()
top_10 = sorted(pairs, key=lambda p: len(pairs[p]), reverse=True)[:10]
for pair in top_10:
    print(f'{pair[0]} and {pair[1]}: {len(pairs[pair])} in total.')

Singapore and United Arab Emirates: 210 in total.
Japan and United Arab Emirates: 209 in total.
Benin and Japan: 207 in total.
Denmark and United Arab Emirates: 207 in total.
Finland and United Arab Emirates: 207 in total.
France and United Arab Emirates: 207 in total.
Germany and United Arab Emirates: 207 in total.
Ireland and United Arab Emirates: 207 in total.
Italy and United Arab Emirates: 207 in total.
Japan and Senegal: 207 in total.

And there we have it: a Singaporean passport paired with an Emirati one is the most powerful pair in 2024!

best passport trios

What if you could have any 3 passports?

Well, what was only 51302 total combinations for pairs of passports becomes \((227\times 226 \times 225)/6 = 1923825\) when we consider trios, which is starting to become a meaningfully large number.

With that said, it’s still possible to brute force all the combinations in reasonable time, especially seeing as we’ve already computed the pairs; we can use our previously computed pairs as a starting point, expanding each pair’s set of visa free destinations by the visa free destinations of a third country.

But, for the sake of memory efficiency, our function will just keep track of a leaderboard of the top \(n\) most powerful trios:

from heapq import heappushpop
def passport_trios(leaderboard_size: int = 10) -> list:
    '''
    Computes the visa free destinations of all combinations of passport trios
    while only keeping track of the 'n' most powerful.

    Function builds off the result of computing the visa free destinations of
    every combination of passport pairs.
    '''
    heap = [(0,)] * leaderboard_size # initialise heap
    passports = sorted(data)
    for i, first_passport in enumerate(passports):
        for j, second_passport in enumerate(passports[i+1:], start=i+1):
            for third_passport in passports[j+1:]:
                trio_destinations = pairs[first_passport, second_passport] | visa_free_destinations(third_passport)
                heappushpop(heap, (len(trio_destinations), first_passport, second_passport, third_passport))
    return heap

trios = passport_trios()
for trio in reversed(trios):
    print(f'{trio[1]}, {trio[2]}, and {trio[3]}: {trio[0]} in total.')

Japan, Mali, and United Arab Emirates: 218 in total.
Japan, Sierra Leone, and United Arab Emirates: 217 in total.
Mali, United Arab Emirates, and United Kingdom: 216 in total.
Mali, South Korea, and United Arab Emirates: 216 in total.
Mali, Sweden, and United Arab Emirates: 216 in total.
Japan, The Gambia, and United Arab Emirates: 217 in total.
Mali, Spain, and United Arab Emirates: 216 in total.
Mali, Malta, and United Arab Emirates: 216 in total.
Mali, Norway, and United Arab Emirates: 216 in total.
Japan, Tunisia, and United Arab Emirates: 216 in total.

It’ll take a few seconds to run, at least it does on my machine, but the answer should pop out eventually, and reveal that the most powerful passport trio is unique! Granting visa free travel to 218 of the 227 destinations worldwide, some ~96% coverage.

But what about 100% coverage?

set covering

The most challenging question for last: the minimum set of passports to travel visa free to all destinations in the world (aka 100% coverage).

If finding the most powerful passport trios wasn’t an obvious enough foreshadowing that our brute force approach wouldn’t scale. Consider how fast the number of total possible combinations of passports we would need to check grows as \(n\), the number of passports we’re combining, grows:

It’s simply not feasible to extend our current approach until we stumble upon a collection of passports with 100% coverage.

So, instead, let’s take a less direct approach and start by constructing a set of passports with 100% coverage, giving us a baseline for the potential minimum set, before trying to minimise it.

One way to construct such a set with 100% coverage, is to iterate through our list of passports picking the one that offers us visa free travel to the largest number of destinations we are still missing visa free travel to. In doing so, we are guaranteed to either find a collection of passports with 100% coverage or discover that it is impossible to travel visa free to certain destinations.

Either way, it’s a very straightforward way to get the ball rolling (i.e. just be greedy). It just requires a little care before implementing. In particular, the construction of a dictionary that maps each passport to its set of visa free destinations:

# a dictionary that maps passports to their visa free destinations (vfds)
vfds = {p: visa_free_destinations(p) | {p} for p in data}

Importantly, a passport must be included in its set of visa free destinations. As in, it goes without saying that having an Indian passport, for example, grants one visa free travel to India, by extension, each passport grants visa free travel to its own destination and so should be a member of its own set of visa free destinations in vfds.²

With that out of the way, we can greedily select a set of passports with 100% coverage as follows:

def greedy_set_covering(subsets: dict, universal: set) -> list:
    answer = set()
    while len(universal) > 0:
        largest_subset = min(subsets, key = lambda e : len(universal - subsets[e]))
        answer.add(largest_subset)
        universal -= subsets[largest_subset] # remove
    return answer
greedy_ans = greedy_set_covering(vfds, set(vfds))
print(greedy_ans)

{'Kenya', 'United Arab Emirates', 'Bhutan', 'Libya', 'France', 'Benin', 'North Korea', 'Turkmenistan', 'Cameroon', 'Afghanistan', 'China'}

So, our first minimum set of passports to see the world visa free includes:

• Kenya
• UAE
• Bhutan
• Libya
• France
• Benin
• North Korea
• Turkmenistan
• Cameroon
• Afghanistan
• China

11 passports in total.

But is this the true minimum? Is there not a smaller set?

experimentation

Before trying more clever ways of working down from 11, it might be worth seeing what happens if we start our greedy search with the most powerful passport pair already in hand (i.e. Singapore + UAE):

print(greedy_set_covering(vfds, set(vfds) - vfds['Singapore'] - vfds['United Arab Emirates']))

{'Kenya', 'Jordan', 'Japan', 'Mali', 'North Korea', 'Turkmenistan', 'Afghanistan', 'Bangladesh'}

Surprise, surprise, we’ve found a smaller set:

• Singapore
• UAE
• Kenya
• Jordan
• Japan
• Mali
• North Korea
• Turkmenistan
• Afghanistan
• Bangladesh,

a total of 10 passports.

So, we can already dismiss our first answer of a minimum of 11 passports.

Continuing this trend, what if we started with the most powerful trio (i.e Singapore, Mali, and UAE):

print(greedy_set_covering(vfds, set(vfds) - vfds['Japan'] - vfds['United Arab Emirates'] - vfds['Mali']))

{'Kenya', 'Jordan', 'North Korea', 'Turkmenistan', 'Afghanistan', 'Bangladesh'}

Even better! We found an even smaller set of passports with 100% coverage:

• Japan
• Mali
• UAE
• Kenya
• Jordan
• North Korea
• Turkmenistan
• Afghanistan
• Bangladesh,

only 9!

Seeing as this seems to be working, it may be tempting to spend the time to compute the power of the 107,734,200 unique combinations of 4 passports, enabling us to start our greedy approach from the most powerful set of 4 passports.

But doing so wouldn’t really help us determine the minimum possible set. Because even if we did find a smaller set of passports, it wouldn’t guarantee that there didn’t exist an even smaller one that relied on combinations of passports we didn’t test.

We’re better off looking for patterns to exploit in the data and in the answers we’ve already found.

patterns

One such pattern is that certain countries (i.e. Afghanistan, North Korea…) always end up in the sets of passports we construct.

Why is that?

The answer lies in the number of passports that can actually travel visa free to one of these destinations:

print([p for p in vfds if 'Afghanistan' in vfds[p]])
print([p for p in vfds if 'North Korea' in vfds[p]])

['Afghanistan']
['North Korea']

Ah…

No passport can travel visa free to Afghanistan or North Korea. Meaning, we need to have each of these passports in our minimum set if we want 100% coverage, in other words, their inclusion is a necessary condition on our minimum set.

Following through on this idea, let’s sort all the destinations in increasing order of number of passports that have visa free travel to it.

To do so, let’s create an inverse of vfds that maps each passport to the set of passports that have visa free travel to it (a painfully confusing sentence):

from collections import defaultdict
inv_vfds = defaultdict(set)
for passport in vfds:
    for p in vfds[passport]:
        inv_vfds[p].add(passport)

Giving us:

for p in sorted(inv_vfds, key=lambda p: len(inv_vfds[p]))[:15]:
    print(f"{p}: {len(inv_vfds[p])}")

Afghanistan: 1
North Korea: 1
Turkmenistan: 1
Libya: 3
Bhutan: 4
Equatorial Guinea: 5
Eritrea: 5
India: 6
South Sudan: 7
Algeria: 8
Congo (Dem. Rep.): 8
Cameroon: 8
Papua New Guinea: 8
Sudan: 9
Yemen: 13

This is massively helpful!

We now know a minimum set must include Afghanistan, North Korea, and Turkemistan. But it also means that we can remove all the destinations these passports have visa free travel to from the set of all destinations we need to cover. Much in the same way we started our greedy algorithm from the most powerful passport pair and passport trio.

print(len(set(vfds) - vfds['Afghanistan'] - vfds['Turkmenistan'] - vfds['North Korea']))

165

Now, if there is to be a collection of fewer than 9 passports with 100% coverage, there needs to be a collection of 5 passports or fewer that can cover the remaining 165 destinations left from possessing an Afghan, Turkmen, and North Korean passport.

While this is progress, it’s still \(^{224}C_{5}=4,493,032,544\) combinations to check…

But what if we did something with Libya? Only 2 countries, other than itself, have visa free travel to it:

print(inv_vfds['Libya'])

{'Tunisia', 'Libya', 'Jordan'}

In effect, this means that we’ll need at least one of those three passports in our minimum set. And given Jordan is a visa free destination for Turkmen passports, there’s a stronger chance³ we wouldn’t need it unless it gave us access to another rare destination that few other passports have visa free travel to, which is unlikely.

Doing the same for Bhutan:

print(inv_vfds['Bhutan'])

{'Bhutan', 'India', 'Bangladesh', 'Maldives'}

we see that only India, the Maldives, and Bangladesh have visa free travel to it. With the Maldives and Bangladesh already covered by our starting set of Afghan, Turkmen, and North Korean passports.

But why does this matter?

At this stage, we’re just trying to reduce the number of total combinations we’d have to test to check whether a minimum set of 8 passports exists.

And, assuming such a minimum would need to include say, Tunisia and India, on top of Afghanistan, Turkemistan, and North Korea, for example, we would only need to look through \(^{222}C^{3}=1,798,940 \approx ^{227}C3\) combinations, which we can already do, seeing as we checked approximately the same number combinations when finding the most powerful passport trios.

Suddenly, the possibility of verifying the optimality of a minimum set of 9 passports for 100% coverage is looking tractable…

we don’t even need backtracking!

In reality, we would have to test 1,798,940 combinations for each country with visa free travel to Bhutan, for each country with visa free travel to Libya, which ends up being \((1,798,940*4*3)=21,587,280\) combinations⁴.

But we can be hopeful and prioritise the starting combinations that are probably going to perform better. In the case of Libya, this would mean testing Tunisia first, then Libya, and then Jordan. And for Bhutan, it would mean testing Bhutan, then India, then Bangladesh, and finally the Maldives.

In other words, it would mean testing the 1,798,940 combination of passport trios for each of the following 5 starting passports in the following order of priority:

1. Afghanistan + Turkmenistan + North Korea + Tunisia + Bhutan
2. Afghanistan + Turkmenistan + North Korea + Tunisia + India
3. Afghanistan + Turkmenistan + North Korea + Tunisia + Bangladesh
4. Afghanistan + Turkmenistan + North Korea + Tunisia + Maldives
5. Afghanistan + Turkmenistan + North Korea + Libya + Bhutan
6. Afghanistan + Turkmenistan + North Korea + Libya + India
7. Afghanistan + Turkmenistan + North Korea + Libya + Bangladesh
8. Afghanistan + Turkmenistan + North Korea + Libya + Maldives
9. Afghanistan + Turkmenistan + North Korea + Jordan + Bhutan
10. Afghanistan + Turkmenistan + North Korea + Jordan + India
11. Afghanistan + Turkmenistan + North Korea + Jordan + Bangladesh
12. Afghanistan + Turkmenistan + North Korea + Jordan + Maldives

The best part is, while I had originally implemented a greedy backtracking algorithm to sieve through larger search space than this when first attempting the problem, this approach is doable with brute force!

So, without overthinking things, we can copy and amend our passport_trios function to take a starting set of passports and only print a trio of passports if they cover the remaining set of destinations:

def look_for_eight(starting_set: set) -> list:
    '''
    A modification of our 'passport_trios' function to look for a
    set of 8 passports with 100% coverage.
    '''
    # remove the starting passports
    passports = sorted(set(vfds) - starting_set)
    # initialise the universal set to include only destinations we're missing
    universal = set(vfds)
    for p in starting_set:
        universal -= vfds[p]
    # iterate through combinations
    for i, first_passport in enumerate(passports):
        for j, second_passport in enumerate(passports[i+1:], start=i+1):
            for third_passport in passports[j+1:]:
                if len(universal - vfds[first_passport] - vfds[second_passport] - vfds[third_passport]) == 0:
                    print(f"Here!: {first_passport}, {second_passport}, {third_passport}")

tests = [
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Tunisia', 'Bhutan'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Tunisia', 'India'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Tunisia', 'Bangladesh'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Tunisia', 'Maldives'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Libya', 'Bhutan'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Libya', 'India'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Libya', 'Bangladesh'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Libya', 'Maldives'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Jordan', 'Bhutan'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Jordan', 'India'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Jordan', 'Bangladesh'},
    {'Afghanistan', 'Turkmenistan', 'North Korea', 'Jordan', 'Maldives'},
]
for test in tests:
    look_for_eight(test)

And there we have it!

If you run the above (~1min on my machine), nothing will be printed. So there’s no set of 8 or fewer passports with 100% coverage. Hence, the smallest set of passports you need to travel the globe visa free is 9!