# Assign unique slugs to set of people. Slugs are as short as possible. (New elements only added to ensure uniqueness.)

I have a Python function that will terminate when some condition is fulfilled.
That could happen after the first (easy) step. But more steps (of increasing complexity) may follow.

Below is the simplified example function find_slugs.
For each person in database it finds a slug, which is unique and as short as possible.

To avoid code repetition it was necessary to create the subfunction maybe_finish.
It checks if the slugs are already unique, and returns the result if they are.
Otherwise it prepares the next step by creating blocks_to_refine, and returns None.

Between the steps are conditional returns, contracted to one line:

if maybe_result := maybe_finish(): return maybe_result


In three lines it would look like this:

maybe_result = maybe_finish()
if maybe_result is not None:
return maybe_result


Repeating this line does not seem like an elegant solution to me.
(It is essentially repeating three lines of code again and again.)

I would be interested in different approaches to this example problem.

For the given list of people the result is {0: 'JohnSpam85a', 1: 'JohnSpam85b', 2: 'JohnEggs91', 3: 'JohnEggs92', 4: 'EmmaFish95a', 5: 'EmmaFish95b', 6: 'MaryBeer', 7: 'MaryWine', 8: 'Owen', 9: 'Ruth'}. For the first three it is {0: 'JohnSpam85a', 1: 'JohnSpam85b', 2: 'JohnEggs'}. For the last three {7: 'Mary', 8: 'Owen', 9: 'Ruth'}.

(There is a corresponding question on Stackoverflow.)

from collections import defaultdict

database = {
0: {'name1': 'John', 'name2': 'Spam', 'born': '1985'},  # JohnSpam85a
1: {'name1': 'John', 'name2': 'Spam', 'born': '1985'},  # JohnSpam85b
2: {'name1': 'John', 'name2': 'Eggs', 'born': '1991'},  # JohnEggs91
3: {'name1': 'John', 'name2': 'Eggs', 'born': '1992'},  # JohnEggs92
4: {'name1': 'Emma', 'name2': 'Fish', 'born': '1995'},  # EmmaFish95a
5: {'name1': 'Emma', 'name2': 'Fish', 'born': '1995'},  # EmmaFish95b
6: {'name1': 'Mary', 'name2': 'Beer', 'born': '2000'},  # MaryBeer
7: {'name1': 'Mary', 'name2': 'Wine', 'born': '2000'},  # MaryWine
8: {'name1': 'Owen', 'name2': 'Wine', 'born': '2000'},  # Owen
9: {'name1': 'Ruth', 'name2': 'Milk', 'born': '2000'}   # Ruth
}

alphabetical_letters = ['a', 'b', 'c', 'd']

def find_slugs():

def maybe_finish():
# A block is a list of numbers with (currently) the same slug.
slug_to_block = defaultdict(list)
for number, slug in number_to_slug.items():
slug_to_block[slug].append(number)
if len(slug_to_block) == len(database):
return number_to_slug
nonlocal blocks_to_refine
blocks_to_refine = []
for block in slug_to_block.values():
if len(block) > 1:
blocks_to_refine.append(block)

##################################################################

blocks_to_refine = None  # created and updated in maybe_finish

number_to_slug = dict()  # result

for number, table_row in database.items():
number_to_slug[number] = table_row['name1']

if maybe_result := maybe_finish(): return maybe_result

# step 2: add last name
for block in blocks_to_refine:
for number in block:
number_to_slug[number] += database[number]['name2']

if maybe_result := maybe_finish(): return maybe_result

# step 3: add year of birth
for block in blocks_to_refine:
for number in block:
number_to_slug[number] += database[number]['born'][2:4]

if maybe_result := maybe_finish(): return maybe_result

# step 4: append letter to year of birth
for block in blocks_to_refine:
for i, number in enumerate(block):
number_to_slug[number] += alphabetical_letters[i]

return number_to_slug

New contributor
Watchduck is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. yesterday
• I did not change the question. I simply added some code at the end, that can be used to measure the performance of the different approaches. yesterday
• That code is now in my own answer. 23 hours ago

maybe_finish building a list of list does not feel great here, also using the database variable only for a quick shortcut does not feel necessary either as the complexity is still $$\O(2n)\$$. Consider yielding your blocks instead and flatten them from the call site.

alphabetical_letters is not necessary either as it already exist in the string module. You also don't need to use a list here, strings are indexable too.

Consider passing database as a parameter to the find_slugs function, this ease reuse and testing. In fact, given your example input, using doctest here seems like a sensible thing to do.

Proposed improvements:

import itertools
from string import ascii_lowercase as alphabet
from collections import defaultdict

flatten = itertools.chain.from_iterable

def find_duplicates(slugs):
similar_slugs = defaultdict(list)
for number, slug in slugs.items():
similar_slugs[slug].append(number)
for same_slug in similar_slugs.values():
if len(same_slug) > 1:
yield same_slug

def build_slugs(database):
"""Convert rows from the database into a unique slug
as short as possible for each row.

>>> database = {
...     0: {'name1': 'John', 'name2': 'Spam', 'born': '1985'},
...     1: {'name1': 'John', 'name2': 'Spam', 'born': '1985'},
...     2: {'name1': 'John', 'name2': 'Eggs', 'born': '1991'},
...     3: {'name1': 'John', 'name2': 'Eggs', 'born': '1992'},
...     4: {'name1': 'Emma', 'name2': 'Fish', 'born': '1995'},
...     5: {'name1': 'Emma', 'name2': 'Fish', 'born': '1995'},
...     6: {'name1': 'Mary', 'name2': 'Beer', 'born': '2000'},
...     7: {'name1': 'Mary', 'name2': 'Wine', 'born': '2000'},
...     8: {'name1': 'Owen', 'name2': 'Wine', 'born': '2000'},
...     9: {'name1': 'Ruth', 'name2': 'Milk', 'born': '2000'},
... }
>>> build_slugs(database)
{0: 'JohnSpam85a', 1: 'JohnSpam85b', 2: 'JohnEggs91', 3: 'JohnEggs92', 4: 'EmmaFish95a', 5: 'EmmaFish95b', 6: 'MaryBeer', 7: 'MaryWine', 8: 'Owen', 9: 'Ruth'}
"""
number_to_slug = {}  # result

for number, table_row in database.items():
number_to_slug[number] = table_row['name1']

# step 2: add last name
for number in flatten(find_duplicates(number_to_slug)):
number_to_slug[number] += database[number]['name2']

# step 3: add year of birth
for number in flatten(find_duplicates(number_to_slug)):
number_to_slug[number] += database[number]['born'][2:4]

# step 4: append letter to year of birth
for block in find_duplicates(number_to_slug):
for letter, number in zip(alphabet, block):
number_to_slug[number] += letter

return number_to_slug

if __name__ == '__main__':
import doctest
print(doctest.testmod())

• Lovely concise implementation. I would advise replacing number with a better name, index would be better for example. And if we have an index, we don't need a map, only a list for slugs. The second issue I have is the performance of find_duplicates: I'd favor a different function splitting the "solved" slugs from the unsolved ones, so the solved ones don't have to be re-iterated over at every step. Oh... and really the last step needs to keep iterating until there's no duplicate left; if I supply 16 person with identical details until then, the current version fails badly. May 25 at 17:02
• My new answer builds upon this one. I have modified find_duplicates to refine the duplicates from the last step, instead of looping through all slugs in each step. (BTW, I tried up to 26 people with identical details, and there is no problem.) 23 hours ago

Clarify the real problem. Your question focuses on how to deal with the repeated if-finished checks. But that repetition is just a small part of a larger repetition across the four slug-creation steps. Steps 2 and 3 are already identical in form: iterate over blocks_to_refine and then over block, appending to the slugs as we go. Step 4 differs from 2 and 3 only because it uses enumerate(). Step 1 seems more different because we are setting number_to_slug values rather than appending to them. But all of those differences can be ironed away by (a) using enumerate() across all steps and (b) initializing variables differently so that even Step 1 operates by appending. In other words, we want every step to have the same structure:

for block in blocks_to_refine:
for i, n in enumerate(block):
number_to_slug[n] += ...


Define a list of slug functions to compute what needs to be appended. To execute the four steps, just iterate over those functions. After each step, check whether you are done and possibly return early. Since we have eliminated the code repetition, there's no need to resort to awkward inner functions and reliance on resetting nonlocal variables (whenever you find yourself feeling the need for the latter, take it as a sign that bigger refactoring might be needed).

def find_slugs():
# Returns a dict mapping each DB number to a unique slug.

# Initialize the return value and the DB numbers that need processing.
slugs = {n : '' for n in database}
todo = [list(slugs)]

# Functions to compute each slug element.
slug_funcs = [
lambda _, n: database[n]['name1'],
lambda _, n: database[n]['name2'],
lambda _, n: database[n]['born'][2:4],
lambda i, _: alphabetical_letters[i],
]

# Build the slugs.
for sf in slug_funcs:
for block in todo:
for i, n in enumerate(block):
slugs[n] += sf(i, n)

# Dict mapping each slug to its DB numbers.
slug_to_nums = defaultdict(list)
for n, slug in slugs.items():
slug_to_nums[slug].append(n)

# Return if all slugs unique.
if len(slug_to_nums) == len(database):
return slugs

# DB numbers for slugs needing refinement.
todo = [
ns
for ns in slug_to_nums.values()
if len(ns) > 1
]

return slugs

• Thank you for that great answer. There is just a small problem with your code. To make it visible, I have added two more people with the same name and birth year. With your code they become EmmaFish95c and EmmaFish95d. But of course, the letters should always start at the beginning of the alphabet. In my code, that is what the blocks are for. May 25 at 8:38
• @Watchduck For future reference, I believe it's frowned on to edit your question code after people have submitted reviews. In any case, it's trivial to restore the block concept, as illustrated in the slightly-revised code above.
– FMc
May 25 at 16:15
• Do you see a reason for the performance loss that coincides with looping through step functions? As far as I can see, fun1 (yours) does essentially the same as fun0 (my initial code), and fun4 is just a nicer way to write fun3. Is there a way to have the improved readability without the loss in performance? 1 hour ago

# nested def

Sometimes I will diplomatically explain that nesting defs causes excessive coupling similar to global variables, and is a technique you should probably avoid. Plus it impacts testability. But here, I will just come right out and say it.

No. Do not nest maybe_finish() as you've done. Break it out as a separate helper, and use explicit parameters to communicate with it. Pass in number_to_slug.

As written, it is unclear what its single responsibility is, and it's hard to reason about its contracts.

Possibly it should be a pair of helpers: one that compares lengths and another that works on blocks to refine.

Do not implicitly return a value when dropping off the end of the function, since this is not a procedure that is strictly being evaluated for side effects. Prefer an explicit return None.

# appropriate name

The single biggest thing wrong with def maybe_finish(): is that it is just a terrible name. It doesn't help the Gentle Reader to identify its purpose, and no """docstring""" or # comment linked "uniqueness" to the notion of being finished. Consider renaming this predicate to slugs_are_unique or slugs_unique.

[ EDIT: After my review the question's title was updated to give exactly the help I sought from a docstring as I was trying to read the code: "Assign unique slugs to set of people. Slugs are as short as possible. (New elements only added to ensure uniqueness.)" ]

# mixed type

    blocks_to_refine = None  # created and updated in maybe_finish


No. Initialize to [] the empty list, rather than telling mypy it is an Optional[list]. Or perhaps this could be entirely local to maybe_finish()?

Kudos, the number_to_slug return variable is well named.

# conventional loop variable

    for number, table_row in ...


The identifier number is accurate, but rather vague. I was left wondering if it was some summary statistic over the row data. And then I saw what it was being used for.

Prefer the index variable i for simple loops such as this.

# iterate over functions

There are four steps. Consider adding four unit tests which trigger each of the four returns.

Define four helpers:

• set_first_name()
• add_last_name()
• add_birth_year()
• append_letter()

Now you no longer need four tests for early return, as writing it once suffices:

steps = [set_first_name, add_last_name, add_birth_year, append_letter]
for step in steps:
step(number_to_slug)
if maybe_result := maybe_finish(number_to_slug):
return maybe_result


The following is my improvement of the code by 301_Moved_Permanently. The crucial feature in that answer was the return of a generator by find_duplicates. But (as mentioned by Matthieu M.) it is not efficient, to check all slugs for duplicates. Instead, the function should refine the duplicates from the last step. That requires using the generator twice: First in the for-loop to append the slugs, and then in the next call of find_duplicates. As generators can only be used once, it is doubled with itertools.tee.

import itertools
from collections import defaultdict
from string import ascii_lowercase as alphabet

flatten = itertools.chain.from_iterable

def double_generator(gen): return itertools.tee(gen, 2)

def find_duplicates(number_to_slug, dup_gen_to_refine=None):
slug_to_numbers = defaultdict(list)
if dup_gen_to_refine is not None:
for number in flatten(dup_gen_to_refine):
slug = number_to_slug[number]
slug_to_numbers[slug].append(number)
else:
for number, slug in number_to_slug.items():
slug_to_numbers[slug].append(number)
for block in slug_to_numbers.values():
if len(block) > 1:
yield block

def find_slugs(database):
number_to_slug = {}  # result

for number, table_row in database.items():
number_to_slug[number] = table_row['name1']

# step 2: add last name
dup_gen = find_duplicates(number_to_slug)
dup_gen_to_append, dup_gen_to_refine = double_generator(dup_gen)
for number in flatten(dup_gen_to_append):
number_to_slug[number] += database[number]['name2']

# step 3: add year of birth
dup_gen = find_duplicates(number_to_slug, dup_gen_to_refine)
dup_gen_to_append, dup_gen_to_refine = double_generator(dup_gen)
for number in flatten(dup_gen_to_append):
number_to_slug[number] += database[number]['born'][2:4]

# step 4: append letter to year of birth
dup_gen = find_duplicates(number_to_slug, dup_gen_to_refine)
dup_gen_to_append, dup_gen_to_refine = double_generator(dup_gen)
for block in dup_gen_to_append:
for letter, number in zip(alphabet, block):
number_to_slug[number] += letter

return number_to_slug


This does not look very elegant, as there is some code duplication in each step. I tried looping through a list of functions, as suggested by FMc, but for some reason that comes with some cost in performance. (That code is not shown here, but on Pastebin.)

I used the following code to generate a database with 112750 rows:

from string import ascii_uppercase as alphabet

db_list = []

for a, b in product(range(5), range(5)):
row = {'name1': alphabet[a], 'name2': alphabet[b], 'born': '2000'}
for _ in range(10):
db_list.append(row)

for a, b, c in product(range(5, 20), range(5, 20), range(100)):
row = {'name1': alphabet[a], 'name2': alphabet[b], 'born': str(1900 + c)}
db_list.append(row)

for i, j in product(range(300), range(300)):
row = {'name1': str(i) + 'x', 'name2': str(j) + 'y', 'born': '2000'}
db_list.append(row)

long_database = {}
for i, row in enumerate(db_list):
long_database[i] = row


The following code is to measure the performance of each approach:
(I modified all functions to take database as an argument, and to use ascii_lowercase.)

import time

for i, fun in enumerate([fun0, fun1, fun2, fun3, fun4]):
start = process_time()
result = fun(database)
end = process_time()
print(f'fun{i} took {end - start} seconds')
if i == 0:
first_result = result
else:
assert result == first_result


The results look always something like this:

fun0 took 0.147413774 seconds              # my initial code
fun1 took 0.20480099000000002 seconds      # by FMc
fun2 took 0.14875496700000002 seconds      # by 301_Moved_Permanently
fun3 took 0.09883650700000002 seconds      # this answer
fun4 took 0.13451846199999995 seconds      # like fun1 and fun3

New contributor
Watchduck is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.