Blog

Quickly finding your favorite League of Legends champion in champ select.

2017-06-26

When I have free time in the evenings, I usually find myself playing a few games of League of Legends before bed with old friends. Anyone who has played a lot of League knows that getting into an actual game can take a bit of time, especially when entering a queue that has a draft-based champion select.

With over 130 champions in the game now, scrolling to find your champion can be a bit of a hassle. There are positional selectors to narrow down the selection but in many cases these can be insufficient. The search bar helps but it can be easy to mistype your champion especially as time is running out. A mistake like this can cause you to panic pick the wrong champion or miss your turn and take on a 5-minute queue penalty until you can search for your next game.

If you pay close attention, though, the search bar in champion select has an interesting algorithm for finding champions based on a search string. Instead of matching your query as a substring, the search algorithm returns all champions whose names contain the (case insensitive) characters of your query in the same order, but not necessarily continuously arranged. If the query were a regular expression, it would looks something like this:

r'(?i).{0,}q.{0,}u.{0,}e.{0,}r.{0,}y.{0,}'

The (?i) indicates case insensitivity and the .{0,} indicate the existence of 0 or more of any character before, after, or between any of the query characters.

As an example, the query ‘blitz’ will return the champion ‘Blitzcrank’, but so will the query ‘btzrk’, as in ‘Blitzcrank.’

The same methodology is used in the SNES game Family Feud, as seen in this tool-assisted speedrun of the game.

In order to avoid dodging the queue, let’s try to determine the shortest length search string required to uniquely identify every champion in the game. If you’re not interested in the method you can skip to the results here.

One of the great things about Riot Games, the makers of League of Legends, is that they have a pretty rich API for league games. They also offer the game’s static data for download, like the champion information in json format!

For this task we’ll be using python. We will need the requests library to get the data, the Counter class for some bookkeeping, and the json module to store our results.

from collections import Counter
import json

import requests

Using the requests library, we can get the json file, and gather all of the champion names into a sorted list.

url = 'http://ddragon.leagueoflegends.com/cdn/6.24.1/data/en_US/champion.json'
r = requests.get(url).json()
names = sorted([r['data'][key]['name'].lower() for key in r['data'].keys()])

Next let’s define a function that will return a list of all possible substrings (continuous or not) of a string. We obtain these substrings using binary flags for each character in the string. We also use a set() object to track the substrings and eliminate any duplicates.

def get_substrings(string):
    length = len(string)
    substrings = set()

    for k in range(1, 2**length):
        binary = "{0:020b}".format(k)[-length:]
        flags = [True if digit == '1' else False for digit in binary]
        sub = [s for s, flag in zip(string, flags) if flag]
        substrings.add(''.join(sub))
    return substrings

Now we can get the substrings for every champion name. Lets store every found substring in a list all_substrings. Let’s also store each champion’s substring set in a dict called substrings.

all_substrings = []
substrings = {}

for name in names:
    subs = get_substrings(name)
    all_substrings = all_substrings + list(subs)
    substrings[name] = subs

Now we’ll use the Counter class which is part of the built-in collections module in python. This will give us a nice dict-like object where the keys are the substrings and the values are their counts from the list. This tells us how many champion names contain each substring, and we can update our dict to filter out only the substrings which are unique.

counter = Counter(all_substrings)
unique = [u for u in counter.keys() if counter[u] == 1]
for name in names:
    substrings[name] = [n for n in substrings[name] if n in unique]

Lastly we’ll go through the dict once more, finding the shortest unique substrings for each champion. Note that we use a try block here in case there are champions without any unique substrings.

for name in names:
    try:
        m = min(map(len, substrings[name]))
    except ValueError:
        substrings[name] = []
    else:
        substrings[name] = sorted([n for n in substrings[name] if len(n) == m])

Finally, let’s output the resulting dict to a json file.

with open('champions.json', 'w') as f:
    json.dump(substrings, f, indent=4)

You can find the results here.

Some fun facts from the results as of writing this post (most recent champion release was Rakan/Xayah):

There are two champions who can be found using a single character: Dr. Mundo (with .) and Quinn (with q).
Vi is the only champion who cannot be uniquely selected with a single string; all of her string sequences are shared with Viktor, for example.

That’s it! Hopefully you can remember the shortest substrings for your favorite champions and have a much easier time locking in your pick and avoiding dodge penalties in future games.

flynn.gg

Christopher Flynn

Blog

Quickly finding your favorite League of Legends champion in champ select.

Further reading