Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Compare, deduce, choose with lexicographic order solution in Clear category for Determine the Order by Phil15
def checkio(words):
letters = sorted(set.union(*map(set, words)))
# 1) Basic comparisons, word by word.
before = {ch: set() for ch in letters}
# NOTE: letters is sorted so before's order is the lexicographic order.
for word in words:
# "word" then "w < o < r < d", before['r'] |= set('wo') for example.
for n, ch in enumerate(word):
before[ch] |= set(word[:n]) - {ch}
# 2) Deduce things: if "r < k" and "k < d" then "r < d".
change = True
while change: # On all given tests, we do this up to 3 times, the last time for nothing.
change = False # This variable will say if we changed `before`.
for letter, bef in before.items():
new = set().union(*map(before.get, bef)) - bef
if new:
before[letter] |= new
change = True
# 3) Choose a letter which has nothing before it, update before & restart.
result = []
while before: # len(letters) times.
# When there are multiple possibilities, it chooses with
# lexicographic order since a dict remembers insertion order.
first = next(ch for ch, bef in before.items() if not bef)
result.append(first)
before.pop(first)
for bef in before.values():
bef.discard(first)
return ''.join(result)
if __name__ == '__main__':
# Important test because my previous code passed
# all tests but was wrong about this new one.
assert checkio(['word', 'spread']) == 'spworead'
# I must say my old code is not the only one wrong, maybe yours is too.
Jan. 29, 2020
Comments:
