Skip to content

Instantly share code, notes, and snippets.

@miraculixx miraculixx/cities_match.py
Last active Jun 19, 2018

Embed
What would you like to do?
map cities by rotated letters
from itertools import combinations
# quick and dirty implementation, not optimized
cities = ['Tokyo', 'London', 'Rome', 'Donlon', 'Kyoto', 'Paris']
normalized = [(c, ''.join(sorted(c.lower()))) for c in cities]
cartesian = list(combinations(normalized, 2))
matches = [[l[0], r[0]] for l, r in cartesian if l[1] == r[1]]
matches.extend([c for c in cities if c not in [m[0] for m in matches] + [m[1] for m in matches]])
matches
# output [['Tokyo', 'Kyoto'], ['London', 'Donlon'], 'Rome', 'Paris']
# improved version by only rotating, not sorting
# -- rotate i times to the left
rot = lambda s, i: s[i:] + s[0:(i)]
# -- keep unrotated with i == 0, rotate every possible way
rotated = [(i, c, rot(c.lower(), i)) for c in cities for i in range(len(c))]
# -- find matches where left is equal to right and right is the original name
matches = [(l[1], r[1]) for l, r in combinations(rotated, 2) if l[2] == r[2] and r[0] == 0]
matches.extend([c for c in cities if c not in [m[0] for m in matches] + [m[1] for m in matches]])
matches
# output [('Tokyo', 'Kyoto'), ('London', 'Donlon'), 'Rome', 'Paris']
cities = ['Tokyo', 'London', 'Rome', 'Donlon', 'Kyoto', 'Paris']
# actually, can be done in 3 statements, without combinatorics. ok it starts to get somewhat involved
rot = lambda s, i: s[i:] + s[0:(i)]
matches = [(c, rot(c.lower(), i).capitalize())
for j, c in enumerate(cities)
for i in range(len(c))
if rot(c.lower(), i) in [cx.lower() for cx in cities[j:]] and i > 0]
matches.extend([c for c in cities if c not in [m[0] for m in matches] + [m[1] for m in matches]])
matches
# output [('Tokyo', 'Kyoto'), ('London', 'Donlon'), 'Rome', 'Paris']
@miraculixx

This comment has been minimized.

Copy link
Owner Author

miraculixx commented Jun 16, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.